Technical background and details

This is a collection of random notes and thoughts from the original development process. Much may be rambling. Information herein was not validated before release, and errors are likely.

Background and Primary Research Paper

The Usenix security conference 2013 was going to have a presentation documenting the internals fully (as well as crytpanalysis). This disclosure was delayed for two years. When it was released, the paper omitted a non-linear output filter function at definition 3.8.

This omitted function takes a 20-bit input, and returns a single bit.

All other details of the cipher appeared to have been fully disclosed (even if some errors existed). The largest error is that text description of the successor function for g register was incorrect. However, the diagram version showed the correct operation.

Variable and notations used

Common variables

• K ==> a 96-bit shared key, known to both vehicle and transponder
• N ==> a 56-bit nonce value, generated by the vehicle, and sent in cleartext to the transponder
• Aᵥ ==> a 28-bit authenticator value generated by a reader (often a vehicle), and sent in cleartext to the tag. (aka frn)
• Aₜ ==> a 20-bit authenticator value generated by a tag and sent in cleartext to the reader (aka grn)
• frn ==> an alternate name for Aᵥ
• grn ==> an alternate name for Aₜ
• g ==> a 23-bit Galois linear feedback shift register
• h ==> a 13-bit non-linear feedback shift register
• l ==> a 7-bit feedback register
• m ==> a 7-bit feedback register
• r ==> a 7-bit feedback register
• sₙ ==> a 57-bit internal state of the cipher === <g, h, l, m, r>
• Copy

       at iteration `n` (where `0 ≤ n ≤ 55`)
  

• s₀ ==> cipher initial state

Notation and Symbols

For our purposes, the finite field F will always refer to a binary finite field (each element ∈ {0,1}). Thus, as is useful for current computers, we can treat these as bitstrings.

Notation Examples:

If the value is stored in Given:

• x⁸ = 00000011

Then:

• x⁸ === x₇ · x₆ · x₅ · x₄ · x₃ · x₂ · x₁ · x₀
• x[7..4] = 0000
• x[3..0] = 0011
• x[2..1] = 01

Cipher data dependencies

Cipher Initial State s0 - Data Dependencies

Evaluating the bits that influence the initial state, s₀₀, as described in section 3.5:

p ==> 56-bit value, depends only on N and K[95..40] q ==> 44-bit value, depends only on p t ==> 43-bit value, depends only on q

Thus, all three of those variables depend only upon N and K[95..40].

Notably, the input i to the successor function for g is hard-coded to zero for the initialization.

As reproduced below, the full initial state is shown to depend only on three variables (p, q, t):

g : t(0..22)
h : 0 · p(0..11)
l : t(23..29)
m : t(30..36)
r : t(37..42) · q(43)

Therefore, s₀₀ depends only on N and K[95..40]. Stated differently, the low 40 bits of key K (aka K[39..0]) have no effect on the calculation of s₀₀.

Challenging the assumptions

Generally, K remains constant, and N is a random value generated by the reader. It appears these presumptions were accepted as always true in the creation of this cipher.

However, the value of N can be fully controlled during research, including choosing to make N constant. Moreover, with a writable tag, K can be modified to have specific relationships with known-good authentication traces. Taken together, these properties will (as to be described later) enable recovery of an equivalent to the output filter function.

As noted earlier, the initial cipher state s₀₀ depends only upon K[95..40] and N.

Therefore, if N is held constant, then the the initial cipher state s₀₀ will depend solely upon K[95..40]. Put another way, this means that all keys which share the most significant 56 bits (or differ only in the least significant 40 bits) will share the same initial state s₀₀.

Cipher State sₙ - Data Dependencies

NOTE: This has utility (value) when K is known, even when the mapping of the output filter function is not yet known for all 2²⁰ potential inputs.

TLDR: With a fixed N...

• s₀ <-- K[40..95]
• s₁ <-- K[39..95]
• s₂ <-- K[38..95]
• sₙ <-- s(N-1) + K[40-N]
• sₙ <-- K[(40-N)..95]

K₃₉..K₀₀ to output bits

Here's an exhaustive table that maps which bit of the key influences a given output bit. Start state + key bit --> output

Branching ... from one trace to millions

Given the ability to control the nonce N, and in particular to use a constant N, it becomes possible to generate many valid authentication sequences (with different keys) from just a single valid authentication with a known key.

Trivially getting 31 more traces

With a static nonce value, an astute observer may have noticed that frn does not rely on the least significant five bits of the key ... those bits influence grn₀₀..grn₀₄.

Therefore, so long as the only bits of K that differ are K₀₄..K₀₀, the frn value will remain constant for a given nonce.

