This paper presents an efficient computational exhaustive method that permits to calculate both upper and lower response-time bounds for CAN messages. Response-time analysis for CAN messages is relatively limited for computations of the worst case situation. It is computed assuming a maximum transmission time and critical instant releasing of messages in the CAN system. This pessimism implies the maximum interference between messages circulated on the bus. It may be correct from a hard real-time perspective when synchronous releasing, but it doesn’t give good outlook when non-common messages releasing. Hence to obtain an analysis close to the reality, the investigated temporal constraints must take into account both effects of time phasing and bit-stuffing. By using a suitable data structure, our work introduces an elegant algorithm that is able to deal with the previous effects. The obtained results for best and worst cases response-times are different from previous results obtained when assuming an optimist and a pessimist bit-stuffing length