Re: Randomness, Quantum Mechanics - and Cryptography
On Sep 6, 2010, at 10:49 PM, John Denker wrote: If you think about the use of randomness in cryptography, what matters isn't really randomness - it's exactly unpredictability. Agreed. This is a very tough to pin down: What's unpredictable to me may be predictable to you, It's easy to pin down. If it's unpredictable to the attacker, it's unpredictable enough for all practical purposes. I was talking about mathematical, even philosophical, underpinnings - not practical purposes. In any case, even if you are concerned with practice, the statement that something is unpredictable to the attacker sounds suspect. After all, most junk cryptographic arguments claim that some algorithm is not reversible by the attacker. One should really expect more. and unpredictability collapses as soon as the random value is known (measured?). QM unpredictability as described by Conway seems much closer to the kind of thing you really need to get crypto results. You're working too hard. QM is interesting, but it is overkill for cryptography. Plain old classical thermodynamical randomness is plenty random enough. But there isn't actually such a thing as classical thermodynamical randomness! Classical physics is fully deterministic. Thermodynamics uses a probabilistic model as a way to deal with situations where the necessary information is just too difficult to gather. Classically, you could in principle measure the positions and momenta of all the atoms in a cubic liter of air, and then produce completely detailed analyses of the future behavior of the system. There would be no random component at all. In practice, even classically, you can't hope to get even a fraction of the necessary information - so you instead look at aggregate properties and, voila, thermodynamics. There's no randomness assumption - much less an unpredictability assumption - for the micro-level quantities. What you need is some uniformity assumptions. If I had access to the full micro details of that liter of air, your calculations of the macro quantities would be completely undisturbed. FWIW, quantum noise is just the limiting case of thermal noise in the limit of high frequency and/or low temperature. There is no dividing line between the two, by which I mean that the full range of intermediate cases exists, and the same equation describes both asymptotes and everything in between. A graph of noise versus temperature for a simple circuit can be found at http://www.av8n.com/physics/thermo/partition-function.html#fig-qho If anybody can think of a practical attack against the randomness of a thermal noise source, please let us know. By practical I mean to exclude attacks that use such stupendous resources that it would be far easier to attack other elements of the system. As a matter of practical engineering, I agree with you. But read what you said over again, and distinguish it from typical snake-oil arguments for novel crypto algorithms. The differences that make your claims believable while those of the snake-oil salesmen are not are subtle and illuminating. But, as the long argument on this subject today has shown, that's still not the end of the story. Just as the snake-oil systems typically fail because their security claims require constraints on the attacker (which real attackers will get around), your claims assume constraints as well. Lowering the temperature and injecting RF. Hmm, hadn't thought of that as an attack technique -- Jerry - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: Randomness, Quantum Mechanics - and Cryptography
On Tue, 7 Sep 2010 22:22:57 -0400 Jerry Leichter leich...@lrw.com wrote: On Sep 6, 2010, at 10:49 PM, John Denker wrote: It's easy to pin down. If it's unpredictable to the attacker, it's unpredictable enough for all practical purposes. I was talking about mathematical, even philosophical, underpinnings - not practical purposes. In any case, even if you are concerned with practice, the statement that something is unpredictable to the attacker sounds suspect. After all, most junk cryptographic arguments claim that some algorithm is not reversible by the attacker. One should really expect more. Actually, I've seen a significant number of proofs in the crypto world that amount to show that the attacker cannot distinguish these bits from a set of random bits with probability better than uninformed guessing. It appears to be reasonable to think that if the attacker cannot distinguish a stream from a true random stream, or cannot predict the next bit with better probability than chance, the attacker has no handle on which to base an attack. I would invite people who are more versed on this topic to chime in. Perry - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Hashing algorithm needed
Hi. Just subscribed to this list for posting a specific question. I hope the question I'll ask is in place here. We do a web app with an Ajax-based client. Anybody can download the client and open the app, only, the first thing the app does is ask for login. The login doesn't happen using form submission, nor does it happen via a known, standard http mechanism. What we do is ask the user for some login information, build a hash out of it, then send it to the server and have it verified. If it checks out, a session ID is generated and returned to the client. Afterwards, only requests accompanied by this session ID are answered by the server. Right now, the hash sent by the browser to the server is actually not a hash, but the unhashed login info. This has to be changed, of course. What we need is a hashing algorithm that: - should not generate the same hash every time - i.e. should includen something random elements - should require little code to generate - should allow verification of whether two hashes stem from the same login data, without having access to the actual login data We need to implement the hashing algorithm in Javascript and the verification algorithm in Java, and it needs to execute reasonably fast, that's why it has to require little code. None of us is really into cryptography, so the best thing we could think of was asking for advice from people who grok the domain. The idea is the following: we don't want to secure the connection, we just want to prevent unauthenticated/unauthorized requests. Therefore, we only send a hash over the wire and store it in the database when the user changes his password, and only send different hashes when the user authenticates later on. On the server, we just verify that the stored hash and the received hash match, when an authentication request arrives. Cleartext passwords aren't stored anyway, and don't ever travel over the wire. However, we could not imagine a reasonable algorithm for what we need until now, and didn't find anything prefabricated on the web. Therefore we ask for help. br, flj PS: reusing the session ID is of course a security risk, since it could allow session hijacking. We're aware of this, but don't intend to do anything about it other than warn customers/users. Since it's a web application, its client code is open, and anybody being able to watch the connection can deduce whatever is needed to hijack the session, no matter what algorithm is used, unless the connection is encrypted right from the start. Connection security is however outside the scope of the web application. We can't encrypt communication in Javascript for efficiency reasons, it has to be done in a lower layer (VPN or SSL, for example). It may in theory work using a preshared key, but it's not reasonable to believe that the application users will be able to cope with such a mechanism. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: Randomness, Quantum Mechanics - and Cryptography
On Tue, Sep 07, 2010 at 10:22:57PM -0400, Jerry Leichter wrote: But there isn't actually such a thing as classical thermodynamical randomness! Classical physics is fully deterministic. Thermodynamics uses a probabilistic model as a way to deal with situations where the necessary information is just too difficult to gather. Classically, you could in principle measure the positions and momenta of all the atoms in a cubic liter of air, and then produce completely detailed analyses of the future behavior of the system. There would be no random component at all. In practice, even classically, you can't hope to get even a fraction of the necessary information - so you instead look at aggregate properties and, voila, thermodynamics. There's no randomness assumption - much less an unpredictability assumption - for the micro-level quantities. What you need is some uniformity assumptions. If I had access to the full micro details of that liter of air, your calculations of the macro quantities would be completely undisturbed. This glosses over the *fundamental* complexity of non-linear classical dynamics. It is a leap to claim that the underlying determinism of a classical dynamical system leads one to conclude that it is even in principle predictable, in the presence of chaos. We should not short-change classical chaos which is an emergent property of complex deterministic systems. http://www-chaos.umd.edu/research.html ... Riddled Basins The notion of determinism in classical dynamics has eroded since Poincar??'s work led to recognition that dynamical systems can exhibit chaos: small perturbations grow exponentially fast. Hence, physically ubiquitous measurement errors, noise, and computer roundoff strongly limit the time over which, given an initial condition, one can predict the detailed state of a chaotic system. Practically speaking, such systems are nondeterministic. Notwithstanding the quantitative uncertainty caused by perturbations, the system state is confined in phase space (on an attractor) so at least its qualitative behavior is predictable. Another challenge to determinism arises when systems have competing attractors. With a boundary (possibly geometrically convoluted ) between sets of initial conditions tending to distinct attractors (basins of attraction), perturbations make it difficult to determine the fate of initial conditions near the boundary. Recently, mathematical mappings were found that are still worse: an attractor's entire basin is riddled with holes on arbitrarily fine scales. Here, perturbations globally render even qualitative outcomes uncertain; experiments lose reproducibility. J.C. Sommerer and E. Ott, A Qualitatively Nondeterministic Physical System, Nature, 365, 135 (1993). -- Viktor. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: Hashing algorithm needed
On 8 September 2010 16:45, f...@mail.dnttm.ro wrote: Hi. Just subscribed to this list for posting a specific question. I hope the question I'll ask is in place here. We do a web app with an Ajax-based client. Anybody can download the client and open the app, only, the first thing the app does is ask for login. The login doesn't happen using form submission, nor does it happen via a known, standard http mechanism. What we do is ask the user for some login information, build a hash out of it, then send it to the server and have it verified. If it checks out, a session ID is generated and returned to the client. Afterwards, only requests accompanied by this session ID are answered by the server. Right now, the hash sent by the browser to the server is actually not a hash, but the unhashed login info. This has to be changed, of course. What we need is a hashing algorithm that: - should not generate the same hash every time - i.e. should includen something random elements - should require little code to generate - should allow verification of whether two hashes stem from the same login data, without having access to the actual login data We need to implement the hashing algorithm in Javascript and the verification algorithm in Java, and it needs to execute reasonably fast, that's why it has to require little code. None of us is really into cryptography, so the best thing we could think of was asking for advice from people who grok the domain. Well, you can't always get what you want. What I do in Nigori for this is use DSA. Your private key, x, is the hash of the login info. The server has g^x, from which it cannot recover x, and the client does DSA using x. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: Hashing algorithm needed
f...@mail.dnttm.ro writes: The idea is the following: we don't want to secure the connection, Why not? Using HTTPS is easier than making up some half-baked scheme that won't work anyway. -- http://noncombatant.org/ - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
