Messages in this thread | | | Date | Sat, 21 Nov 1998 18:26:06 +0100 | From | Alexander Kjeldaas <> | Subject | Re: kerneli blowfish/twofish compromised? |
| |
[cc'd to the author who can answer to these allegations better than me]
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/
| |