[cryptography] Oddity in common bcrypt implementation

Steven Bellovin smb at cs.columbia.edu
Tue Jun 28 15:14:18 EDT 2011


On Jun 28, 2011, at 2:46 31PM, Marsh Ray wrote:

> On 06/28/2011 12:48 PM, Steven Bellovin wrote:
>>> Wow, this sounds a lot like the way 64-bit DES was weakened to 56 bits.
>>> 
>> It wasn't weakened -- parity bits were rather important circa 1974.
>> (One should always think about the technology of the time.
> 
> It's a very reasonable-sounding explanation, particularly at the time. http://en.wikipedia.org/wiki/Robbed_bit_signaling is even still used for things like T-1 lies.
> 
> But somehow the system managed to handle 64-bit plaintexts and 64-bit ciphertexts. Why would they need to shorten the key? Of the three different data types it would be the thing that was LEAST often sent across serial communications lines needing parity.
> 
> If error correction was needed on the key for some kind of cryptographic security reasons, then 8 bits would hardly seem to be enough.
> 
> What am I missing here?

Errors in plaintext weren't nearly as important.  In text, the normal
redundancy of natural language suffices; even for otherwise-unprotected
data, a random error affects only one data item.  For ciphertext, the
modes of operation provide a range of different choices on error propagation.
In either case, higher-level protocols could provide more detection or
correction.  

A single-bit error in a key, however, could be disastrous; everything is
garbled.  Even hardware wasn't nearly as reliable then; it was not at all
uncommon to have redundant circuitry (at least in mainframes) for registers 
and ALUs, using the complement output of the flip-flops used for registers
(http://en.wikipedia.org/wiki/Flip-flop_%28electronics%29).

And there were fill devices: http://en.wikipedia.org/wiki/Fill_device --
the path from it to the crypto device really needed error detection.

Beyond that -- we know from Biham and Shamir that the inherent strength
of DES is ~54 bits against differential cryptanalysis; having more bits to
go into the key schedule doesn't help.


		--Steve Bellovin, https://www.cs.columbia.edu/~smb








More information about the cryptography mailing list