github/RRG-Proxmark3
1
0
Fork 0
mirror of https://github.com/RfidResearchGroup/proxmark3.git synced 2024-11-09 15:10:36 -08:00
Code Issues Packages Projects Releases Wiki Activity
master
RRG-Proxmark3/client/deps/id48/TECHNICAL.md
Henry Gabryjelski cc2bae2f4d lf em 4x70 writekey --> lf em 4x70 setkey
2024-03-13 09:38:35 -07:00

777 lines
34 KiB
Markdown
Raw Permalink Blame History

This file contains ambiguous Unicode characters

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

# 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 `i`th bit of a bitstring `xⁿ` (where `i<n`)
`xₙ₋₁` | the last bit of a bitstring `xⁿ`
`xₙ` | the `n`th 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 `∧`)
`||` | logical OR (disjunction) (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̄∧∨
```
Reference in New Issue View Git Blame Copy Permalink