RRG-Proxmark3/client/deps/id48/TECHNICAL.md

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>

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

Symbol	Meaning
^	bitwise exclusive-or (XOR); the paper used ⊕
ε	the empty bitstring
0ⁿ	bitstring of n zero-bits
xⁿ	a bitstring of length n
x₀	the first bit of a bitstring
xᵢ	the ith bit of a bitstring xⁿ (where i<n)
xₙ₋₁	the last bit of a bitstring xⁿ
xₙ	the nth bit of the bitstring xꟲ (where C>n)
x·y	concatenation of bitstrings x and y
~x	bitwise complement of bitstring x (paper uses x̄)
&&	logical AND (conjunction) (research paper uses ∧)
`
x[i..j]	The contiguous bits of x from subscript i to j

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

Start state	Key bit	Output
s₀₀	K₃₉	<< hidden >>
s₀₁	K₃₈	<< hidden >>
s₀₂	K₃₇	<< hidden >>
s₀₃	K₃₆	<< hidden >>
s₀₄	K₃₅	<< hidden >>
s₀₅	K₃₄	<< hidden >>
s₀₆	K₃₃	<< hidden >>
s₀₇	K₃₂	O₀₀ == frn₀₀
s₀₈	K₃₁	O₀₁ == frn₀₁
s₀₉	K₃₀	O₀₂ == frn₀₂
s₁₀	K₂₉	O₀₃ == frn₀₃
s₁₁	K₂₈	O₀₄ == frn₀₄
s₁₂	K₂₇	O₀₅ == frn₀₅
s₁₃	K₂₆	O₀₆ == frn₀₆
s₁₄	K₂₅	O₀₇ == frn₀₇
s₁₅	K₂₄	O₀₈ == frn₀₈
s₁₆	K₂₃	O₀₉ == frn₀₉
s₁₇	K₂₂	O₁₀ == frn₁₀
s₁₈	K₂₁	O₁₁ == frn₁₁
s₁₉	K₂₀	O₁₂ == frn₁₂
s₂₀	K₁₉	O₁₃ == frn₁₃
s₂₁	K₁₈	O₁₄ == frn₁₄
s₂₂	K₁₇	O₁₅ == frn₁₅
s₂₃	K₁₆	O₁₆ == frn₁₆
s₂₄	K₁₅	O₁₇ == frn₁₇
s₂₅	K₁₄	O₁₈ == frn₁₈
s₂₆	K₁₃	O₁₉ == frn₁₉
s₂₇	K₁₂	O₂₀ == frn₂₀
s₂₈	K₁₁	O₂₁ == frn₂₁
s₂₉	K₁₀	O₂₂ == frn₂₂
s₃₀	K₀₉	O₂₃ == frn₂₃
s₃₁	K₀₈	O₂₄ == frn₂₄
s₃₂	K₀₇	O₂₅ == frn₂₅
s₃₃	K₀₆	O₂₆ == frn₂₆
s₃₄	K₀₅	O₂₇ == frn₂₇
s₃₅	K₀₄	O₂₈ == grn₀₀
s₃₆	K₀₃	O₂₉ == grn₀₁
s₃₇	K₀₂	O₃₀ == grn₀₂
s₃₈	K₀₁	O₃₁ == grn₀₃
s₃₉	K₀₀	O₃₂ == grn₀₄
s₄₀	0₁₄	O₃₃ == grn₀₅
s₄₁	0₁₃	O₃₄ == grn₀₆
s₄₂	0₁₂	O₃₅ == grn₀₇
s₄₃	0₁₁	O₃₆ == grn₀₈
s₄₄	0₁₀	O₃₇ == grn₀₉
s₄₅	0₀₉	O₃₈ == grn₁₀
s₄₆	0₀₈	O₃₉ == grn₁₁
s₄₇	0₀₇	O₄₀ == grn₁₂
s₄₈	0₀₆	O₄₁ == grn₁₃
s₄₉	0₀₅	O₄₂ == grn₁₄
s₅₀	0₀₄	O₄₃ == grn₁₅
s₅₁	0₀₃	O₄₄ == grn₁₆
s₅₂	0₀₂	O₄₅ == grn₁₇
s₅₃	0₀₁	O₄₆ == grn₁₈
s₅₄	0₀₀	O₄₇ == grn₁₉

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.

msb changed	key bits changed mask	Values to test	2^N
0	0x00'0000'0000	1	0
1	0x00'0000'0001	1	0
2	0x00'0000'0003	1	0
3	0x00'0000'0007	1	0
4	0x00'0000'000F	1	0
5	0x00'0000'001F	1	0
6	0x00'0000'003F	2	1
7	0x00'0000'007F	4	2
8	0x00'0000'00FF	8	3
9	0x00'0000'01FF	16	4
10	0x00'0000'03FF	32	5
11	0x00'0000'07FF	64	6
12	0x00'0000'0FFF	128	7
13	0x00'0000'1FFF	256	8
14	0x00'0000'3FFF	512	9
15	0x00'0000'7FFF	1,024	10
16	0x00'0000'FFFF	2,048	11
17	0x00'0001'FFFF	4,096	12
18	0x00'0003'FFFF	8,192	13
19	0x00'0007'FFFF	16,384	14
20	0x00'000F'FFFF	32,768	15
21	0x00'001F'FFFF	65,536	16
22	0x00'003F'FFFF	131,072	17
23	0x00'007F'FFFF	262,144	18
24	0x00'00FF'FFFF	524,288	19
25	0x00'01FF'FFFF	1,048,576	20
26	0x00'03FF'FFFF	2,097,152	21
27	0x00'07FF'FFFF	4,194,304	22
28	0x00'0FFF'FFFF	8,388,608	23
29	0x00'1FFF'FFFF	16,777,216	24
30	0x00'3FFF'FFFF	33,554,432	25
31	0x00'7FFF'FFFF	67,108,864	26
32	0x00'FFFF'FFFF	134,217,728	27
33	0x01'FFFF'FFFF	268,435,456	28
34	0x03'FFFF'FFFF	536,870,912	29
35	0x07'FFFF'FFFF	1,073,741,824	30
36	0x0F'FFFF'FFFF	2,147,483,648	31
37	0x1F'FFFF'FFFF	4,294,967,296	32
38	0x3F'FFFF'FFFF	8,589,934,592	33
39	0x7F'FFFF'FFFF	17,179,869,184	34
40	0xFF'FFFF'FFFF	34,359,738,368	35
> 40	... more ...	changes s₀₀ ...	56

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?

sₙ	Output Bit	Bits in K	Delta from s(N-1)	Hex Value
s₁		K[39..95]	K₃₉	0x80_0000_0000
s₂		K[38..95]	K₃₈	0x40_0000_0000
s₃		K[37..95]	K₃₇	0x20_0000_0000
s₄		K[36..95]	K₃₆	0x10_0000_0000
s₅		K[35..95]	K₃₅	0x08_0000_0000
s₆		K[34..95]	K₃₄	0x04_0000_0000
s₇	Aᵥ₂₇	K[33..95]	K₃₃	0x02_0000_0000
s₈	Aᵥ₂₆	K[32..95]	K₃₂	0x01_0000_0000
s₉	Aᵥ₂₅	K[31..95]	K₃₁	0x00_8000_0000
s₁₀	Aᵥ₂₄	K[30..95]	K₃₀	0x00_4000_0000
s₁₁	Aᵥ₂₃	K[29..95]	K₂₉	0x00_2000_0000
s₁₂	Aᵥ₂₂	K[28..95]	K₂₈	0x00_1000_0000
s₁₃	Aᵥ₂₁	K[27..95]	K₂₇	0x00_0800_0000
s₁₄	Aᵥ₂₀	K[26..95]	K₂₆	0x00_0400_0000
s₁₅	Aᵥ₁₉	K[25..95]	K₂₅	0x00_0200_0000
s₁₆	Aᵥ₁₈	K[24..95]	K₂₄	0x00_0100_0000
s₁₇	Aᵥ₁₇	K[23..95]	K₂₃	0x00_0080_0000
s₁₈	Aᵥ₁₆	K[22..95]	K₂₂	0x00_0040_0000
s₁₉	Aᵥ₁₅	K[21..95]	K₂₁	0x00_0020_0000
s₂₀	Aᵥ₁₄	K[20..95]	K₂₀	0x00_0010_0000
s₂₁	Aᵥ₁₃	K[19..95]	K₁₉	0x00_0008_0000
s₂₂	Aᵥ₁₂	K[18..95]	K₁₈	0x00_0004_0000
s₂₃	Aᵥ₁₁	K[17..95]	K₁₇	0x00_0002_0000
s₂₄	Aᵥ₁₀	K[16..95]	K₁₆	0x00_0001_0000
s₂₅	Aᵥ₀₉	K[15..95]	K₁₅	0x00_0000_8000
s₂₆	Aᵥ₀₈	K[14..95]	K₁₄	0x00_0000_4000
s₂₇	Aᵥ₀₇	K[13..95]	K₁₃	0x00_0000_2000
s₂₈	Aᵥ₀₆	K[12..95]	K₁₂	0x00_0000_1000
s₂₉	Aᵥ₀₅	K[11..95]	K₁₁	0x00_0000_0800
s₃₀	Aᵥ₀₄	K[10..95]	K₁₀	0x00_0000_0400
s₃₁	Aᵥ₀₃	K[ 9..95]	K₀₉	0x00_0000_0200
s₃₂	Aᵥ₀₂	K[ 8..95]	K₀₈	0x00_0000_0100
s₃₃	Aᵥ₀₁	K[ 7..95]	K₀₇	0x00_0000_0080
s₃₄	Aᵥ₀₀	K[ 6..95]	K₀₆	0x00_0000_0040
s₃₅	Aₜ₁₉	K[ 5..95]	K₀₅	0x00_0000_0020
s₃₆	Aₜ₁₈	K[ 4..95]	K₀₄	0x00_0000_0010
s₃₇	Aₜ₁₇	K[ 3..95]	K₀₃	0x00_0000_0008
s₃₈	Aₜ₁₆	K[ 2..95]	K₀₂	0x00_0000_0004
s₃₉	Aₜ₁₅	K[ 1..95]	K₀₁	0x00_0000_0002
s₄₀	Aₜ₁₄	K[ 0..95]	K₀₀	0x00_0000_0001
s₄₁	Aₜ₁₃	K[ 0..95]	...
s₄₂	Aₜ₁₂	K[ 0..95]	...
s₄₃	Aₜ₁₁	K[ 0..95]	...
s₄₄	Aₜ₁₀	K[ 0..95]	...
s₄₅	Aₜ₀₉	K[ 0..95]	...
s₄₆	Aₜ₀₈	K[ 0..95]	...
s₄₇	Aₜ₀₇	K[ 0..95]	...
s₄₈	Aₜ₀₆	K[ 0..95]	...
s₄₉	Aₜ₀₅	K[ 0..95]	...
s₅₀	Aₜ₀₄	K[ 0..95]	...
s₅₁	Aₜ₀₃	K[ 0..95]	...
s₅₂	Aₜ₀₂	K[ 0..95]	...
s₅₃	Aₜ₀₁	K[ 0..95]	...
s₅₄	Aₜ₀₀	K[ 0..95]	...

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 writingPermanent write-prevention when set to 1. Lock₁ === Pin-code lock

Block	P	Purpose	Bits (LSB first)	Bits (MSB first)
0		`user memory	bits 0..15`	bits 15.. 0
1		`user memory	bits 16..29, lock0, lock1`	lock₁, lock₀, bits 29..16
2	RO	`id	bits 0..15`	bits 15.. 0
3	RO	`id	bits 16..31`	bits 31..16
4	wo	`crypto key	bits 0..15`	bits 15.. 0
5	wo	`crypto key	bits 16..31`	bits 31..16
6	wo	`crypto key	bits 32..47`	bits 47..32
7	wo	`crypto key	bits 48..63`	bits 63..48
8	wo	`crypto key	bits 64..79`	bits 79..64
9	wo	`crypto key	bits 80..95`	bits 95..80
10	wo	`pin code	bits 0..15`	bits 15.. 0
11	wo	`pin code	bits 16..31`	bits 31..16
12		`user memory	bits 30..45`	bits 45..30
13		`user memory	bits 46..61`	bits 61..46
14		`user memory	bits 62..77`	bits 77..62
15		`user memory	bits 78..93`	bits 93..78

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̄∧∨