[Top] [All Lists]

RE: [Cfrg] OpenPGP security analysis

2002-09-17 12:08:24

Another attack, based on the fact that the last block containing part of the
hash is subject to bit-flipping, as David Wagner points out:

Suppose a 16-byte block size is being used, so the last 16 bytes of the SHA1
hash are subject to modification.  This means the attacker can make targeted
changes to the ciphertext, and if he is able to predict what effect these
changes have on the corresponding plaintext, then he can compute what the
new SHA1 hash should be.  If this new hash collides with the old hash in the
first 4 bytes, then he can bit-flip the last 16 bytes of the SHA1 hash to
match.  So the attacker can experimentally try around 2^31 ciphertext
modifications, and odds are one of them will collide with the unmodifiable 4
bytes of the hash, and he'll be able to make a forgery.

With CFB (which PGP uses) and known plaintext, the attacker can make
computable alterations in the plaintext by changing the ciphertext.
Px     (the xth plaintext block)
Px+1   (the x+1th plaintext block)
Py     (the yth plaintext block)

He can change the ciphertext with predictable results on the plaintext by
setting Cy=Cx.  Then he can compute:
Py   = (Py xor Cy) xor Cx
Py+1 = (Px+1 xor Cx+1) xor Cy+1

Note that the attacker can't control Py or Py+1 with precision, because if
he did targeted bit-flipping on the ciphertext he wouldn't know what that
block was encrypted as.  So this would mostly be useful for overwiting a
particular section of incriminating evidence with random data, or somesuch.

There may other ways of making predictable modifications of the plaintext,
which can also take advantage of the fact that you only need to find a
collision on 4 bytes of the hash, then can bit-flip the rest.