Method and apparatus for nonlinear IV setup in keystream generators
View Patent ↗The invention concerns the contact-less technology MIFARE, and describes a method to update a state by injecting an IV using a non-linear feedback shift register that makes use of only look-up tables and basic operations on 8-bit words.
1. A method to perform a “reader challenge setup step in an authentication phase”, according to MIFARE contact-less technology authentication and encryption protocol, in a “tag device”, wherein, a size of an internal state of a cipher, called “ST” is 6 bytes, at time t, the internal state of the cipher is represented by ST t =(ST t [0], . . . , ST t [5]), a reader challenge, called “RC “, of length 4 bytes, is denoted by: RC=(RC[0], RC[3]) a linear function “LF” performing a linear feedback function of a MIFARE contact-less technology linear feedback shift register, and a non linear function, “NLF”, performing a MIFARE contact-less technology two-layer filter generator, are used to update a value of said ST using the RC,
wherein the method comprises at least the following steps:
storing, in a memory of said tag device, four tables f1i, f1p, f2i, f2p;
from an initial state of the reader challenge setup step denoted by ST to' , computing by a processor of said tag device, the successive states ST t0+8 , ST t0+16 , ST t0+24 , ST t0+32 by computing byte per byte a linear feedback value using the function LF; and
injecting, by said tag device, byte per byte the “RC” into the ST using said four tables f1i, f1p, f2i, f2p and the function NLF.
2. The method according to claim 1 wherein said method comprises a preliminary step of arrangement of “ST” bits in byte to store, in one nibble the bits with a pair ranking, and in the other nibble the bits with an impair ranking.
3. The method according to claim 1 wherein, said linear feedback function is defined using 6 8-bit×8-bit pre-computed tables L 0 , . . . , L 5 such that:
LF ( ST 8t+i[ 0], . . . , ST 8t+i[ 5])= L 5 [ST 8t+i[ 5]]⊕ L 4 [ST 8t+i[ 4]]⊕ . . . ⊕ L 0 [ST 8t+i [0]].
4. The method according to claim 3 wherein, said “NLF ” function is defined by:
an 8-bit size register, called “Buff' which is initialized or updated using the linear function LF applied on ST and one byte of RC
the four tables f1i, f1p, f2i, f2p, which are 8-bit ×8-bit pre-computed tables, are applied on the state ST
one function “Ga”, applied on four byte values “a”, “b”, “c” and “d” and producing a one byte value:
Ga ( a, b, c, d )=((( a^d ) & ( a^b^ )( b & c )))^0xFF^ d )
one function “Gb”, applied on four byte values “a”, “b”, “c” and “d” and producing a one byte value such as:
Gb ( a, b, c, d )=(( a^ ( b & d )) & ( c^a )^( a & d ))
one function “G” that receive the outputs of said functions Ga, Gb and two byte values, denoted by U and V that are initialized with bits from said ST, two byte values, denoted by UU and VV that are initialized with bits from said ST and possibly with bits from said Buff, these values UU and VV are updated using 8 steps before the final update of the register Buff and the register Buff
when all bits of said register Buff are computed, the first byte of said ST is trashed, all the other bytes are left shifted, and the register Buff is insert as sixth rank.
5. The method according to claim 4 wherein, said register “Buff” contains the current byte of the RC to compute, xored with the byte provided by said linear function “LF”.