lkml.org 
[lkml]   [1998]   [Nov]   [21]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    From
    SubjectRe: 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/

    \
     
     \ /
      Last update: 2005-03-22 13:45    [W:0.029 / U:1.592 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site