GENERATOR FOR GENERATING A MESSAGE AUTHENTICATION CODE, METHOD OF GENERATING A MESSAGE AUTHENTICATION CODE, PROGRAM ELEMENT AND COMPUTER-READABLE MEDIUM

• US 20090222667A1
• Filed: 02/24/2006
• Published: 09/03/2009
• Est. Priority Date: 03/01/2005
• Status: Active Grant

• Current Assignee: NXP B.V. (NXP Semiconductors NV)
• Original Assignee: NXP B.V. (NXP Semiconductors NV)
• Inventors: Nikov, Ventzislav, Vauclair, Marc, Javier, Serret Avila
• Granted Patent: US 8,516,258 B2
• Time in Patent Office: Days
• US Class Current: 713/175
• CPC Class Codes: H04L 9/002 Countermeasures against attacks on cryptographic mechanisms network architectures or network communication protocols for protection against malicious traffic H04L63/1441
• CPC Class Codes: H04L 9/0637 Modes of operation, e.g. cipher block chaining [CBC], electronic codebook [ECB] or Galois/counter mode [GCM]
• CPC Class Codes: H04L 9/0643 Hash functions, e.g. MD5, SHA, HMAC or f9 MAC
• CPC Class Codes: H04L 9/0662 with particular pseudorandom sequence generator

Abstract

Current MAC algorithms impose a significant system performance requirement in order to process messages in real time. According to an exemplary embodiment of the present invention, a hardware implemented generator for generating a MAC is provided, that results in a significant improvement in hardware performance requirements for processing messages in real time. The engine is based on linear feedback shift registers which are adapted to generate secure MACs.

Claims

1. A generator for generating a message authentication code, the generator comprising:

a first circuit adapted for performing a delinearization of a first data set, resulting in a second data set;

wherein the first data set comprises an original code; and

wherein the delinearization is based on a linear feedback shift register construction and a pseudorandom stream.

2. The generator of claim 1, further comprising:

a second circuit adapted for performing an error detection code generation of the second data set, resulting in a third data set;

wherein the first circuit comprises a first linear feedback shift register; and

wherein the first circuit is different from the second circuit.

3. The generator of claim 1, wherein the first circuit comprises:

at least one lower weight stage;

at least one higher weight stage;

wherein the delinearization of the first data set comprises a generation of arbitrarily delayed mixed copies of the first data set that are xor-ed against the first data set;

wherein the at least one lower weight stage is adapted to ensure that an effect of each bit of the first data set propagated through all subsequent states of the first circuit;

wherein the at least one higher weight stage is jammed following a pseudorandom number sequence; and

wherein the at least one higher weight stage is driven by the pseudorandom number sequence and generates logic arbitrarily delayed subsequences of a state of the at least one lower weight stage.

4. The generator of claim 1, further comprising:

a fourth circuit comprising a first pseudorandom number generating engine adapted for performing a first pseudorandom number generation;

wherein the fourth circuit is adapted for providing the generated first pseudorandom number to the first circuit.

5. The generator of claim 4, wherein the pseudorandom number generating engine is selected from the group consisting of a combination of at least one second linear feedback shift register, a first block cipher operated in counter and a second block cipher operated in Output Feedback mode.

6. The generator of claim 5, wherein an initial state of the combination of the at least one second linear feedback shift register is chosen at random and is not reused to generate message authentication codes for more then one message;

wherein the initial state is used for performing the pseudorandom number generation.

7. The generator of claim 2, wherein the second circuit comprises a cyclic redundancy check circuit;

wherein the generation of the error detection code is based on a cyclic redundancy check construction performed by the second circuit.

8. The generator of claim 2, wherein the second circuit is selected from the group consisting of a cyclic redundancy check circuit, a cryptographic MDC function circuit, and a congruence generator.

9. The generator of claim 2, wherein the second circuit is selected from the group consisting of hashing functions used to perform efficient indexing of data and hashing functions used to perform efficient routing of networking data sets.

