[Discuss] KeePassX

[blu at nedharvey.com (Edward Ned Harvey (blu))]

> From: Kent Borg [mailto:kentborg at borg.org]
> Sent: Wednesday, August 14, 2013 10:25 AM
> 
> But you don't mean AES-128 can be broken today with 2^64 operations, do
> you?  That sounds wrong--or theoretical.

That is what I'm saying, but it was at least a year or two ago I read that, and I can't seem to find my book anymore.  I wonder if I let somebody borrow it...  If anybody on this list has a copy of Cryptography Engineering, I'm almost certain you can look up even / odd permutations in the index and find 2-3 pages in the chapter about block ciphers, discussing this topic and concluding that you need twice as many bits as you think you need.  Specifically, they conclude that you need 256 bits in order to withstand attack of 2^128 operations.  I'd love to validate or clarify this topic...

This is all I can really remember of it:

Given that one of the requirements of a block cipher is a 1-1 mapping of all possible plaintexts to all possible ciphertexts (message must be losslessly decipherable), you can imagine having a (impossibly) huge table that maps each possible plaintext to a corresponding ciphertext, given a specified Key & IV.  Ideally, the plaintext-to-ciphertext table would be a completely independent random shuffling of the ordering of ciphertexts, for each different Key/IV combination.  But since we're not doing an *actual* shuffle, we're actually mathematically constructing the table by a sequence of ciphertext reorder operations, and we're constrained by the 1-1 mapping requirement, you acknowledge, if you imagine beginning to construct this table, every time you set one of the plaintexts to correspond to one of the ciphertexts, it means that ciphertext can no longer be associated to the plaintext that it was formerly associated with, which means the *other* plaintext must now be associated to the ciphertext that was formerly associated with the plaintext that you just set.  In other words, every change you make to the table implies another (inverse) change to the table.  Every change you make must involve swapping the relationships between two plaintexts and two ciphertexts.

Every possible mapping of plaintexts to ciphertexts is called a permutation, and every permutation can be either even or odd - that is - the number of reordering operations to construct the table is either even or odd.  But because we're not using a true random shuffling, we're instead performing this sequence of location swaps that involve two swaps for every intended swap...  It means that every known real block cipher uses only even permutations.

How you translate this weakness into an attack, I don't know.  It may be theoretical for all I know.  Also, my understanding of the mathematics would have me conclude that I only lost one bit from my key, not half the bits.  That's why I only *use* cryptography and don't *create* it.  I read a book and took a class on how to *use* cryptography.  I am utterly unqualified to create ciphers and hashes.  As I recall, the book talked about some more stuff, that I don't really understand (or at least don't remember clearly) and he concluded that all known real-world block ciphers using 256 bit keys actually require 2^128 operations to break.

This is separate from and not to be confused with the birthday attack - wherein you only need 2^128 operations to produce an expected collision on a 256 bit hash function.