On Sat, Nov 21, 1998 at 12:37:45AM -0600, kernel@mallory.draper.net wrote:
> Hi,
>
> I suspect that the twofish and blowfish code, as contained in the
> Linux International Kernel Crypto Patch *ONLY*, is compromised.
>
> See:
> ftp://ftp.kerneli.org/pub/linux/kerneli/v2.1/patch-int-2.1.129.1.gz.
>
> This is ** NOT ** an allegation that twofish and blowfish, developed
> by Bruce Schneier, have problems. I am sure that Bruce's reference code
> is fine. Also please forgive my being off topic... many people on this
> list use these patches.
>
> Background: Since Linus is hinting strongly that 2.2 is about to be
> born, the time seems right to retrofit my own stuff into the new world.
>
> While modifying the loop device driver to support an IV derived from
> from the disk block number, and using twofish from the international
> patch as a code base, I checked the CBC ciphertext corresponding to
> several hundred thousand bytes of plaintext zeros looking for repeating
> patterns... (I am not a great cryptanalyst, on the other hand I hate to
> build obviously broken code, so I check these things).
>
> Repeating patterns did exist which is a very bad thing for CBC mode
> code to do. Thinking I have a bug I dig further...
>
> Module loop_fish2.c function blockEncrypt_CBC at line #437 zeros
> the IV (reverting to far less secure ECB mode, hmmm):
> if ( ( len & 0x1FF) == 0)
> {
> iv0=0;
> iv1=0;
> iv2=0;
> iv3=0;
> }
>
This makes sense. In CBC-mode, two messages are identical up to the
first difference in the plaintext. Each block on the device is
treated as a separate message. Finding repeating patterns is
expected, and therefore the implementation isn't *necessarily* broken.
Say you had 200k of zeros that would be 400 messages (512 bytes each)
and 400 repeating patterns.
One solution to avoid this is to initialize CBC-mode with the
block-number as an initialization block. You *know* this - you were
trying to fix exactly this weakness so I'm really confused about what
you're trying to show.
> This accounts for the repeating patterns in ciphertext. Now my
> confidence in the International Crypto Patch is shaken and I wonder
> if blowfish also has problems. More checking... blowfish from the
> patch appears to leak plaintext directly into ciphertext...
>
> Module loop_blow.c function blowfish_cbc_encrypt at line #361:
> if (size & 0x000001FF)
> {
> memcpy(dst, src, size);
> return;
> }
>
> Module loop_blow.c function blowfish_cbc_decrypt at line #420 recovers
> the leaked plaintext.
>
> I am requesting that another set of eyes take a look at blowfish and twofish
> from the International Patch. It is possible that I am going nuts having
> worked into the wee hours (again). On the other hand, this does not look
> like an accidental set of bugs; and if someone is leaking compromised crypto
> to the world then perhaps this needs to be, um, known.
>
I agree that this looks bad!
However, I'm pretty sure the above code will never be executed since I
don't think it is possible to get the kernel to read or write less
than 512 bytes from a block device - the whole cbc-mode depends on
this (I don't think the kernel will read/write less than a page - can
someone confirm this?). The code is trying to cope with the kernel
not requesting a multiple of 512 bytes. Failing instead of leaking
plaintext would probably be a better idea, but I wouldn't call the
code compromised if the kernel never reads less than 512 bytes.
In regard to your work I can say that none of the loop-devices
currently use the block-number as initialization vector and therefore
there are weaknesses. The loop devices use the "weak" ECB, or the
better CBC mode (but with IV=0). Currently the patch is a set of
independent patches all containing crypto. I'm working on moving the
ciphers out of the loop-devices and into a separate library with an
API accessible by other parts of the kernel (for example IPsec, CIPE
etc). When the move is made, I hope that we eventually have
regression tests for each cipher with test-vectors to be sure that the
implementations are correct.
astor
PS: Eyeball pressure is always welcomed - especially for this patch.
-- Alexander Kjeldaas, Guardian Networks AS, Trondheim, Norway http://www.guardian.no/- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.rutgers.edu Please read the FAQ at http://www.tux.org/lkml/