Re: [cryptography] Weak random data XOR good enough random data = better random data?
On Mon, Jul 28, 2014 at 06:23:12PM +0200, Lodewijk andré de la porte wrote: I'm working on some Javascript client side crypto. There's a cryptographic quality random generator present in modern browsers, but not in older ones. I also don't trust browsers' random generators' quality. I'd like to ship a few KB (enough) of random data and XOR it with whatever the best-available RNG comes up with. That way the user can still verify that I didn't mess with the randomness, no MITM attacks can mess with the randomness, but given a good transport layer I can still supplement usually bad randomness. There are a couple things that you can do for older browsers that don't support crypto.getRandomValues(): 1. You can build your own CSPRNG using either Blum Blum Shub or Blum Micali. In both cases, the CSPRNG is slow, and you'll need to rely on a bigint.js library for the primes, but if all you need is a few KB of random data, this will suffice. I've built BBS in Javascript, adhering to all the rules, and it performs good enough, and the security lies in the hard factoring problem. 2. You can checkout isaac.js at https://github.com/rubycon/isaac.js. ISAAC is a CSPRNG written by Rober Jenkins in 1996, and based on RC4. It is fast and secure. -- . o . o . o . . o o . . . o . . . o . o o o . o . o o . . o o o o . o . . o o o o . o o o pgpX8VQrODfZT.pgp Description: PGP signature ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Weak random data XOR good enough random data = better random data?
From: Lodewijk andré de la porte Subject: Re: [cryptography] Weak random data XOR good enough random data = better random data? Come to think of it, is there or why isn't there a block-cipher mode that chains using a hashing algorithm? The main reason would be difficulty in proving security. Spacing on the term right now, but I’ll call it a cycle. Every hash function has cycles, so to define it: H[0] = Hash(input) H[N]= Hash(H[N-1]) The problem is that H[i] == H[j] where i =/= j. Every input for every hash has cycles, and current hashes have large numbers of them. CTR mode relies on the cycle length being the 2^block_size. CBC relies on the cycle length being very long. Proving the minimum cycle length in a hash is not something that I am aware ever having been done, making it effectively impossible to prove security. So while using a hash function in the block chaining sounds like a good idea, because we have proofs of security for CTR and CBC that say they are no weaker than the cipher, the hash mode would have to actually prove that it is stronger than the underlying cipher for the extra computation to be worth it. I can’t say that it is impossible to do, just that it hasn't been done, and I don't expect it to be done. Joe ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Weak random data XOR good enough random data = better random data?
On Mon, Jul 28, 2014 at 9:23 AM, Lodewijk andré de la porte l...@odewijk.nl wrote: If I XOR probably random data with good enough random data, does that result in at least good enough random data? Yes, in fact, it's provably at *least* as random as the most random of the two data sources: https://en.wikipedia.org/wiki/Product_cipher -- Tony Arcieri ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Weak random data XOR good enough random data = better random data?
isn't the simplest solution would be to concatenate or XOR a counter? Thus H[0] = Hash(input) H[N] = Hash(H[N-1]+CTR) considering that hashes from MD4 to SHA-2 all have block sizes of 512 bits, much larger than their outputs, one could simply concatenate a 128-bit counter. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Weak random data XOR good enough random data = better random data?
Thanks for the responses everyone! Reg. making a CSPRNG in JS: I don't have experience and wouldn't trust it. Using someone else's is even worse, I find other's often do things even worse (somehow). And seeding it would sort of have moved the problem rather than solving it. A PRNG shouldn't be able to generate entropy out of nothing and I don't really feel like doing the cryptanalysis (or trusting someone else's ;) (but it's probably a decent way to do it, I've seen a JS Fortuna for example) Everyone else told me basically the same thing, but somehow it all made complete sense only after James' comment. It sounds like what you want is a way to generate randomness a user can trust, in a browser lacking crypto.getRandomValues. That's hard to impossible - it's why crypto.getRandomValues was made. I believe state of the art prior to crypto.gRV was using mouse movements and other server-unpredictable events. That's exactly it! I'm not 100% on the security of the wiggle-mouse based entropy, still seems a bit too sketchy to me. I'd also prefer not to annoy users any more than I have to. It's also just a lot of hassle. Do touchscreens provide the same entropy? What about a user with a *very* slow phone (maybe an update in the background)? Prefer avoiding dragons, even if they seem small enough to slay. If I just hand the user data it's deferred computing, not clientside crypto. There's also the question of whether crypto.getRandomValues can be trusted. Where does the browser get it's entropy? Does the browser add flaws? HTML runs on a wide device landscape, PC's, Game Consoles, SmartTV's, e-readers, smartphones, etc. (in the future they'll support the current HTML5 or I may support them, now I doubt many would run my website properly) As an added bonus I can more easily reach users that just don't care. If you get a stern warning to upgrade or suffer decreased security and ignore it, I'd like to say I don't have to care. The problem is that users are unknowing, so you can't expect them to respond to such a warning. Now I can rest easy knowing I gave them good randomness. The client-side randomness assurance couldn't be important to people running aged software. So, thanks everyone, for checking my sanity. Wouldn't know what to do without a list like this. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Weak random data XOR good enough random data = better random data?
Come to think of it, is there or why isn't there a block-cipher mode that chains using a hashing algorithm? ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
[cryptography] Weak random data XOR good enough random data = better random data?
Hey everyone, If I XOR probably random data with good enough random data, does that result in at least good enough random data? I'm working on some Javascript client side crypto. There's a cryptographic quality random generator present in modern browsers, but not in older ones. I also don't trust browsers' random generators' quality. I'd like to ship a few KB (enough) of random data and XOR it with whatever the best-available RNG comes up with. That way the user can still verify that I didn't mess with the randomness, no MITM attacks can mess with the randomness, but given a good transport layer I can still supplement usually bad randomness. I don't see how it could reduce the randomness to XOR with patterned data. If someone knows better of this, let me know. If I'm correct that also means it should be okay to reuse the few KB's should they ever run out (in this system), at worst it no longer improves the randomness. I don't expect that to ever happen, and I'd prefer requesting new KB's, but it's still interesting. Could someone confirm this whole thought-train for me? That means, is it a good idea to (over HTTPS) send some randomness*, XOR it with the best-available RNG for better randomness? I actually feel pretty confident about it, just asking for (a few) second opinion(s). Best regards, Lewis * It'd probably siphon down from a Linux OS, but ofc the code is portable so randomness is probably low quality too. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Weak random data XOR good enough random data = better random data?
On 7/28/2014 12:23 PM, Lodewijk andré de la porte wrote: Hey everyone, If I XOR probably random data with good enough random data, does that result in at least good enough random data? I'm working on some Javascript client side crypto. There's a cryptographic quality random generator present in modern browsers, but not in older ones. I also don't trust browsers' random generators' quality. I'd like to ship a few KB (enough) of random data and XOR it with whatever the best-available RNG comes up with. That way the user can still verify that I didn't mess with the randomness, no MITM attacks can mess with the randomness, but given a good transport layer I can still supplement usually bad randomness. I don't see how it could reduce the randomness to XOR with patterned data. If someone knows better of this, let me know. If I'm correct that also means it should be okay to reuse the few KB's should they ever run out (in this system), at worst it no longer improves the randomness. I don't expect that to ever happen, and I'd prefer requesting new KB's, but it's still interesting. Could someone confirm this whole thought-train for me? That means, is it a good idea to (over HTTPS) send some randomness*, XOR it with the best-available RNG for better randomness? I actually feel pretty confident about it, just asking for (a few) second opinion(s). Best regards, Lewis * It'd probably siphon down from a Linux OS, but ofc the code is portable so randomness is probably low quality too. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography The words probably and good enough do not sit well with me. I think javascript uses the mt random number generator. My advise is combine that with another source and a hash. In other words: Good enough is not good enough. -- Kevin ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Weak random data XOR good enough random data = better random data?
On 28 Jul 2014 18:23 +0200, from l...@odewijk.nl (Lodewijk andré de la porte): If I XOR probably random data with good enough random data, does that result in at least good enough random data? If you are truly concerned, have you considered implementing a proper CSPRNG yourself in Javascript (or using someone else's implementation of the same; I'm sure they are out there) and seeding that PRNG with randomness from both sides of the communications channel? It'd be a bit less obvious to the casual code viewer what's going on, but you would seem to have a much better shot of guaranteeing a particular level of randomness provided to whatever uses the PRNG. -- Michael Kjörling • http://michael.kjorling.se • mich...@kjorling.se OpenPGP B501AC6429EF4514 http://michael.kjorling.se/public-keys/pgp “People who think they know everything really annoy those of us who know we don’t.” (Bjarne Stroustrup) ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Weak random data XOR good enough random data = better random data?
Den 28 jul 2014 18:23 skrev Lodewijk andré de la porte l...@odewijk.nl: Hey everyone, If I XOR probably random data with good enough random data, does that result in at least good enough random data? I'm working on some Javascript client side crypto. There's a cryptographic quality random generator present in modern browsers, but not in older ones. I also don't trust browsers' random generators' quality. I'd like to ship a few KB (enough) of random data and XOR it with whatever the best-available RNG comes up with. That way the user can still verify that I didn't mess with the randomness, no MITM attacks can mess with the randomness, but given a good transport layer I can still supplement usually bad randomness. I don't see how it could reduce the randomness to XOR with patterned data. If someone knows better of this, let me know. If I'm correct that also means it should be okay to reuse the few KB's should they ever run out (in this system), at worst it no longer improves the randomness. I don't expect that to ever happen, and I'd prefer requesting new KB's, but it's still interesting. Could someone confirm this whole thought-train for me? That means, is it a good idea to (over HTTPS) send some randomness*, XOR it with the best-available RNG for better randomness? I actually feel pretty confident about it, just asking for (a few) second opinion(s). With a mixer function that isn't shitty and lossy/non-reversable, you are unlikely to lose entropy. With XOR specifically, then AS LONG AS THE INPUTS ARE UNCORRELATED you will not lose entropy (you always has at least as much entropy as your most entropic input). XOR practically anything with random and you still have random. But if you bitflip the XOR key and XOR that string with the key, you get all 0's. Not good. There are tons of methods by which they can be correlated that leak data. If you know why/how one time pads are mathematically proven uncrackable, you should know why this is true. Also, because of how XOR works, you need to make sure at least one of the inputs have high entropy density if you need to use the output for something that needs good randomness. Two books of random sentences have high entropy, but low entropy density (on average one bit of entropy per character, while each character takes about 7 or 8 bits of space to represent on the hard drive). Taking 256 bits of XOR'ed random words as a key for something is NOT good enough. This is when you need strong mixing like hashing or encryption of the entire input, so that each bit in the output represents close enough to a full bit of entropy. Any reversible method can not lose entropy. Otherwise you have found a magical compression function. Practically any encryption algorithm (all reversible) that is considered secure can be used to mix your inputs, and you will not lose entropy (even insecure encryption algorithms also shouldn't cause entropy loss, unless what you used as a key held most of the entropy and the encryption algorithm fails to mix it properly with the plaintext - in which case your plaintext still sets the minimum entropy of the output). Most good hashing algorithms will also preserve most of the entropy (for equivalent length inputs, you can't preserve 500 bits of entropy in a 100 bit hash). If you need 200 bits of entropy, it should be safe to use a modem hash function with a 256 bit strength to hash all of your inputs. One example: RC4 produces a biased key stream that you can recover the original key from if you can get a pure enough version with enough bits of the raw key stream. Use RC4 to encrypt standard ASCII plaintext (the literal version) and the attacker can use statistical attacks to remove enough of the plaintext from the ciphertext to get parts of the key stream, then the key can be cracked to decrypt everything. However, that attack fails if you only encrypt high entropy plaintexts as they then can't be separated from the key stream (same argument for why as the one time pad security). Also, there's no known easy of cracking ChaCha20's key stream, it looks random (no known detectable bias) and the key can't be recovered, so it would resist the above attack. Using a well defined existing mixing function with your own predefined random data, like a salt, is fine. It doesn't make it weaker. Even XOR'ing it in will never make it weaker. But however, if it is publicly known shared randomness then it only prevents cross-service rainbow tables and similar batch bruteforce attacks (adds work to crack them all linearly with the number of services rather than linearly with number of total users (assuming reused randomness)). It doesn't help against targeted attacks. Note that a MITM that can replace that randomness you send out imply that they can inject malicious code as well, in which case the security is non-existent. Then they can explicitly attack the RNG to be bad, or backdoor everything. ___
Re: [cryptography] Weak random data XOR good enough random data = better random data?
Lodewijk andré de la porte writes: I don't see how it could reduce the randomness to XOR with patterned data. If someone knows better of this, let me know. If I'm correct that also means it should be okay to reuse the few KB's should they ever run out (in this system), at worst it no longer improves the randomness. I don't expect that to ever happen, and I'd prefer requesting new KB's, but it's still interesting. DJB describes a more complicated scenario in which an active attacker manipulates one source of entropy in order to reduce the unpredictability of the overall output. http://blog.cr.yp.to/20140205-entropy.html I guess the other bad case is where both sources are systematically correlated in some way (that doesn't change their overall statistics individually, and that an attacker wouldn't otherwise have been able to notice). It's hard to see a path to that in this case. But you could certainly construct an artificial scenario where it's true. DJB also announced a randomness-generation mailing list in that post; I'm not sure what level of participation it's gotten, but that might be another good place to bring up this topic. -- Seth Schoen sch...@eff.org Senior Staff Technologist https://www.eff.org/ Electronic Frontier Foundation https://www.eff.org/join 815 Eddy Street, San Francisco, CA 94109 +1 415 436 9333 x107 ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Weak random data XOR good enough random data = better random data?
You're talking about two different things here. As others have said, if you XOR good random with 'not very good but non-malicious random' - you are unlikely to reduce the entropy. (And as Seth said, if you XOR good random with malicious random (e.g. a trojaned RDRAND instruction) you're in bad shape.) But that's not what you asked. On Mon, Jul 28, 2014 at 11:23 AM, Lodewijk andré de la porte l...@odewijk.nl wrote: That way the user can still verify that I didn't mess with the randomness, no MITM attacks can mess with the randomness, but given a good transport layer I can still supplement usually bad randomness. What this _sounds like_ to me, is that you want to try and make a good faith effort to users that you can't deduce the randomness their browser generates. You ship them high quality RNG output, and then generate some randomness (probably Math.random() based?) and the output should be unguessable by you. But it's not. Math.random()-based random is guessable in 2^X, to varying degrees of X: maybe between 20 60? (I'm estimating off recollections of papers from my head.) Math.random() seeded algorithms are also guessable - once seeded an algorithm doesn't make more entropy. It sounds like what you want is a way to generate randomness a user can trust, in a browser lacking crypto.getRandomValues. That's hard to impossible - it's why crypto.getRandomValues was made. I believe state of the art prior to crypto.gRV was using mouse movements and other server-unpredictable events. -tom ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Weak random data XOR good enough random data = better random data?
On 2014-07-29 02:23, Lodewijk andré de la porte wrote: Hey everyone, If I XOR probably random data with good enough random data, does that result in at least good enough random data? Yes, but other mixing functions are better. Best to hash all streams together, rather than xor them together. Then if there is any random difference between two imperfectly random streams, the resulting stream will be more random than either one. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
