Cryptography-Digest Digest #218, Volume #13 Fri, 24 Nov 00 19:13:01 EST
Contents:
hash-breaking question ([EMAIL PROTECTED])
Re: DES question: Has this ever been proven before? (David Wagner)
Re: voting through pgp ("Trevor L. Jackson, III")
Re: Entropy paradox (John Savard)
Re: Entropy paradox ("Matt Timmermans")
Re: A Simple Voting Procedure (Dan Oetting)
Re: Mode of operation to maintain input size with block ciphers? (Jerry Leichter)
ElGamal ("Chris Loeser")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: hash-breaking question
Date: Fri, 24 Nov 2000 20:40:01 GMT
I have a question regarding the security of cryptographic hash
functions such as SHA-1.
If I hash a secret value X and a known salt value Y with cryptographic
hash algorithm H, and then I hash X and a known salt value Z with H,
can the known values H(X|Y), Y, H(X|Z), and Z be used by an attacker to
efficiently recover the secret value X?
Thanks.
Adam Pritchard
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: DES question: Has this ever been proven before?
Date: 24 Nov 2000 21:00:36 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
Francois Grieu wrote:
>The only "drawback" I can think compared to my previous technique
>is that the X and Y found by cycle-finding look random, when mine
>tend to be 0 (or some choosen value) in the left half.
If you want X and Y to be 0 in the left half (or some fixed value),
you can adapt the parallel collision search algorithm to this case,
too. Let trunc_n(x) denote the first n bits of x, and x||y denote
the concatenation of x and y. Then you can define
f(X) = 0 || trunc_32(DES_k(X) xor X)
and iterate f until you find a collision. (This is the basic idea,
and it can be tweaked a little bit to improve the constant factors,
I think.)
>It still seems possible to use a bitsliced DES implementation
Yes, you can just have 64 independent iterations of f proceeding
in parallel. This is just a simulation on a single machine of a
64-parallelized-execution, and it works because the van Oorschot
and Wiener algorithm parallelizes nicely.
------------------------------
Date: Fri, 24 Nov 2000 16:07:45 -0500
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: voting through pgp
David A Molnar wrote:
> Dan Oetting <[EMAIL PROTECTED]> wrote:
> > "Scott Fluhrer" wrote:
> >> Actually, the idea of digital coins would seem to fill the bill nicely.
>
> > One Dollar - One Vote! The concept sounds familiar :)
>
> I'm sure I've seen that in a paper somewhere before...oh, wait.
>
> Most of the talk about electronic voting I've seen so far seems to center
> on the (very real) problems involved with using home PCs as a client
> platform. Some secondary talk on what the requirements for a voting
> scheme would be (c.f. other thread here).
>
> What I haven't seen yet is a discussion of electronic voting with
> specific reference to the problems in the Florida election.
> What are the problems with the Florida election which have the U.S. tied
> up in knots right now? Are there problems ones which can be addressed by
> electronic voting in some form, or by using cryptographic ideas?
>
> Following the California commission, I'm going to discount electronic
> voting from home entirely. When I refer to "electronic voting," I will
> mean something like an electronic voting machine connected via a network
> to some tabulating agency.
>
> Off the top of my head, the following problems (either alleged or
> confirmed) with the Florida election come to mind:
>
> * Election "results" called too early. This is a polling problem
> and a news network problem, but it points the way to a potential
> voting problem. If we adopt an electronic
> voting system which allows for counting as the votes are cast,
> we'd have to make sure that the results didn't leak until
> after the close of the polls. This might be difficult.
IMHO "calling" the election is the expression of an opinion rather than fact.
Reporting the votes tallied so far would be reporting facts. If the news
media avoided reporting opinions and reported only the facts then their
reports would tend to _increase_ the turnout in the precincts still open
rather than discouraging it.
>
>
> * The infamous "butterfly ballot." This seems a user interface
> issue as much as anything else. Which probably means that the
> people reading sci.crypt are the last people who should be
> involved. :-)
>
> I don't see how electronic voting would be better than a well
> designed ballot, unless maybe you have a computer in the voting
> booth which reads the names of candidates to you.
The issue that can be addressed by active ballots is that of confirmation --
immediate feedback to the voter. The problem we'd like to avoid is a voter
exiting the booth thinking he has cast votes a certain way and finding out
later that the vote counting system tallied his votes a different way. This
problem derives from voter confusion and ballot ambiguity. Active ballots can
address both problems.
An active ballot can provide an unambiguous summary display of the votes to be
cast. When the voter executes the commit action the votes are not subject to
further interpretation by any agency, including the voter, election officials,
or courts.
>
>
> * Ballots which are in themselves difficult or impossible to
> accurately count.
> - Dimpled ballots and half-punched-out chads.
> - Ballots with votes for two or 0 candidates.
> - Ballots with food stains (John Leo references these in
> U.S. News and World Report; I don't know how many
> actually exist or if he was being sarcastic)
>
> Again this is a user interface issue, and we don't seem to
> need electronic voting, strictly speaking. We can build
> mechanical mechanisms which enforce only voting for one
> candidate (radio buttons), do not register a vote until
> all offices have a vote, etc. There's probably lots of
> tricky issues involved, but I don't see that we need
> electronic voting. Maybe a system in which the ballot is
> marked by a mechanical mechanism and then available for
> inspection by the voter before finally being deposited
> would work -- but what happens when they silently
> malfunction and no one notices?
>
> * Intimidation or unreasonable requirements to vote at the
> polling place. For example, there are reports that several
> areas of Florida required 3 distinct forms of
> state or federal photo ID to vote.
> (This seems *extremely* strange to me - in Nevada we just
> give a signature...I don't think I even have 3 forms of
> "real" photo ID)
You probably didn't have elected officials removed from office for election
fraud. Florida did. The deposed Mayor of Miami secured a position with a
political party as the person responsible for the absentee ballots that he has
used to cheat in his election. C.f., a recent post in this ng by Paul Pires.
>
>
> I don't see how electronic voting would be any better or
> worse than what we have now. I don't see how electronic
> voting at home would be any better or worse than absentee
> ballots.
>
> * The election was close enough to be influenced by absentee
> ballots. Absentee ballots were
> - later in arriving than regular votes
> - open to new ballots being "found"
> - potentially mailed by people not authorized to
> mail them to voters
>
> If we rule out electronic voting by home PC, I don't see
> a good way to solve this with electronic voting. As for
> people introducing fradulent absentee ballots, that seems
> to be a problem in creating logs and cross checks.
>
> * Recounts by machine are less reliable than recounts by
> hand.
What units are you using for reliability? I suspect machine tallies are more
repeatable than human tallies. I suspect this repeatability is a foundation
for accuracy and thus trust.
>
> * Recounts may alter ballots, possibly by shaking out chads.
> * Hand recounts are the most reliable kind of recount, but
> hand recounts cannot be completed before the certification
> deadline.
Again what is your definition of reliable?
>
> * Counts and recounts are inconsistent with each other, leading
> to charges of fraud.
> * Ballots just "show up" having been accidentally not submitted
> for tabulation on Election Day.
> * Ballots can be spoiled or changed during counting.
>
> This seems the really crucial point. The suits before various
> courts seem to grow out of disputes over the recounting process.
> Produce a better counting and recounting, and we prevent a
> second Florida.
> (of course, the new system will probably fail spectacularly some
> new way. generals fight the last war, Maginot line, and all that)
>
> Electronic voting *may* be a win over paper ballots in this case,
> but only if the tallying system can be constructed in such a way
> that its workings are publically verifiable. This is the
> "transparency" point others have made in other threads: current
> paper systems allow everyone to watch the ballots being counted
> *and believe that they are watching the ballots being counted.*
>
> An ideal system would have a method of recount which is at least
> as reliable as today's hand recounts. It would also have totals
> consistent from count to count...
Perhaps a voter could submit his ballot to a machine within the voting booth.
Said machine would indicate the "official" interpretation of the ballot. If
the voter approves than there would be no basis for altering the official
interpretation of that ballot.
Feedback to the voter that enables the ballot interpretation to occur prior to
the voter exiting the voting booth seems to be key in eliminating the voter
confusion and ballot interpretation issues.
>
>
> An electronic voting system with voting machines connected
> directly to a tabulation center might address the "forgotten
> ballots" problem. It would also raise questions about privacy
> and transparency which might be addressed via cryptography.
> But how to actually implement all this?
>
> This begins to look like a software and hardware engineering
> problem. Which is not encouraging.
>
> What other problems were there in the Florida election which I'm
> forgetting? and what, if anything, do electronic voting and cryptography
> have to address these problems?
Electronic processing might close the temporal gap that attends absentee and
overseas ballots. Consider a ballot transport system designed around secure
comm protocols that allowed a person to submit their ballot to an out-of-state
or overseas polling booth within the normal voting hours on election day. The
booth would cryptographically secure the contents of the ballot for immediate
delivery to the home-state election counting mechanism. POst offices could
offer the facility.
Is crypto up to providing the security equivalent to a postmarked and signed
hardcopy document? In the minds of the voters?
To pick on an eminent authority, B. Silverman has communication issues with a
non-trivial fraction of the posters in this forum. Imagine the conversation
given an audience of ancient Floridians. Perhaps the present systems is not
as bad as some alternatives.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Entropy paradox
Date: Fri, 24 Nov 2000 21:11:13 GMT
On Fri, 24 Nov 2000 18:58:24 +0100, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote, in part:
>Where does the (almost n fold)
>amplification in terms of G from s to n*t come from? It
>must come from somewhere, isn't it? That's the essence
>of the paradox I originally posted.
Nope.
Entropy must come from somewhere.
G doesn't have that problem.
Once you have _enough_ entropy to avoid a brute force search, then you
can produce all the G you want, to encipher any amount of data,
however large, provided you use a cipher sufficiently resistant to
cryptanalysis.
Producing bits that can't be predicted from an external analysis, in
any number, is also no problem, as that is equivalent.
But to avoid brute force search, G isn't good enough; only real
entropy will do. Hence, real entropy isn't without practical
implications.
The thing G lacks that entropy has is _precisely_ what makes it
necessary for entropy to 'come from somewhere'. No paradox, but a
perfect fit.
Perhaps the problem you're having is in seeing what it means for a
sequence to be unpredictable. It just means that a cryptanalyst can't
grab hold of a chunk of it, and use that chunk somehow to work back to
the rule for generating it - the key.
It doesn't mean the sequence has an endless amount of real novelty,
just that the small key behind the scenes (which is always open to
brute-force searching) can't be reached. So the sequence is
effectively novel, because the cryptanalyst was not able enough to
reach the means of predicting it.
Part of the wall keeping the cryptanalyst out - and allowing G to
reach a high value - is an entropy large enough to prevent brute-force
search, and another part is the strength of the cipher. Obtaining a
large G from a small key is precisely what all conventional ciphers,
other than the one-time pad, are for.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: "Matt Timmermans" <[EMAIL PROTECTED]>
Subject: Re: Entropy paradox
Date: Fri, 24 Nov 2000 16:26:33 -0500
Reply-To: "Matt Timmermans" <[EMAIL PROTECTED]>
Mok-Kong Shen <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
Where does the (almost n fold)
> amplification in terms of G from s to n*t come from? It
> must come from somewhere, isn't it? That's the essence
> of the paradox I originally posted.
Why do you think that there must be a law of conservation of G? It clearly
isn't true. That's not a paradox -- it's just the way things are.
------------------------------
From: Dan Oetting <[EMAIL PROTECTED]>
Subject: Re: A Simple Voting Procedure
Date: Fri, 24 Nov 2000 16:01:35 -0700
In article <[EMAIL PROTECTED]>, David Schwartz
<[EMAIL PROTECTED]> wrote:
> Dan Oetting wrote:
> >
> > In article <[EMAIL PROTECTED]>, David Schwartz
> > <[EMAIL PROTECTED]> wrote:
> >
> > > Stanley Chow wrote:
> > >
> > > > Properties under discussion:
> > > > p1) voter can prove, by himself alone, at his sole option, that
> > > > his vote is or is not correctly counted
> > > > p2) voter can be forced to reveal his vote against his will
> > > >
> > >
> > > The voter is displayed a GUID before he or she votes which he
> > > may or
> > > may not write down. He then casts his vote. Immediately after the
> > > election, all the GUIDs are released along with which way they voted.
> > > At
> > > the same time the voter votes, he is shown one GUID (that is not his)
> > > that was cast (by someone else) for each other candidate, which he
> > > may
> > > or may not write down.
> > >
> > > Why doesn't this meet 'p1' without providing 'p2'?
> >
> > If the system is rigged, the alternate GUID's could be selected from a
> > small pool known to the atacker.
>
> No system can meet the requirements if it's not implemented according
> to its specification.
An Even Simpler Voting Procedure:
1. Each voter privately enters a vote in the system.
2. At the end of the voting period the system prints the totals.
P1 is satisfied by the voter witnessing his own act of voting.
P2 is not satisfied because no one else has witnessed the act of voting
and there is no record of how an individual voted.
-- Dan Oetting
------------------------------
From: Jerry Leichter <[EMAIL PROTECTED]>
Subject: Re: Mode of operation to maintain input size with block ciphers?
Date: Fri, 24 Nov 2000 17:50:32 -0500
After posting my previous message, I realized that I was really vague
about how to handle the "all but one byte" case, and actually pointed in
a direction that doesn't work.
Here - again assuming a 128-bit block - is a method to send 15 bytes of
plaintext in exactly 15 bytes of cyphertext:
P is the plaintext
E = P || 00000000 -- expand to 128 bits with zeros
do
E = Encrypt(E)
while (bottom 8 bits of E are non-zero)
C = top 120 bits of E is the cyphertext
To decrypt, exchange P and E and replace Encrypt by Decrypt.
On average, the loop runs 128 times. If it runs more than a couple of
hundred times, you start to have real doubts about the cipher being
used.
This can be optimized by using a technique analogous to the one-byte
technique: The test in the while becomes "any byte is all zero bits,
and exactly one of the 16 values you get by removing that zero byte and
inserting a zero byte at each position among the remaining 15 decrypts
to a value with bottom byte 0." C then simply omits the selected 0
byte; the receiver has to try all the positions for re-inserting it to
find the unique one. (There's an optimization problem hiding in here:
How many "byte positions" give you the smallest expected number of
encryptions?)
Stepping back, it is worth asking just what problem is being solved
here. I would suggest that we are looking for a technique with three
properties:
1. |C| = |P| (same size plain- and cypher-text)
2. "Reasonable" number of encryptions;
3. Same security properties as the underlying encryption.
In particular, for reasonable block encryptions, changing any bit of the
key or of P, on average, flips half the bits of C. This rules out XOR
with the encryption of some constant, for example.
The techniques I outlined do require a rather strong security guarantee
on the underlying encryption: Security against adaptive chosen
plaintext attack. Given that, an attacker could compute exactly what
the sender does without any help from sender, so we can be sure we
aren't adding any new vulnerability. (Of course, *any* technique that
encrypts a short block as a short block is inherently vulnerable to a
codebook-style attack.) Fortunately, this is a security property we
expect these days.
BTW, an alternative approach for short blocks (again, say 1 byte) is:
Use the encryption - say in counter mode - as a strong PRNG. Use this
to compute a pseudo-random permutation on {0 ... 255}, and use that to
encrypt the input byte. This has the flavor of using XOR, but is
probably as strong as the original cypher - though the proof might be a
bit more complex in this case.
It's an oddity that the short and long are easy, while the intermediate
cases are hard! (Or maybe there's a clever technique for those ...
anyone?)
-- Jerry
------------------------------
From: "Chris Loeser" <[EMAIL PROTECTED]>
Subject: ElGamal
Date: Sat, 25 Nov 2000 00:47:59 +0100
Hi out there,
short question :
to sign a message I can use any public-key crypto-system the other way round
:
sign with your private key and verify with the public one.
this should work for ElGamal public key system (based on DH-key exchange)
BUT : why is there a special ElGamal Signature sheme ?
thx in advance ...
regards
Chris
mailto: [EMAIL PROTECTED]
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