This allows a single known-good key + nonce + frn to be trivially expanded to 32x known-good sets, for "nearby" consecutive keys. Another way to state this is that each block of 32 consecutive keys will share the same Aᵥ value.

More formally, where (K' ^ K) <= 0x1F, then Aᵥ' = Aᵥ.

REM using the key and auth values from the research paper
lf em 4x70 setkey --key A090A0A02080000000000000
REM expect a tag response of `60 9D 6`
lf em 4x70 auth --rnd 3FFE1FB6CC513F --frn F355F1A0
REM repeat using 31 additional keys in the same "block"
lf em 4x70 setkey --key A090A0A02080000000000001
lf em 4x70 auth --rnd 3FFE1FB6CC513F --frn F355F1A0
lf em 4x70 setkey --key A090A0A02080000000000002
lf em 4x70 auth --rnd 3FFE1FB6CC513F --frn F355F1A0
lf em 4x70 setkey --key A090A0A02080000000000003
lf em 4x70 auth --rnd 3FFE1FB6CC513F --frn F355F1A0
REM ... and so on, for a total of 31 more keys
lf em 4x70 setkey --key A090A0A0208000000000001E
lf em 4x70 auth --rnd 3FFE1FB6CC513F --frn F355F1A0
lf em 4x70 setkey --key A090A0A0208000000000001F
lf em 4x70 auth --rnd 3FFE1FB6CC513F --frn F355F1A0

The tag will respond to all 32 authentications, although its grn responses may differ for each key.

Moving one bit further...

Walking the sequence backwards one additional bit, where the last six bits of the key change, what happens to Aᵥ?

It turns out that Aᵥ will either remain identical, or that the least significant bit of Aᵥ will flip. Thus, there are exactly two possible values that need to be tested for Aᵥ, and the tag will respond to exactly one of them.

Formally, where (K' ^ K) <= 0x3F, then Aᵥ' ^ Aᵥ <= 0x1.

REM using the key and auth values from the research paper
lf em 4x70 setkey --key A090A0A02080000000000000
REM expect a tag response of `60 9D 6`
lf em 4x70 auth --rnd 3FFE1FB6CC513F --frn F355F1A0
REM repeat using 31 additional keys in the same "block"
lf em 4x70 setkey --key A090A0A02080000000000020
REM 50% chance that this is the correct FRN value
lf em 4x70 auth --rnd 3FFE1FB6CC513F --frn F355F1A0
REM 50% chance that this is the correct FRN value
lf em 4x70 auth --rnd 3FFE1FB6CC513F --frn F355F1B0

Expanding further...

Each additional bit of the key that is changed will double the number of Aᵥ values that need to be tested to find the correct challenge.

Using K'' == K ^ 0x1FF (nine lowest bits changed), requires testing only 16 possible Aᵥ'' values, by permuting the least significant bits of Aᵥ.

Thus, exactly one of the following should result in a successful authentication:

REM modify the key's lowest nine bits
lf em 4x70 setkey --key A090A0A02080000000000100
REM 1/16 chance for each of these to work:
lf em 4x70 auth --rnd 3FFE1FB6CC513F --frn F355F100
lf em 4x70 auth --rnd 3FFE1FB6CC513F --frn F355F110
lf em 4x70 auth --rnd 3FFE1FB6CC513F --frn F355F120
lf em 4x70 auth --rnd 3FFE1FB6CC513F --frn F355F130
lf em 4x70 auth --rnd 3FFE1FB6CC513F --frn F355F140
lf em 4x70 auth --rnd 3FFE1FB6CC513F --frn F355F150
lf em 4x70 auth --rnd 3FFE1FB6CC513F --frn F355F160
lf em 4x70 auth --rnd 3FFE1FB6CC513F --frn F355F170
lf em 4x70 auth --rnd 3FFE1FB6CC513F --frn F355F180
lf em 4x70 auth --rnd 3FFE1FB6CC513F --frn F355F190
lf em 4x70 auth --rnd 3FFE1FB6CC513F --frn F355F1A0
lf em 4x70 auth --rnd 3FFE1FB6CC513F --frn F355F1B0
lf em 4x70 auth --rnd 3FFE1FB6CC513F --frn F355F1C0
lf em 4x70 auth --rnd 3FFE1FB6CC513F --frn F355F1D0
lf em 4x70 auth --rnd 3FFE1FB6CC513F --frn F355F1E0
lf em 4x70 auth --rnd 3FFE1FB6CC513F --frn F355F1F0
REM hint: response will be `65 09 A`

Table of search space per key change

Depending on the most significant bit that changed in the key, it can be trivially calculated how many variations of Aᵥ need to be tested to find the correct challenge for that same nonce.

Branching of keys

Thus, it becomes almost trivial to generate millions of valid authentication sequences for a given nonce, frn, and K' ~= K. Each of these authentication sequences has the potential to generate at least twenty distinct internal cipher states from Aₜ.

While trivial, this takes time. Millions of traces were generated over the course of multiple months using multiple PM3 Easy devices 24/7, each one writing keys and brute-forcing the frn values.

Creating equivalent to the "Output Filter Function"

While the mechanics and computation of the output filter function is not known, the inputs are defined in Definition 3.9, and the output is a single bit.

Therefore, if the entire cipher except for the internal computations of the output filter are known, given a known valid authentication trace, all twenty of the input bits passed to the output filter function can be calculated for each of the 48 output bits (Aᵥ and Aₜ).

When using branched traces (from above), the first 36 internal cipher states (give or take) are shared, and thus do not provide "new" information. This still provides up to 12 bits of "new" information per trace, or up to ~192 bits of "new" information per block of 32 consecutive keys that share the same frn value.

Treating the 20-bit parameter as an index to a bitmap, the full mapping requires only a 128k bitmap. Initially, when there remain unknown mappings, a second 128k bitmap is used to tracks if the output bit for that 20-bit parameter has already been found.

As the table become more filled, it becomes easier to generate new authentication sequences using entirely random values for N and K, especially where the most significant bits of frn are known. Thus, the brute force space for key branching never becomes overwhelmingly large.

As an exercise for the reader, and as it is important to finish filling the last values in the table, an astute reader can realize optimizations that improve finding a "targeted" 20-bit input, especially where the cipher states from current branching had been archived.

In summary, these traces can thus be used to (slowly) fill in a 128k bitmap indicating all possible output values for any of the 2²⁰ inputs, without ever needing to replicate or know the internal functioning of the output filter function.

Which bits of K ....

Given a static value for N, what bits in K influence a given output bit?

128k table ... too large to fit in IoT flash memory

Although too large to fit, there are various two-level (boolean) logic reduction techniques that can migrate from a truth table (e.g., the bitmap) to a reduced set of logical operations that will obtain the same result. (ref: Espresso)

With the 128k bitmap converted to a truth table, a much more reduced set of tables was found to generate the same results. There is no assurance that this is the most optimal way to generate the results, but it is an acceptably small solution ... small enough to even be implemented in FPGA logic if desired.

Appendix of random notes (not organized)

EM4x70 Chip Memory Layout

There are sixteen (16x) blocks of memory, each storing a 16-bit value. Blocks may be protected (P column) as read-only (RO) or write-only (WO). Lock₀ === Disable writing ... (?) write-prevention when set to 1. Lock₁ === Pin-code lock

Vehicle authentication value - Data dependency

Given:

• An EM4x70 (ID48) Transponder with a writable key
• The output filter OF(X²⁰) -> r¹ function is a black box:
  • The internal workings are not, themselves, known
  • The 20-bit input for the output filter function OF(X²⁰) can be calculated for s₀..s₅₄, given only N and K
• Exists a bitmap OF_Known[2²⁰] (128kb) indicating if, for a given 20-bit input, the result r¹ is known
  • Initially, this is all set to zero (false).
• Exists a bitmap OF_Result[2²⁰] (128kb) indicating, for a given 20-bit input, a known result r¹.
  • Values are valid only when corresponding bit in OF_Known is set to one (true)

The, starting with a single known valid trace: K + [ N, Aᵥ, Aₜ]:

1. The starting valid trace fills in ~48 entries in OF_Known/OF_Result
2. By cycling through all K'' having the same upper 91 bits, 31 additional traces [K'', N, Aᵥ] are trivially created. Each K'' will share the first 28 output bits (Aᵥ is the same), but have potentially 20 more unique internal states. a. 31 instances x 20 bits per instance == 620 more potential entries b. Subtotal: 668 entries known (0.06%)
3. By cycling through all K' having the same upper 80 bits, with least significant 5 bits set to zero: a. Brute-forcing the required value of N' takes at most 512 attempts because N(55..9) = N'(55..9). b. On average, this takes 256 attempts. b. As above, all other 31 values for K'' will use the same N', allowing 668 additional output values to be potentially filled
4. Over time, OF_Known will trend towards being mostly populated

more random thoughts

Can leave multiple pm3 running 24/7, logging results.

Note that the initial state S₀ is also known (for that nonce) for ALL OTHER 2^40 keys that share the same bits in K[95..40]. (!!!)

earliest notes on branching technique

Similar to Partial Key-Update Aₜtack, for creating mapping of the output filter function OF( x²⁰ ) --> bool

Given:

• Known private key K

• Known working data: { Nonce[55..0] , AuthV[27..0], AuthT²⁰ }

• ID48 Transponder with Rewritable Key

• Output bit does not alter any other cryptographic state

• s₀ depends ONLY on { N, K[40..95] }

• sₙ depends ONLY on s(N-1) and K(40-N) --> { N, K[(40-N)..95] }

• s₀ depends ONLY on --> { N, K[40..95] }

• s₁ --> { N, K[39..95] }

• s₂ --> { N, K[38..95] }

• s₃ --> { N, K[37..95] }

• s₄ --> { N, K[36..95] }

• s₅ --> { N, K[35..95] }

• s₆ --> { N, K[34..95] }

• s₇ Aᵥ₂₇ --> { N, K[33..95] }

• s₈ Aᵥ₂₆ --> { N, K[32..95] }

• s₉ Aᵥ₂₅ --> { N, K[31..95] }

• s₁₀ Aᵥ₂₄ --> { N, K[30..95] }

• s₁₁ Aᵥ₂₃ --> { N, K[29..95] }

• s₁₂ Aᵥ₂₂ --> { N, K[28..95] }

• s₁₃ Aᵥ₂₁ --> { N, K[27..95] }

• s₁₄ Aᵥ₂₀ --> { N, K[26..95] }

• s₁₅ Aᵥ₁₉ --> { N, K[25..95] }

• s₁₆ Aᵥ₁₈ --> { N, K[24..95] }

• s₁₇ Aᵥ₁₇ --> { N, K[23..95] }

• s₁₈ Aᵥ₁₆ --> { N, K[22..95] }

• s₁₉ Aᵥ₁₅ --> { N, K[21..95] }

• s₂₀ Aᵥ₁₄ --> { N, K[20..95] }

• s₂₁ Aᵥ₁₃ --> { N, K[19..95] }

• s₂₂ Aᵥ₁₂ --> { N, K[18..95] }

• s₂₃ Aᵥ₁₁ --> { N, K[17..95] }

• s₂₄ Aᵥ₁₀ --> { N, K[16..95] }

• s₂₅ Aᵥ₉ --> { N, K[15..95] }

• s₂₆ Aᵥ₈ --> { N, K[14..95] }

• s₂₇ Aᵥ₇ --> { N, K[13..95] }

• s₂₈ Aᵥ₆ --> { N, K[12..95] }

• s₂₉ Aᵥ₅ --> { N, K[11..95] }

• s₃₀ Aᵥ₄ --> { N, K[10..95] }

• s₃₁ Aᵥ₃ --> { N, K[ 9..95] }

• s₃₂ Aᵥ₂ --> { N, K[ 8..95] }

• s₃₃ Aᵥ₁ --> { N, K[ 7..95] }

• s₃₄ Aᵥ₀ --> { N, K[ 6..95] }

Therefore, if we write K' to a second transponder, where K' == K ^ 0x20 (flip bit 6) then Aᵥ' == Aᵥ[27..1] + one random bit

Therefore, by carefully selecting derived keys to be written to transponders, it becomes trivial to generate many successful authentication traces.

Example: Known valid trace: [ K, N, Aᵥ ] == [ F32AA98CF5BE4ADFA6D3480B, 45F54ADA252AAC, 4866BB70 ] --> 9B D1 80

[ K', N, Aᵥ' ] == [ F32AA98CF5BE4ADFA6D3482B, 45F54ADA252AAC, 4866BB60 ] --> Fail [ K', N, Aᵥ' ] == [ F32AA98CF5BE4ADFA6D3482B, 45F54ADA252AAC, 4866BB70 ] --> 4E BB D0

[ K', N, Aᵥ' ] == [ F32AA98CF5BE4ADFA6D3486B, 45F54ADA252AAC, 4866BB40 ] --> Fail [ K', N, Aᵥ' ] == [ F32AA98CF5BE4ADFA6D3486B, 45F54ADA252AAC, 4866BB50 ] --> Fail [ K', N, Aᵥ' ] == [ F32AA98CF5BE4ADFA6D3486B, 45F54ADA252AAC, 4866BB60 ] --> Fail [ K', N, Aᵥ' ] == [ F32AA98CF5BE4ADFA6D3486B, 45F54ADA252AAC, 4866BB70 ] --> 39 55 90

[ K', N, Aᵥ' ] == [ F32AA98CF5BE4ADFA6D3484B, 45F54ADA252AAC, 4866BB60 ] --> Fail [ K', N, Aᵥ' ] == [ F32AA98CF5BE4ADFA6D3484B, 45F54ADA252AAC, 4866BB70 ] --> E8 60 D0

[ K', N, Aᵥ' ] == [ F32AA98CF5BE4ADFA6D348DB, 45F54ADA252AAC, 4866BB70 ] --> Fail [ K', N, Aᵥ' ] == [ F32AA98CF5BE4ADFA6D348DB, 45F54ADA252AAC, 4866BB60 ] --> Fail [ K', N, Aᵥ' ] == [ F32AA98CF5BE4ADFA6D348DB, 45F54ADA252AAC, 4866BB50 ] --> Fail [ K', N, Aᵥ' ] == [ F32AA98CF5BE4ADFA6D348DB, 45F54ADA252AAC, 4866BB40 ] --> Fail [ K', N, Aᵥ' ] == [ F32AA98CF5BE4ADFA6D348DB, 45F54ADA252AAC, 4866BB30 ] --> Fail [ K', N, Aᵥ' ] == [ F32AA98CF5BE4ADFA6D348DB, 45F54ADA252AAC, 4866BB20 ] --> Fail [ K', N, Aᵥ' ] == [ F32AA98CF5BE4ADFA6D348DB, 45F54ADA252AAC, 4866BB10 ] --> ED 9C 20 [ K', N, Aᵥ' ] == [ F32AA98CF5BE4ADFA6D348DB, 45F54ADA252AAC, 4866BB00 ] --> Fail

This has been CONFIRMED WORKING using actual hardware.

See https://github.com/dorssel/usbipd-win/wiki/Automation#json

This can avoid having to swap to Windows to re-connect if the device disconnects/reconnects for any reason.

Branching Logic

Function ExpandBy32() takes as input:

• 96-bit private key K
• 56-bit nonce N
• 28-bit valid vehicle auth Aᵥ

Step 1. Write the private key K Step 2. Validate authentication works with N and Aᵥ Step 3. Set lowest 5 bits of K to zero Step 4. For i in (0..31): 4a. Set temporary key K' as K+i (set some of lowest 5 bits) 4b. Write private key K' 4c. Validate authentication works with N and Aᵥ 4d. Verify received 20-bit response, Aₜ 4e. For each success, print the set: { K', N, Aᵥ, Aₜ }

Function Branch() takes as input:

• 96-bit private key K
• 56-bit nonce N
• 28-bit valid vehicle auth Aᵥ (just A in below)

VERIFY VALID INPUTS:

• Write the private key
• Validate authentication works with N and Aᵥ

Then (using 2^16) potential authentications as maximum Select a target key K', where K'[95..()]

This is when the private key IS already known, and you have a starting point.

My vehicle

My 2004 Volvo S60 key originally had a pin code of 'AAAAAAAA'.

Updating the pin code:

1. Get info: In this example, block 1 data == ED08, (0b1110...)

   lf em 4x70 info

2. Because Lockbit 0 was set, unlock with the PIN:

   lf em 4x70 unlock --pin AAAAAAAA

3. Verify successful unlock by checking LockBit0: In this example, block 1 data == AD08, (0b1010...) so LockBit1 = 1, LockBit0 = 0 == success.

   lf em 4x70 info

4. Write the new pin code as DEADBEEF

   lf em 4x70 setpin --pin DEADBEEF

5. Set lockbit0 to 1 (based on existing data in block1): e.g, AD08 | 4000 == ED08

   lf em 4x70 write --block 1 --data ED08

[=] ------+----------+----------------------------- [=] 3 | xx xx | ID (redacted) [=] 2 | xx xx | ID (redacted) [=] ------+----------+----------------------------- [=] 1 | ED 08 | UM1 [=] 0 | 87 7D | UM1 [=] ------+----------+----------------------------- [=] [=] Tag ID: DB 4F B2 E8 [=] Lockbit 0: 1 [=] Lockbit 1: 1 [=] Tag is LOCKED.

Demodulating the traces

To be written. Generally, save as WAV file, and then use more powerful tools than the data viewer that is built into PM3 client.

fancy characters

Symbols, subscripts, superscripts...

X₀₁₂₃₄₅₆₇₈₉₊₋₌₍₎ₐₑₒₓₔₕₖₗₘₙₚₛₜⱼᵢᵣᵤᵥᵦᵧᵨᵩᵪ.
X⁰¹²³⁴⁵⁶⁷⁸⁹⁺⁻⁼⁽⁾ⁿⁱ
⊕εx̄∧∨