DE102012219079A1 - Method for implementing strict monotonic numerator to securely transfer e.g. critical messages from transmitter to receiver in motor car, involves incrementing counter value until counter value is equal to or larger than stored value - Google Patents

Abstract

The method involves saving a sum of an initial value of a strictly monotonic numerator (56) and a constant value (62) as a stored value in a storage unit i.e. non volatile storage unit (58), where the stored value is used as initial value. The counter value incremented in an occurrence of a certain event until the counter value is equal to or larger than the stored value. A set of codes is assigned with a message that is exchanged between a transmitter (52) and a receiver (54). The codes are computed under consideration of the message and the counter value by using a key. An independent claim is also included for an arrangement for providing a strict monotonic numerator.

Description

The invention relates to a method for implementing a strictly monotonic counter and to an arrangement for providing such a counter. Strictly monotonous counters become u. a. for securely transmitting messages and information from a sender to a recipient. Messages and information are represented by data exchanged between a sender and a receiver.

In particular, the invention relates to a method of providing such a strictly monotonically increasing counter, without having to store the value of the counter after each message transmission.

State of the art

Counters are units for counting successive events, the value of the counter being increased by a pre-agreed amount after occurrence of the event. One speaks of a strictly monotonous counter, if its value only becomes larger or smaller and is never constant. Such counters are used in many ways. An application is, for example, as given below, given in the provision of security services.

The authenticity and / or integrity of messages and data is required in security services for a variety of applications. This is for information security to ensure the confidentiality, availability and integrity of data exchanged between senders and recipients. For this purpose, a number of protection methods are known, with which a protection against dangers and avoidance of damages and risks are to be ensured. However, these protection methods are subject to attack.

A widespread attack on such protection methods is the re-importing of "old" pre-recorded data, a so-called replay attack, on the freshness or freshness of the data. To prevent this, the messages must be recognized as fresh. There are two standard approaches:
So the integration of time stamps or progressive counters is known. However, the use of time stamps requires synchronous clock and receiver clocks, which is often not the case in embedded systems. The use of counters requires reliable, strictly monotone, transmitter-side counters, which must endure especially in embedded systems over a power loss or reboot. The mission will be illustrated by a concrete example:
The provision of security services has standard procedures for protecting the integrity of messages. This is to be able to detect even malicious falsifications of messages to the recipient. One way to do this is to use Message Authentication Codes (MACs). The MAC is calculated on the content of a message and attached to or linked to the message. To compute the MAC you need a secret, for example, a key that is known only to the sender and the receiver. The sender can therefore calculate and transfer the MAC. The receiver also calculates the MAC and compares it to the transmitted MAC. If both agree, the message is unadulterated if the encryption process is secure and only the sender and recipient know the key.

However, an attacker can perform a replay attack, i. H. He picks up a message and plays it back later. Thus, the MAC is still correct and the recipient will erroneously accept the message. This is particularly problematic for frequently recurring message or message content.

To prevent a replay attack, the MAC can be calculated in addition to the message content via a counter. The counter is incremented after each message, resulting in different MACs. However, the transmitter and receiver must have a synchronized counter. The simplest way is to replace the counter reading or value at the beginning of communication between transmitter and receiver. However, since an attacker can hear this, a replay attack will succeed in this case as well, if the levels of the counter repeats itself.

For this reason, strictly monotonic counters, also called monotonic counters, are used. These never overflow the life of the system and are incremented in a strictly monotonic manner. With the aid of this property, the starting value of the counter can then be exchanged between transmitter and receiver. Even in the event that an attacker listens to this transmission, the security of the system is not compromised. If the attacker sent the intercepted message again at a later time, the default would be violated that the counter in the message would be incremented with each transmission, and the receiver could thereby detect the (replay) attack.

For this purpose, however, it must be ensured that the system knows and stores the last counter value at all times, so that even after a reset or reset of the system, the counter is strictly monotonically increasing. For this, the counter value must be stored very often, ideally after each message, in a non-volatile memory.

Disclosure of the invention

Against this background, a method according to claim 1 and an arrangement with the features of claim 6 are presented. Embodiments result from the dependent claims and the description.

With the presented method, it is thus possible to provide a strictly monotonically increasing counter, without having to store the value of the counter after each message transmission.

In order to avoid frequent saving of the current counter value, the sum of the counter value and a defined value, the so-called "pre-step", is stored at the beginning of the communication after the counter value has been exchanged between transmitter and receiver , eg counter value +1000. In this example, the "Pre-Step" is 1000. Now sender and receiver can exchange 1000 messages. After the 1000th message, the sum of the current counter reading and the pre-step, namely counter value +1000, is stored again. If a reset occurs between two memory operations, the stored value will be used as the start value of the counter at the next start. This will skip some counter values. However, the counter is strictly monotonically increasing and the number of memory operations is reduced by a factor of 1000 in the example presented.

