### 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
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

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
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

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

```