lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
Open Source and information security mailing list archives
| ||
|
Message-ID: <20071209170520.GY19691@waste.org> Date: Sun, 9 Dec 2007 11:05:20 -0600 From: Matt Mackall <mpm@...enic.com> To: Theodore Tso <tytso@....edu>, Andrew Morton <akpm@...ux-foundation.org>, linux-kernel@...r.kernel.org Subject: Re: [PATCH 4/6] random: make backtracking attacks harder On Sun, Dec 09, 2007 at 08:33:00AM -0500, Theodore Tso wrote: > On Sat, Dec 08, 2007 at 11:43:37PM -0600, Matt Mackall wrote: > > > If you are trying to find the value of the 80 bits that were > > > extracted, and you know the current state of the pool, yes, you can > > > take the 96 bits that were changed after the last extraction, and try > > > all possible 2**96 combinations of the bits; but you probably won't > > > rule anything out, since after you iterate over all of the 2**96 > > > combinations, you'll probably be able to generate all of the 2**80 > > > possible output bits. So you won't gain anything by trying to do a > > > backtracking attack. So I don't think there's anything to worry about > > > here. > > > > Two observations: > > > > - 2**96 << 2**160 so our feedback is much weaker than our hash so we > > should improve it on general principle > > Well, no. You're comparing apples and oranges here. You can iterate > over 2**96 choices, but given that even if you are doing an iterative > guessing attack, you have 2**80 knowns, and 2**96 unknowns, it doesn't > buy you anything. So saying that there is a successful attack with > O(2**96) simply isn't true! Again, I agree that there's not any sort of useful attack here. > > - there's a way to improve this attack to 2**64 in some situations! > > Yeah, but again, what does this "attack" buy you? If you know the > output, and the current state of the pool, after doing 2**64 > iterations you can get the state of the pool before the output. > Big-di-whoopdie-do. You can't actually *do* anything with it. Ahh, but this an attack on the output! You know only: pool' (including a fortuitously placed add_ptr) and from that, you can get all but 64 bits of pool. By 2**64 iterations of: pool = pool' + guess hash = SHA1(init, pool) # simplified pool^ = add(pool, hash) if pool^ = pool': success! Now you've recovered pool. Then you can recover the *output* with: hash = SHA1(init, pool) pool' = add(pool, hash) entropy = extract(pool) output = SHA1(hash, entropy) Depending on where the add_ptr lands, we might even be able to go back another iteration. By the way, I think the paper missed out on some corner case attacks which extend the range to greater than half of the possible add_ptr positions. Whenever less than 96 bits are changed in the first block, we can discover the pool in O(2**64). > It's fixing a non-problem, but I don't think changing actually hurts > anything. My preferred way of dealing with this problem is simply to > increase the output pool size, since that increases the number of bits > that change each time from 96 bits to 160 bits. Let's do that. But let's also do this because it makes the code more readable and somewhat stronger (for instance the first word fed back will be cascaded from the whole pool rather than the first 512 bits). We also only need to grab the lock once. -- Mathematics is the supreme nostalgia of our time. -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@...r.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Powered by blists - more mailing lists