It is thus not the current counter value, but a future counter value stored. When this counter value is reached, a future counter value is again stored. After each restart, therefore, a future counter value is always stored as an initial value and the counter is strictly monotonically increasing.

The presented method has, at least in some of the embodiments, considerable advantages. This can reduce the storage frequency of the current counter value. This means that the number of write cycles to the typically non-volatile memory can be reduced. This increases the performance of the system as there are fewer writes to memory. In addition, non-volatile memory life requirements are reduced because fewer write cycles are performed.

Further advantages and embodiments of the invention will become apparent from the description and the accompanying drawings.

It is understood that the features mentioned above and those yet to be explained below can be used not only in the particular combination indicated, but also in other combinations or in isolation, without departing from the scope of the present invention.

Brief description of the drawings

1 shows in a flow chart an embodiment of the presented method.

2 shows an embodiment of the described arrangement.

Embodiments of the invention

The invention is schematically illustrated by means of embodiments in the drawings and will be described in detail below with reference to the drawings.

1 shows in a flow chart a sequence of an embodiment of the described method. The prerequisite for this is that the system has a non-volatile memory, with the two variables "Counter value" and "Stored value" and a constant "Pre-Step".

In a first step 10 the system is started. The counter value is read from memory, ie the stored value, and the counter is initialized with this counter value. In a subsequent step 12 the variable stored value is calculated with counter value + pre-step and stored in the memory.

Subsequently, in one step 14 the counter value is exchanged between sender and receiver. Subsequently, in one step 16 processed the next message. The MAC is calculated via the message and the counter value and the message is transmitted. It will be in one step 18 the counter value is incremented by 1.

In a subsequent step 20 It is now checked whether the counter value is greater than or equal to the stored value. If this is the case, it takes place in one step 22 calculating the stored value equal to counter value + prestep and storing it. Then, a return to the step 16 , Will at step 20 If it is determined that the counter value is not equal to or greater than the stored value, a jump back to step is made directly 16 ,

2 shows an embodiment of the described arrangement, in total with the reference numeral 50 is designated. This arrangement includes a transmitter 52 and a receiver 54 , In the transmitter are a counter 56 and a non-volatile memory 58 provided in which counter values can be stored. Furthermore, the transmitter includes 52 an arithmetic unit 60 which calculates, based on a message to be transmitted and a counter value, a code associated with the message to the recipient 54 is sent.

In addition, in the transmitter 52 a constant value 62 stored, which is added to the counter value. The resulting sum is in the non-volatile memory 58 stored.

It should be noted that the above method has been described above in connection with the use of a counter for a MAC to ensure the freshness of messages. The application of the method goes beyond that. This relates to an implementation of a lifecycle strictly monotonic counter using a non-volatile memory, which is limited in terms of performance and the number of possible write cycles. The underlying requirement is the strict monotony of a counter, i. H. the counter values are not repeated, regardless of the specific application.

For each application, the constant value, the pre-step, can be set individually. This depends on the desired storage frequency and the average duration of the communication session.

It should also be noted that the counter value skips some values each time it is restarted, and that the initial value is always greater than the initial value of the previous restart by a multiple of the pre-step.

The presented method can be used in the use of MACs to secure critical messages on a vehicle internal bus system, such as CAN or FlexRay. Furthermore, an application in control devices, for example in motor vehicles, take place, in which the limitation of the writing cycles to the non-volatile memory, for example the non-volatile data flash, in the so-called EEPROM emulation, is an important challenge.

Claims (8)

Method of implementing a strictly monotone counter ( 56 ), wherein in a first step a sum of an initial value of the counter ( 56 ) and a constant value ( 62 ) in a memory ( 58 ) is stored as a stored value and then the counter value is incremented each time an event occurs until the counter value is equal to or greater than the stored value. Method according to Claim 1, in which, in the event that the counter value is equal to or greater than the stored value, a sum of the counter value and the constant value ( 62 ) formed in the memory ( 58 ) is stored as a stored value and then the counter value is incremented each time an event occurs until the counter value is equal to or greater than the stored value. A method according to claim 1 or 2, wherein the stored value is used as an initial value. Method according to one of claims 1 to 3, which is used to calculate a code associated with a message transmitted between a sender ( 52 ) and a receiver ( 54 ), the code being calculated taking into account the message and the counter value with the aid of a key. Method according to Claim 4, in which the message linked to the code is transmitted by the transmitter ( 52 ) to the recipient ( 54 ) is transmitted. Arrangement for providing a strictly monotone counter ( 56 ), in particular for carrying out a method according to one of claims 1 to 5, to which a counter value is assigned, which is incremented in each case when an event occurs, wherein additionally a memory ( 58 ) is provided, in which a sum of the counter value and a constant value ( 62 ) is stored as a stored value. Arrangement according to Claim 6, in which as memory ( 58 ) a non-volatile memory ( 58 ) serves. Arrangement according to claim 6 or 7, which is adapted to calculate a code for a message taking into account the counter value.

Images