Intuitive cryptography that's also practical and secure.

Good work.  In fact, I knew days ago that you would post
this...

I agree with you about intuitive cryptography.  What you're
complaining
about is, in effect, "Why Johnny Can't Hash". 
There was another
instance of that in today's NY Times.  In one of the court
cases
stemming from the warrantless wiretapping, the Justice
Department is,
in the holy name of security, effectively filing court
papers with
itself -- it's depositing the "filings" in a
secure facility, rather
than with the court, to protect them.  I won't go into the
legal,
political, judicial, or downright bizarre aspects of this
case (save to
note that one of the plaintiff's attorneys was quoted as
saying
"Sometime during all of this, I went on Amazon and
ordered a copy of
Kafka?s ?The Trial,? because I needed a refresher course in
bizarre
legal procedures."), but one point the article
mentioned is
relevant here:  how is the record preserved for a possible
appeal?  Indeed, one of the judges involved has commented on
that
point.

There's an obvious cryptographic solution, of course:
publish the
hash of any such documents.  Practically speaking, it's
useless.  Apart
from having to explain hash functions to lawyers, judges,
members of
Congress, editorial page writers, bloggers, and talk show
hosts, is
this a time you'd want to stand up before a Congressional
committee and
testify that some NSA technology, i.e., SHA-512, that NIST
thinks needs
replacing, is still strong enough to protect documents that
concern
possible NSA misconduct?  And of course, collision attacks
are
precisely the concern here.

------------------------------------------------------------
---------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography"
to majordomometzdowd.com

Matt Blaze wrote:
> an even more important problem
> than psychic debunking, namely electronic voting. I
think "intuitive
> cryptography" is a very important open problem for
our field.

The first problem of voting is that neither side (paper vote
vs e-vote)
accepts that voting is hard to do right -- and that we have
not done
it yet. Paper is not the "gold standard" of
voting.

The real-world voting problem is actually much harder than
people think.
Voting is an open-loop process with an intrinsic "vote
gap", such that
no one may know for sure what the vote cast actually was --
unless one
is willing to sacrifice the privacy of the vote. This
problem is
technology-agnostic.

A solution [1], however, exists, where one can fully
preserve privacy
and security, if a small (as small as you need) margin of
error is
accepted. Because the margin of error can be made as small
as
one needs and is willing to pay, it is not really relevant.
Even when
all operational procedures and flaws including fraud and
bugs are
taken into account.

The solution seems fairly intuitive. In fact, it was used
about 500
years by the Mogul in India to prevent fraud.

The solution is also technologically neutral, but has more
chances for
success, and less cost, with e-voting.

Best,
Ed Gerck

[1] In Shannon's cryptography terms, the solution reduces
the probability
of existence of a covert channel to a value as close to zero
as we want.
This is done by adding different channels of information, as
intentional
redundancy. See http://www.vote.caltech.edu/wote01/pdfs/gerck-witness.p
df
I can provide more details on the fraud model, in case of
interest.

------------------------------------------------------------
---------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography"
to majordomometzdowd.com

[Perry, please use this one if possible]

Matt Blaze wrote:
> an even more important problem
> than psychic debunking, namely electronic voting. I
think "intuitive
> cryptography" is a very important open problem for
our field.

Matt,

You mentioned in your blog about the crypto solutions for
voting and
that they have been largely ignored. The reason is that they
are either
solutions to artificially contrived situations that would be
impractical
in real life, or postulate conditions such as threshold
trust to protect
voter privacy that would not work in real life.
Technology-oriented
colleagues are not even aware why threshold trust would not
work in
elections.

Thus, the first problem of voting is that neither side
(paper vote vs
e-vote accepts that voting is hard to do right -- and that
we have not
done it yet.

The real-world voting problem is actually much harder than
people think.

Voting is an open-loop process with an intrinsic "vote
gap", such that
no one may know for sure what the vote cast actually was --
unless one
is willing to sacrifice the privacy of the vote. This
problem is
technology-agnostic.

A solution [1], however, exists, where one can fully
preserve privacy
and security, if a small (as small as you need) margin of
error is
accepted. Because the margin of error can be made as small
as
one needs and is willing to pay, it is not really relevant.
Even when
all operational procedures and flaws including fraud and
bugs are
taken into account.

The solution seems fairly intuitive. In fact, it was used
about 500
years by the Mogul in India to prevent fraud.

The solution is also technologically neutral, but has more
chances for
success, and less cost, with e-voting.

Best,
Ed Gerck

[1] In Shannon's cryptography terms, the solution reduces
the probability
of existence of a covert channel to a value as close to zero
as we want.
The covert channel is composed of several MITM channels
between the voter
registration, the voter, the ballot box, and the tally
accumulator. This
is done by adding different channels of information, as
intentional
redundancy. See http://www.vote.caltech.edu/wote01/pdfs/gerck-witness.p
df
I can provide more details on the fraud model, for those who
are
interested.

------------------------------------------------------------
---------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography"
to majordomometzdowd.com

| ...I agree with you about intuitive cryptography.  What
you're
| complaining about is, in effect, "Why Johnny Can't
Hash".  There was
| another instance of that in today's NY Times.  In one of
the court
| cases stemming from the warrantless wiretapping, the
Justice
| Department is, in the holy name of security, effectively
filing court
| papers with itself -- it's depositing the
"filings" in a secure
| facility, rather than with the court, to protect them.  I
won't go
| into the legal, political, judicial, or downright bizarre
aspects of
| this case (save to note that one of the plaintiff's
attorneys was
| quoted as saying "Sometime during all of this, I went
on Amazon and
| ordered a copy of Kafka?s ?The Trial,? because I needed a
refresher
| course in bizarre legal procedures."), but one point
the article
| mentioned is relevant here:  how is the record preserved
for a
| possible appeal?  Indeed, one of the judges involved has
commented on
| that point.
| 
| ...There's an obvious cryptographic solution, of course:
publish the
| hash of any such documents.  Practically speaking, it's
useless.  Apart
| from having to explain hash functions to lawyers, judges,
members of
| Congress, editorial page writers, bloggers, and talk show
hosts,...
This is a common misconception.  The legal system does not
rely on
lawyers, judges, members of Congress, and so on
understanding how
technology or science works.  It doesn't rely on them coming
to accept
the trustworthiness of the technology on any basis a
technologist would
consider reasonable.  All it requires is that they accept
the authority
of experts in the subject area, and that those experts agree
"strongly
enough" that the mechanism is sound.

How many people understand DNA matching?  How much do you
think *you*
understand about DNA matching?  Could you name a single
reagent used in
doing a DNA match?  Could you distinguish between a good
match and a bad
match?  If someone handed you one of those pictures of
different bands
on an electrophoresis plate, could you tell if it was real
or faked?
Does any of this influence your faith in the validity of DNA
matching as
a forensic technology?

Just as DNA matching can be explained in very simple, if
fundamentally
very limited terms, as something like fingerprint matching
only more
sophisticated, one can easily explain hashing in pretty much
the same
terms.  It would not be hard to find highly credentialed
experts who
would testify as to the worth, applicability, and general
acceptance by
those in the field, of the technique.  Sure, lawyers on the
other side
of a case trying to gain acceptance for hashing could
probably find
*someone* to cast doubt on it - but it's unlikely they would
be very
good expert witnesses - and in the end that's what
determines the
outcome.

| this a time you'd want to stand up before a Congressional
committee and
| testify that some NSA technology, i.e., SHA-512, that NIST
thinks needs
| replacing, is still strong enough to protect documents
that concern
| possible NSA misconduct?  And of course, collision attacks
are
| precisely the concern here.
Well, there will always be tin-hatters out there who will
doubt
absolutely everything.  We rely on the police to hold on to
evidence
concerning the people charged with crimes - who are
sometimes corrupt
cops, politicians who control police funds, etc., etc. 
There are
procedural safeguards around the chain of custody of
materials.

When it comes to records of decided cases, the courts hold
on to this
stuff.  Just how secure are *their* facilities?  There is
rarely reason
for anyone to mount a concerted attack against them.  If
you're worrying
about the NSA modifying stored evidence, what makes you
think they would
have much trouble mounting a black-bag attack against some
court's
storage room somewhere?

There are a number of very troubling issues about this
series of cases
and the way the courts have allowed them to be handled (so
far; history
shows that the courts, just like the other branches of
government, are
very protective of what they perceive as their domain of
responsibility,
and they tend to take back their roles).  But I'm not
particularly
concerned about the NSA using some secret technique to find
a second
preimage of a hash of the evidence.  Of course, the
practical
difficulties of even getting to the point of being able to
compute a
hash over a large collection of papers, books, various kinds
of records,
and likely some other pieces of physical evidence is
considerable....

							-- Jerry

------------------------------------------------------------
---------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography"
to majordomometzdowd.com

On Tue, 30 Jan 2007 16:10:47 -0500 (EST)
"Leichter, Jerry" <leichter_jerroldemc.com> wrote:

>

> | 
> | ...There's an obvious cryptographic solution, of
course: publish the
> | hash of any such documents.  Practically speaking,
it's useless.
> | Apart from having to explain hash functions to
lawyers, judges,
> | members of Congress, editorial page writers,
bloggers, and talk
> | show hosts,... 

> This is a common misconception.  The legal system does
> not rely on lawyers, judges, members of Congress, and
so on
> understanding how technology or science works.  It
doesn't rely on
> them coming to accept the trustworthiness of the
technology on any
> basis a technologist would consider reasonable.  All it
requires is
> that they accept the authority of experts in the
subject area, and
> that those experts agree "strongly enough"
that the mechanism is
> sound.

I don't dispute your analysis.  However, this case is not
just a legal
one, it's a political issue, which is why I spoke of
"editorial page
writers, bloggers, and talk show hosts".  All it will
take is for
enough technically-skilled conspiracy theorists to raise the
issue of
hash function collisions and NSA, and we won't hear the end
of it for
decades to come.  (Did you know that President Kennedy was
actually
killed by a large prime factor discovered by the CIA...?)



		--Steve Bellovin, http://www.cs.columbi
a.edu/~smb

------------------------------------------------------------
---------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography"
to majordomometzdowd.com

On Jan 30, 2007, at 16:41, Steven M. Bellovin wrote:

> On Tue, 30 Jan 2007 16:10:47 -0500 (EST)
> "Leichter, Jerry" <leichter_jerroldemc.com> wrote:
>
>>
>
>> |
>> | ...There's an obvious cryptographic solution, of
course: publish  
>> the
>> | hash of any such documents.  Practically
speaking, it's useless.
>> | Apart from having to explain hash functions to
lawyers, judges,
>> | members of Congress, editorial page writers,
bloggers, and talk
>> | show hosts,...
>
>> This is a common misconception.  The legal system
does
>> not rely on lawyers, judges, members of Congress,
and so on
>> understanding how technology or science works.  It
doesn't rely on
>> them coming to accept the trustworthiness of the
technology on any
>> basis a technologist would consider reasonable. 
All it requires is
>> that they accept the authority of experts in the
subject area, and
>> that those experts agree "strongly
enough" that the mechanism is
>> sound.
>
> I don't dispute your analysis.  However, this case is
not just a legal
> one, it's a political issue, which is why I spoke of
"editorial page
> writers, bloggers, and talk show hosts".  All it
will take is for
> enough technically-skilled conspiracy theorists to
raise the issue of
> hash function collisions and NSA, and we won't hear the
end of it for
> decades to come.  (Did you know that President Kennedy
was actually
> killed by a large prime factor discovered by the
CIA...?)

Yes, and randomized hashes (which many of these applications
require
to make them secure) seem especially likely to invite this
sort of
ill-informed -- but intuitively attractive -- speculation.

-matt

------------------------------------------------------------
---------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography"
to majordomometzdowd.com

| > | 
| > | ...There's an obvious cryptographic solution, of
course: publish the
| > | hash of any such documents.  Practically speaking,
it's useless.
| > | Apart from having to explain hash functions to
lawyers, judges,
| > | members of Congress, editorial page writers,
bloggers, and talk
| > | show hosts,... 
| 
| > This is a common misconception.  The legal system
does
| > not rely on lawyers, judges, members of Congress, and
so on
| > understanding how technology or science works.  It
doesn't rely on
| > them coming to accept the trustworthiness of the
technology on any
| > basis a technologist would consider reasonable.  All
it requires is
| > that they accept the authority of experts in the
subject area, and
| > that those experts agree "strongly enough"
that the mechanism is
| > sound.
| 
| I don't dispute your analysis.  However, this case is not
just a legal
| one, it's a political issue, which is why I spoke of
"editorial page
| writers, bloggers, and talk show hosts".  All it will
take is for
| enough technically-skilled conspiracy theorists to raise
the issue of
| hash function collisions and NSA, and we won't hear the
end of it for
| decades to come.  
I doubt *anything* would eliminate the conspiracy theorists.
 Intuitive
cryptography or otherwise, any convincing argument that the
records
had *not* been tampered with would require careful
examination - and
conspiracy theorists don't carefully examine evidence
*against* their
positions.

|		    (Did you know that President Kennedy was actually
| killed by a large prime factor discovered by the CIA...?)
Actually, it's well known that aliens controlled both Lee
Harvey Oswald
and Jack Ruby - their control over Ruby was slipping, he was
about to go
public revealing what he know, so having Ruby kill Oswald
did a great
job of covering up the ongoing invasion.

These aliens presented a take-it-or-leave it surrender
document to
President Truman at Area 51 shortly after WW II.  Kennedy
was about to
start an aggressive campaign against them - as, later was
Robert
Kennedy, which is why the aliens arranged his death,
too....

							-- Jerry 

(What was the name of the TV series a number of years back
that was
built on this premise?  Not very good, but cleverly done.)

| 
| 
| 		--Steve Bellovin, http://www.cs.columbi
a.edu/~smb
| 
| 

------------------------------------------------------------
---------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography"
to majordomometzdowd.com

I am not convinced that we need intuitive cryptography.  
Many things in life are not understood by the general
public.
How does a car really work: most people don't know but they
still drive one.
How does a microwave oven work?

People don't need to understand the details, but the high
level concept
should be simple:  If that is what you are trying to convey,
I agree with
you.

I guess we could very well do with some cryptographic
simplifications.  Hash
functions are one example.  We have security against
arbitrary collisions,
2nd pre-image resistance, preimage resistance.  Most of our
hash functions
today don't satisfy all of these properties:  "Oh SHA1
is vulnerable to
aribitrary collisions attacks, but it is still safe agains
2nd pre-image
attacks, so don't worry!" 
Why do we need all of these properties?  In most cases, we
don't.
Mathematical masturbation might be to blame?   
Block cipher encryption.  How many modes of operations
exist?  Some use a
counter, others need a random non predictable IV, others
just need a non
repeatable IV?  Do we need all of this?
I often find myself explain these concepts to
non-cryptographers.  I'm often
taken for a crazy mathematician.

What is the length of a private key?  In 1024-bit RSA, your
d is about 1024
bits.  But is d your private key, or is it (d,N),  in which
case there is
more than 1024 bits!  No, N is public, the known modulus,
but you need it to
decrypt, you can't just use d by itself.  Oh, in DSA the
private key is much
shorter.  You actually also need a random k, which you can
think of as part
of your key, but it's just a one time value.  Are we talking
about key
lengths, of modulus lengths really?

When you encrypt with RSA, you need padding.   With Elgamal,
you don't need
any, complicated story.  And don't use just any padding. 
You would be
foolish to use PKCS#1 v1.5 padding, everybody knows that
right?  Use OAEP.
It is provably broken, but works like a charm when you
encrypt with RSA!

Going back to the million dollar paranormal challenges: 
Something like a
Windows SAM file containing the NTLM v2 hash of the
passphrase consisting of
the answer might be something to consider?  Not perfect
but...

--Anton




-----Original Message-----
From: owner-cryptographymetzdowd.com
[mailto:owner-cryptographymetzdowd.com] On Behalf Of
Matt Blaze
Sent: January 26, 2007 5:58 PM
To: Cryptography
Subject: Intuitive cryptography that's also practical and
secure.

I was surprised to discover that one of James Randi's
"million dollar
paranormal challenges" is protected by a surprisingly
weak (dictionary-
based) commitment scheme that is easily reversed and that
suffers from
collisions. For details, see my blog entry about it:
    htt
p://www.crypto.com/blog/psychic_cryptanalysis/

I had hoped to be able to suggest a better scheme to Randi
(e.g., one
based on a published, scrutinized bit commitment protocol). 
 
Unfortunately
I don't know of any that meets all his requirements, the
most important
(aside from security) being that his audience
(non-cryptographers
who believe in magic) be able to understand and have
confidence in it.

It occurs to me that the lack of secure, practical crypto
primitives and
protocols that are intuitively clear to ordinary people may
be why
cryptography has had so little impact on an even more
important problem
than psychic debunking, namely electronic voting. I think
"intuitive
cryptography" is a very important open problem for our
field.

-matt

------------------------------------------------------------
---------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography"
to majordomometzdowd.com

------------------------------------------------------------
---------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography"
to majordomometzdowd.com

----- Original Message ----- 
From: "Andrea Pasquinucci" <cesareucci.it>
To: "Cryptography" <cryptographymetzdowd.com>
Sent: Tuesday, January 30, 2007 12:33 PM
Subject: Re: Intuitive cryptography that's also practical
and secure.


> I have been working for
> the last 2 years on a project about web-voting
> (http://eballot.ucci.it/)

> PS. any comment on my protocol/system is greatly
appreciated.

If I'm reading the design correctly, the biggest failure I
see is that it is 
open to coersion. It is possible to hold someone's family or
other 
personally important stuff for ransom for a receipt that
reflects voting 
"correctly."
                    Joe 

------------------------------------------------------------
---------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography"
to majordomometzdowd.com