10. The generator of claim 2, wherein the second circuit is implemented by extracting the final state of the first circuit, using it as initial state of a self-shrinking-generator circuit and operating the self-shrinking generator circuit until output of desired size is obtained.

11. The generator of claim 2, wherein the second circuit is implemented by sampling the state of the first circuit using a resilient non-linear function which result is then feed to a cyclic redundancy check construction.

12. The generator of claim 2, wherein the second circuit is implemented by sampling the state of the first circuit using a resilient non-linear function which result is then feed to a function selected from the group consisting of hashing functions used to perform efficient indexing of data and hashing functions used to perform efficient routing of networking data sets.

13. The generator of claim 1, wherein, before performing the delinearization, the first data set is padded with at least one of a suffix and a prefix.

14. The generator of claim 4, further comprising:

a fifth circuit comprising a second pseudorandom number generating engine adapted for performing a second pseudorandom number generation;

wherein the fifth circuit is adapted for providing the generated second pseudorandom number to the first circuit.

15. The generator of claim 4, further comprising:

a third pseudorandom number generating engine adapted for performing a third pseudorandom number generation on;

wherein the first circuit comprises a fist mixing engine and a second mixing engine.

16. The generator of claim 4, further comprising a one-bit multiplexor;

wherein the first circuit comprises a FIFO register;

where the one-bit multiplexor is adapted for determining an input of the FIFO register by using a first and a second polynomial;

wherein the first pseudorandom number generating engine is adapted for controlling a selection of the first and the second polynomial.

17. The generator of claim 16, wherein the second circuit is implemented by extracting the final state of the first circuit, using it as initial state of a self-shrinking-generator circuit and operating the self-shrinking generator circuit until output of desired size is obtained.

18. The generator of claim 16, wherein the second circuit is implemented by sampling the state of the first circuit using a resilient non-linear function which result is then feed to a cyclic redundancy check construction.

19. The generator of claim 16, wherein the second circuit is implemented by sampling the state of the first circuit using a resilient non-linear function which result is then feed to a function selected from the group consisting of hashing functions used to perform efficient indexing of data and hashing functions used to perform efficient routing of networking data sets.

20. The generator of claim 4, wherein the first pseudorandom number generating engine is adapted for determining a shrinking stream.

21. A method of generating a message authentication code, the method comprising the following step:

performing a delinearization of a first data set by a first circuit, resulting in a second data set;

wherein the first data set comprises an original code;

wherein the delinearization is based on a linear feedback shift register construction and a pseudorandom stream.

22. The method of claim 21, further comprising the steps of:

performing an error detection code generation of the second data set by a second circuit, resulting in a third data set;

wherein the first circuit comprises a first linear feedback shift register;

wherein the first circuit is different from the second circuit.

23. The method of claim 21, further comprising the step of:

performing a pseudorandom number generation by a fourth circuit comprising a pseudorandom number generating engine;

providing the generated pseudorandom number to the first circuit.

24. The method of claim 21, wherein the second circuit is implemented by performing an non-linear function on the state of the first circuit and feeding the result into a cyclic redundancy check

25. The method of claim 21, wherein the second circuit is implemented by performing an non-linear function on the state of the first circuit and feeding the result into a function selected from the group consisting of hashing functions used to perform efficient indexing of data and hashing functions used to perform efficient routing of networking data sets.

26. The method of claim 21, wherein the second circuit is implemented by extracting the state of the first circuit, using it as initial state of a self-shrinking-generator circuit and operating the self-shrinking generator circuit until an output of the desired size is obtained.

27. Program element of generating a message authentication code, which, when being executed by a processor, is adapted to carry out the step of:

performing a delinearization of a first data set by a first circuit, resulting in a second data set;

wherein the first data set comprises an original code;

wherein the delinearization is based on a linear feedback shift register construction and a pseudorandom stream.

28. Computer-readable medium in which a computer program of generating a message authentication code is stored, which, when being executed by a processors, is adapted to carry out the step of:

performing a delinearization of a first data set by a first circuit, resulting in a second data set;

wherein the first data set comprises an original code;

wherein the delinearization is based on a linear feedback shift register construction and a pseudorandom stream.