Generator for generating a message authentication code, method of generating a message authentication code, program element and computer-readable medium

• US 8,516,258 B2
• Filed: 02/24/2006
• Issued: 08/20/2013
• 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: Vauclair, Marc, Javier, Serret Avila, Nikov, Ventzislav
• Primary Examiner(s): Mehedi, Morshed
• Application Number:
  US11/817,783
• Publication Number:
  US 20090222667A1
• Time in Patent Office: 2,734 Days
• Field of Search: 713/175, 380/40, 380/46
• 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 (MAC), the generator comprising:

a first circuit that performs a delinearization of a first data set, resulting in a second data set, wherein the first data set comprises a plain text and the first circuit further comprises;

a first pseudorandom number generator; and

a central plain text mixer, implemented by a load-controlled first linear feedback shift register (LFSR), that generates arbitrarily delayed mixed copies of the plain text;

an error detection circuit that detects errors in the second data set, resulting in a third data set; and

wherein the error detection circuit is implemented by sampling a state of the first circuit using a resilient non-linear function and feeding results from the sampling to perform efficient indexing of data and efficient routing of networking data sets.

2. The generator of claim 1, wherein the first pseudorandom number generator is a second LFSR.

3. The generator of claim 2, wherein an initial state of the second LFSR is chosen at random and is not reused to generate MACs for more then one message, and the initial state is used for performing the pseudorandom number generation.

4. The generator of claim 1, wherein the error detection circuit comprises a cyclic redundancy check (CRC) circuit.

5. The generator of claim 1, wherein the error detection circuit is a cryptographic Modification Detection Code (MDC) function circuit.

6. The generator of claim 1, wherein the error detection circuit provides efficient indexing of data and efficient routing of networking data sets.

7. The generator of claim 1, wherein the error detection circuit is implemented by extracting a final state of the first circuit, using the extracted final state as an initial state of a self-shrinking-generator circuit, and operating the self-shrinking generator circuit until output of desired size is obtained.

8. The generator of claim 1, wherein the error detection circuit is implemented by sampling a state of the first circuit using a resilient non-linear function and feeding results from the sampling to a CRC circuit.

9. 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.

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

a second pseudorandom number generator.

11. The generator of claim 10, wherein the first circuit further comprises:

a third pseudorandom number generator;

a first mixing engine; and

a second mixing engine.

12. The generator of claim 1, further comprising:

a one-bit multiplexer, wherein the first circuit further comprises a FIFO register, the one-bit multiplexer determines an input of the FIFO register by using a first polynomial and a second polynomial, and the first pseudorandom number generator controls a selection of the first polynomial and the second polynomial.

13. The generator of claim 12, wherein the error detection is implemented by extracting a final state of the first circuit, using the extracted final state as an initial state of a self-shrinking-generator circuit, and operating the self-shrinking generator circuit until output of desired size is obtained.

14. The generator of claim 12, wherein the error detection is implemented by sampling a state of the first circuit using a resilient non-linear function and feeding results from the sampling to a CRC circuit.

15. The generator of claim 12, wherein the error detection circuit is implemented by sampling a state of the first circuit using a resilient non-linear function and feeding results from the sampling to perform efficient indexing of data and efficient routing of networking data sets.

16. The generator of claim 1, wherein the first pseudorandom number generator determines a shrinking stream.

17. A generator for generating a message authentication code (MAC), the generator comprising:

a first circuit that performs a delinearization of a first data set, resulting in a second data set, wherein the first data set comprises a plain text and the first circuit further comprises;

a first pseudorandom number generator; and

a central plain text mixer, implemented by a load-controlled first linear feedback shift register (LFSR), that generates arbitrarily delayed mixed copies of the plain text;

wherein the central plain text mixer further comprises;

a lower weight stage; and

a higher weight stage, wherein the delinearization of the first data set further comprises a generation of arbitrarily delayed mixed copies of the first data set that are xor-ed against the first data set, the lower weight stage ensures that an effect of each bit of the first data set propagates through all subsequent states of the central plain text mixer, a pseudorandom number sequence jams the higher weight stage, drives the higher weight stage and generates arbitrarily delayed subsequences of a state of the lower weight stage.

18. A method of generating a message authentication code (MAC), the method comprising:

generating a first pseudonumber with a first pseudorandom number generator;

transmitting the generated pseudonumber to a central plain text mixer, wherein the central plain text mixer comprises a load- controlled linear feedback shift register (LFSR);

performing a delinearization of a first data set at delayed random positions in the central plain text mixer based upon the generated pseudonumber to produce a second data set;

detecting errors in the second data set using an error detection circuit, resulting in a third data set; and

wherein the error detection circuit is implemented by sampling a state of the first circuit using a resilient non-linear function and feeding results from the sampling to perform efficient indexing of data and efficient routing of networking data sets.

19. The method of claim 18, further comprising:

performing an error detection for the second data set, resulting in a third data set.

20. The method of claim 18, further comprising:

generating a second pseudonumber with a second pseudorandom number generator.

21. The method of claim 18, further comprising:

performing a non-linear function on the second data set and feeding the result into a cyclic redundancy check (CRC) circuit.

22. The method of claim 19, further comprising:

performing a non-linear function on the second data set;

performing efficient indexing of data; and

performing efficient routing of networking data sets.

23. The method of claim 19, further comprising:

extracting the second data set;

using the extracted second data set as an initial state of a self-shrinking-generator circuit; and

operating the self-shrinking generator circuit until an output of the desired size is obtained.

24. A non-transitory computer-readable medium in which a computer program for generating a message authentication code (MAC) is stored, which, when being executed by processors, is adapted to:

generate a first pseudonumber with a first pseudorandom number generator;

transmit the generated pseudonumber to central plain text mixer, wherein the central plain text mixer comprises a load-controlled linear feedback shift register (LFSR);

perform a delinearization of a first data set at delayed random positions in the central plain text mixer based upon the generated pseudorandom to produce a second data set;

detecting errors in the second data set using an error detection circuit, resulting in a third data set; and

wherein the error detection circuit is implemented by sampling a state of the first circuit using a resilient non-linear function and feeding results from the sampling to perform efficient indexing of data and efficient routing of networking data sets.