Cryptography Reference
In-Depth Information
If we take an arbitrary plaintext,
p
0
, and build 17 plaintexts,
p
i
, that all differ
only in one byte of
p
0
, then there must be at least two
p
i
in which the differing
bytes are in the same row. We select two such texts,
p
m
and
p
n
, and encrypt
them. Exactly 31 positions of every cipher will
not
differ from the encrypted
text,
p
0
. For example, if we use '0' for the bytes where fcrypt(
p
m
) does not
differ from fcrypt(
p
0
), and analogously use '1' for the bytes of
p
n
, things would
look like this:
...0......1.....
...0......1.....
...0......1.....
...0......1.....
...0......1.....
...0......1.....
XXXXXXXXXXXXXXXX
...0......1.....
...0......1.....
...0......1.....
...0......1.....
...0......1.....
...0......1.....
...0......1.....
...0......1.....
...0......1.....
The positions marked with 'X' haven't changed in the two ciphertexts. If we
were an attacker with access to a ciphering device, we would consequently
proceed as follows:
•
We take plaintext
p
0
and build 17 slightly modified plaintexts,
p
i
,as
described above.
•
We have all 18 texts encrypted with the same key and intercept the
ciphertexts.
•
For each cipher, fcrypt(
p
i
), we find the bytes that don't differ from
fcrypt(
p
0
)
. These are always 31 positions. We call the set of all positions
of these bytes the 'checkpoint set'.
•
Two different checkpoint sets will generally have two common elements.
But at least two sets have exactly 16 common elements. This means that
we've recovered one row or one column of the secret matrix.
•
Using a sufficiently large number of plaintexts and doing some puzzle
work, it's relatively easy to recover the secret matrix.
