Cryptography-Digest Digest #141, Volume #13 Sat, 11 Nov 00 12:13:01 EST
Contents:
Re: Q: Computations in a Galois Field (Mok-Kong Shen)
Re: RC6 Question (Mok-Kong Shen)
Rotor Machines and Alan Turing the father of modren cryptography
([EMAIL PROTECTED])
Re: voting through pgp (Paul Crowley)
Re: voting through pgp (Timothy M. Metzinger)
vote buying... (Timothy M. Metzinger)
Re: Type 3 Feistel? (John Savard)
Re: Why remote electronic voting is a bad idea (was voting through pgp) (Roger
Schlafly)
Re: Q: Rotor machines (Steve Portly)
Re: Rotor Machines and Alan Turing the father of modren cryptography (Mok-Kong Shen)
Re: RC6 Question (Tom St Denis)
Re: voting through pgp ("John A. Malley")
Re: Why remote electronic voting is a bad idea (was voting through pgp)
([EMAIL PROTECTED])
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Q: Computations in a Galois Field
Date: Sat, 11 Nov 2000 12:40:08 +0100
Paul Crowley wrote:
>
> Mok-Kong Shen wrote:
> > My understanding of the section you mentioned is that both
> > the x to 1/x mapping and the affine transformation are
> > such that they are simple to describe and (apparently by
> > some chance) happen to be very good.
>
> The x -> 1/x thing is known to be very good; it's not coincidence, it's
> well known as a bijective S-box strongly resistant to DC and LC. Any
> affine transformation would preserve these properties; it's not hard to
> choose a simple one that achieves the few extra properties that the
> Rijndael designers wanted.
>
> Now I understand why you're asking - you want a non-interoperable
> variant! You could go for choosing a different affine function with the
> same nice properties, there should be many. I don't think I'd recommend
> messing with MixColumn, and I'd *definitely* leave ShiftRow alone.
>
> Frankly, though, your best bet is probably a simple variant of the key
> schedule; this will probably allow you to implement your variant on
> Rijndael hardware. A radically different set of round constants would
> probably do it.
>
> Unless I'm not guessing the purpose of this variant properly?
Yes. The variant that almost certainly doesn't affect the
strength of the cipher is permuting the round keys which
I mentioned in the said thread among other methods of
modifying the keyscheduling. The next fairly safe variant
is in my view modification of the affine transformation
(though one probably has to test a little bit to be sure
to capture its effect on diffusion properties). I remain
personally optimistic though that the other variants
suggested could also prove to be viable in practice for
achieving (where realizable) non-interoperability which
renders the opponent's job more difficult in a very
general and essential manner.
M. K. Shen
============================
http://home.t-online.de/home/mok-kong.shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: RC6 Question
Date: Sat, 11 Nov 2000 12:52:09 +0100
Vinchenzo wrote:
>
> In the RC6 specification one of the basics operations is defined as:
>
> "a<<<b rotate the w-bit word a to the left by the amount given by the least
> significant log2(w) bits of b." What does that mean...anybody has already
> implemented this algorithm? Please help me!
You probably have to query the authors of RC6 why they
choose the least significant bits of b instead of other
bits. A possible reason is that these bits are or are
considered to be more random. log2(2) should be clear,
since there is no sense to rotate e.g. a 32-bit word
by more than 31 bits and 5 bits provide that amount
for rotation. RC6 implementation is in AES contest, if
I am not mistaken.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED]
Subject: Rotor Machines and Alan Turing the father of modren cryptography
Date: Sat, 11 Nov 2000 12:09:54 GMT
In 1939, British intelligence, with the help of Polish spies, managed to
obtain a working replica of a new and secret coding
machine known as Enigma. Unfortunately, the Germans changed the machine
settings (the key) on a daily basis. The British
equivalent of the NSA, the Government Code and Cipher School, formed a
Top Secret group set up for the purpose of developing
a method for extracting the daily Enigma key from the morning messages,
or traffic. Alan Turing, a brilliant mathematician and
an expert in Boolean algebra, invented a computer, the Turing Bombe,
which accomplished this feat. The first encrypted messages
obtained in the morning with the new daily key (machine settings) were
fed into the Bombe and when the relays quit clicking a
clerk would read out the new key (machine settings), and then check it
on a replica of the Enigma machine. The key was then
passed on to other clerks using working replicas of the Enigma machine,
who would decrypt the German messages as they came
in for the rest of the day.
Turing derived his mathematical logic functions from a knowledge of the
internal electrical logic of the Enigma, then designed the
Bombes (the first special purpose digital computers) to do an automated
key extraction attack. When the daily key had been
derived, it was passed on for decryption with a standard Enigma machine.
The Bombes did not do exhaustive searches (of all possible keys), as
some writers have suggested. Instead, by deriving Boolean functions for
the rotor key set logic, the first messages of the day provided the
input to test for only "logical" key sets with the "illogical" sets
skipped
altogether.
This is very much the basis of modren day cryptography as practiced by
the "Pros". Much of the Work of Alan Turing has been secret and
confidential and never published to this day.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Paul Crowley <[EMAIL PROTECTED]>
Subject: Re: voting through pgp
Date: Sat, 11 Nov 2000 12:22:49 GMT
John Savard wrote:
> On Fri, 10 Nov 2000 20:25:37 GMT, [EMAIL PROTECTED] wrote, in
> part:
>
> >A much more reasonable solution would be electronic voting inside the
> >current vote booths.
>
> Even that is dangerous, because without tangible ballots, if the
> voting machines were, somehow, programmed to count incorrectly, there
> would be no way to know that.
We got on to this because of the usability problems of the Palm Beach
ballots. They're difficult to use partly because they're designed to be
counted by computer. One answer would be to put a computer in every
polling booth, but have it print your final vote onto paper which can
then be put in the ballot box by hand.
Usability can be improved: you have a big touch screen, and at the end
it shows you what you voted for and asks you to confirm before
printing. The paper trail is still there: people can check that the
piece of paper says what they think. The counting can be made faster:
barcodes can be printed on each piece of paper encoding the vote (random
votes would have to be checked to ensure the barcode matched the printed
representation).
It's expensive, though. I think it might be overkill for current
ballots (the UK system of nice, clear ballots and hand counting works
fine) but it would be *very* useful if we ever wanted to introduce some
fairer voting system, like Condorcet
(http://russp.org/electionmethods.org/), which asks voters to rank
candidates in order of preference. Otherwise I think voters might get
too confused trying to fill out the preferences grid, and counting would
take too long.
--
__
\/ o\ [EMAIL PROTECTED]
/\__/ http://www.cluefactory.org.uk/paul/
------------------------------
From: [EMAIL PROTECTED] (Timothy M. Metzinger)
Subject: Re: voting through pgp
Date: 11 Nov 2000 14:16:02 GMT
In article <[EMAIL PROTECTED]>, Paul Crowley
<[EMAIL PROTECTED]> writes:
>Usability can be improved: you have a big touch screen, and at the end
>it shows you what you voted for and asks you to confirm before
>printing. The paper trail is still there: people can check that the
>piece of paper says what they think. The counting can be made faster:
>barcodes can be printed on each piece of paper encoding the vote (random
>votes would have to be checked to ensure the barcode matched the printed
>representation).
Here in northern virginia, our vote process has a ballot where you push a
button for the candidates you choose, the button lights up. the internal logic
does not permit you to vote for two candidates for the same office (i.e. if I
push gore, than bush, only the last selection registers). Once your selection
is final, you then push a big VOTE button on the bottom, and your vote is
recorded (not sure whether it increments a counter or makes a physical mark on
a tape or what).
Nearly impossible to get confused, easy to check your vote and correct any
mistakes.
This "punching" stuff is nuts.
Timothy Metzinger
Commercial Pilot - ASMEL - IA AOPA Project Pilot Mentor
'98 M20J - N1067W
Pipers, Cessnas, Tampicos, Tobagos, and Trinidads at FDK
------------------------------
From: [EMAIL PROTECTED] (Timothy M. Metzinger)
Subject: vote buying...
Date: 11 Nov 2000 14:16:03 GMT
All I have to say about "buying a vote" is that it's MY vote, and if I wish to
sell it (I don't), I can.
Timothy Metzinger
Commercial Pilot - ASMEL - IA AOPA Project Pilot Mentor
'98 M20J - N1067W
Pipers, Cessnas, Tampicos, Tobagos, and Trinidads at FDK
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Type 3 Feistel?
Date: Sat, 11 Nov 2000 15:49:38 GMT
On Sat, 11 Nov 2000 12:04:47 +0100, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote, in part:
>Intuitively I would think that the balanced one should
>be better, with everything else being equal. Are there
>concrete reasons against this view? Thanks.
I tend to agree that the target-heavy version could be weaker, since
it limits the size of the input to the f-function.
And if the number of rounds is kept constant, the source-heavy version
modifies each part of the block fewer times.
But if one were to:
use three-quarters of the block as input into an f-function that
thoroughly mixes that input,
have an output from the f-function that is the size of the input, and
apply it to the other part of the block through a mixture of addition
and XOR, with in-line S-boxes in between, and
double the number of rounds compared to a standard Feistel cipher, so
that each part of the block is modified the same number of times (but
more thoroughly each time)
I would think that capable of providing a very strong design. But it
might be as slow as a Feistel cipher with two or three times as many
rounds, and thus whether or not it was worthwhile would be questioned.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: Roger Schlafly <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: Why remote electronic voting is a bad idea (was voting through pgp)
Date: Sat, 11 Nov 2000 08:33:11 -0800
David Hopwood wrote:
> binary digit wrote:
> ? Imagine if everyone had pgp in the world and voted through pgp, every
> ? single vote could be verified and everyone would be happy,
>
> Problems with remote electronic voting systems (in no particular order):
> 1. obtaining voter anonymity *and* adequate authentication,
> 2. vote buying and coercion,
> 3. authenticating computers and not individual voters is not sufficient,
> 4. targetted denial of service,
> 5. verifiability of software and hardware,
> 6. some voters may have problems with electronic interfaces that they
> would not have with paper ballots,
> 7. attacks against insecure end-points (both voters' PCs, and servers),
> 8. there is arguably more scope for *undetectable* corruption than in
> a paper-based system,
> 9. existing weaknesses in paper-based systems [*1] are magnified if
> voting is remote and anonymous, because it is easier to get away
> with attacks,
> 10. bias due to poorer social groups having less access to computers.
>
> It might be possible to address 1, 2, and possibly 3 by a cryptographic
> protocol, and 6 by careful interface design [*2], but I don't see the
> other problems being solved any time soon, if they are solvable at all.
I don't see how you can do (1) by a crypto protocol. In Calif (and
everywhere else?) a voter can register with a postcard and then vote
in person with no ID at all. The only thing that keeps the system honest
is that very few people are willing to violate federal election law
in person and in front of witnesses just to get one lousy vote.
With a PGP-type approach, there are various authentication methods
possible, such as certs. But ISTM it would be a much greater burden
on the voter, requiring special ID and registration requirements.
And all it would take would be some flawed CA procedure, and someone
will anonymously vote 1000s of times. I just don't see how you'd
manage the fraud problem. (But go ahead and make suggestions.)
------------------------------
From: Steve Portly <[EMAIL PROTECTED]>
Subject: Re: Q: Rotor machines
Date: Sat, 11 Nov 2000 11:27:51 -0500
Mok-Kong Shen wrote:
> John Savard wrote:
> >
> > Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> >
> > >I remember having seen elsewhere several people claiming to
> > >have good computer simulations of rotor machines. If the
> > >rotors are not for the normal natural language alphabet but
> > >for a larger alphabet of 256 characters (8-bit ASCII) and if
> > >there are a fairly large number, say 16 or more, of rotors,
> > >how easy is it nowadays to crack such a system with computers?
> >
> > That depends. A simple rotor system, where the rotors move in odometer
> > fashion, won't be saved by having 256-contact rotors or 16 rotors,
> > since the isomorph method could still be used.
> >
> > Let the rotor wirings be a function of the key and IV; let the motion
> > of the rotors be controlled by something like RC4; then you'll have a
> > system strong enough to withstand modern attack, I think.
>
> Yes, paremetrization (dependency of the algorithm upon the
> key) and using a pseudo-random stream to dynamically control
> (affect) other encryption operations are fruitful ideas in
> my conviction, though this seems to be largely ignored or
> be against the prevailing opinions of the current crypto
> schools. (I have tried these in my own humble designs.)
>
As you pointed out these systems would be secure for even short messags.
Perhaps we need to set more parameters to answer this question?
I was hoping we could gently explore the possible implications of modern
computers that don't use binary digits.
>
> > >P.S. A recent article of F. L. Bauer noted that, according
> > >to dpa, Prince Andrew, who presented on 18th Sep an original
> > >Enigma to the prime minister of Poland, Jerzej Buzek,
> > >stressed that the crypto experts of the Allies would not
> > >have broken the encryption of the German military, had there
> > >not been the help from the Polish scientists.
> >
> > This is true, although it might seem debatable. The British made many
> > advances, and accomplished impressive feats beyond anything the Poles
> > had done. But they might never have gotten started without the Polish
> > contribution.
>
> The paper mentioned also the interesting fact that two of
> the Poles, after they arrived GB through a difficult journey
> from France, were not allowed to participate in the British
> work, apparently on the reasoning that their starting help
> had already been sufficient for Bletchley Park to continue
> all itself.
>
> M. K. Shen
> -------------------------
> http://home.t-online.de/home/mok-kong.shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Rotor Machines and Alan Turing the father of modren cryptography
Date: Sat, 11 Nov 2000 17:44:20 +0100
[EMAIL PROTECTED] wrote:
>
[snip]
>
> This is very much the basis of modren day cryptography as practiced by
> the "Pros". Much of the Work of Alan Turing has been secret and
> confidential and never published to this day.
See however
http://www.pro.gov.uk/news/InTheNews/Enigma/Enigma1.htm
M. K. Shen
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: RC6 Question
Date: Sat, 11 Nov 2000 16:35:57 GMT
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
>
> Vinchenzo wrote:
> >
> > In the RC6 specification one of the basics operations is defined as:
> >
> > "a<<<b rotate the w-bit word a to the left by the amount given by
the least
> > significant log2(w) bits of b." What does that mean...anybody has
already
> > implemented this algorithm? Please help me!
>
> You probably have to query the authors of RC6 why they
> choose the least significant bits of b instead of other
> bits. A possible reason is that these bits are or are
> considered to be more random. log2(2) should be clear,
> since there is no sense to rotate e.g. a 32-bit word
> by more than 31 bits and 5 bits provide that amount
> for rotation. RC6 implementation is in AES contest, if
> I am not mistaken.
The only reason they chose the five lsb bits is to increase software
speed throughput.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "John A. Malley" <[EMAIL PROTECTED]>
Subject: Re: voting through pgp
Date: Sat, 11 Nov 2000 08:51:34 -0800
[EMAIL PROTECTED] wrote:
[snip]
>
> The real question, then, is whether electronic voting is more or less
> secure than absentee voting by mail. Can it eliminate some of the
> risks, or are new ones introduced?
>
A key "security" feature of physically voting in front of others who are
voting at a location where the State gathers the votes and checks for
voter authenticity may be missing from the electronic voting protocols
as well as absentee voting.
Are there cryptographic protocols for message exchange between voters
and the vote gatherer such that any or all voters can "witness" one
another's act of voting, and the vote gatherer can authenticate each
voter, and the voters can authenticate each other as well as the voter
gatherer?
This scenario is similar to the physical voting experience in front of
neighbors at the State-sanctioned polling booth.
John A. Malley
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Why remote electronic voting is a bad idea (was voting through pgp)
Date: 11 Nov 2000 09:08:33 -0800
Zero-Knowledge MIME Encapsulated Message
--863VMV5X2OHQZ16CHSJDHZZF0RR
Content-Type: text/plain
David Hopwood <[EMAIL PROTECTED]> writes:
> Problems with remote electronic voting systems (in no particular order):
These should be evaluated against the increasing use of remote
non-electronic voting systems, i.e. absentee ballots. A substantial
and growing percentage of votes are cast absentee in the US. The
state of Oregon did its entire ballot absentee this year.
> 1. obtaining voter anonymity *and* adequate authentication,
Not an issue, compared to absentee ballots.
> 2. vote buying and coercion,
Not an issue, compared to absentee ballots.
> 3. authenticating computers and not individual voters is not sufficient,
Not an issue, compared to absentee ballots (anyone can fill out someone
else's absentee ballot).
> 4. targetted denial of service,
This is an issue, but of practicality rather than security. Balance
it against the increased ease of use for electronic voting.
> 5. verifiability of software and hardware,
Not an issue, modulo existing electronic voting systems.
> 6. some voters may have problems with electronic interfaces that they
> would not have with paper ballots,
And vice versa! Much of the motivation for going to electronic systems
is that they can be easier to use than paper ballots. Many commentators
have asked why cumbersome punch card systems are still in use when a
simple ATM style screen would be so much easier and reliable.
> 7. attacks against insecure end-points (both voters' PCs, and servers),
> 8. there is arguably more scope for *undetectable* corruption than in
> a paper-based system,
These are probably valid.
> 9. existing weaknesses in paper-based systems [*1] are magnified if
> voting is remote and anonymous, because it is easier to get away
> with attacks,
Not an issue, modulo absentee ballots.
> 10. bias due to poorer social groups having less access to computers.
They'd still keep the old system. Also, in a few years, Internet
access will become nearly universal.
> It might be possible to address 1, 2, and possibly 3 by a cryptographic
> protocol, and 6 by careful interface design [*2], but I don't see the
> other problems being solved any time soon, if they are solvable at all.
See above for a characterization of the risks compared to those already
being accepted in existing absentee systems.
> 4 is particularly tricky - when people have the option not to vote [*3],
> how do you distinguish a non-vote from a denial of service attack?
DoS attacks are a problem, but they can be detected by various forms of
monitoring. This problem has only cropped up in the last year or so,
and it may be that technical fixes will become available to significantly
reduce the impact of this problem. Allowing an extended voting period
can also help.
> It can't be done with cryptography. 10 is also a very serious problem,
> and since this effect is very difficult to quantify, it might undermine
> confidence in the validity of the election.
Any change to voting may introduce bias by making it easier for some
groups to vote. Conservatives opposed the "motor voter" law which
allowed people to register to vote automatically when they renew their
driver's licenses, because it would introduce bias by making it easier
for poor people to vote.
> [*1] For the U.S., I understand that a particular problem is the
> accuracy of electoral rolls - both people who are registered more
> than once, and a large proportion of the population who are not
> registered.
This problem is not restricted to electronic voting.
> [*2] PGP is not a particularly good example of the kind of interface
> needed; it is far too complicated. There is a paper called
> "Why Johnny can't encrypt" that describes some usability experiments
> on PGP 5.x, with rather depressing conclusions (I can't find an
> exact reference right now, but try a search engine).
The main problem was with understanding the meaning of PK crypto, that
you generate your own key but don't use it for encryption. It is not
particularly relevant to this issue.
> [*3] Although an obvious approach is to require every registered voter
> to cast a vote, which may be "no vote", I don't think that would
> be either practical or, in many countries, politically tenable.
Agreed, this would never work.
> Any remote electronic voting system would have to run in parallel
> with the existing system. It is a general rule that you can't make a
> system more secure by adding more options, because an attacker
> will just target the weakest part of the system. You also can't make
> a system more robust, even against accidental foul-ups, by adding
> more options, because it is the least robust parts that will usually
> go wrong. There are exceptions to these rules, but they are very rare.
By reducing the number of votes in the insecure part of the system you
reduce the opportunities for manipulation and fraud.
> Electronic systems in voting booths have fewer problems, although
> they are still subject to problems 5 and 6. Note that a poorly designed
> interface of an electronic voting machine is the source of some of
> the controversy in the Florida election (and there were apparently
> complaints about the interface from voters on the day, so it's not
> just after-the-fact whinging).
(Whose brilliant idea was it to put a "g" in "whine"? You don't
pronounce it, do you? It's supposed to be onomatopoeic, a word which
imitates the sound it describes. Whiny children don't use the "g"
sound.)
The Florida system was a primitive electromechanical punch card, which
limited the ballot layout options. One of the principle advantages of
a modern computerized system would be to escape those limitations
while still providing the speed and reliability of automated counting.
> There is some more discussion of this in the latest issue of RISKS
> (archived at http://catless.ncl.ac.uk/Risks/21.11.html). I particularly
> liked Lauren Weinstein's "Hacking the Vote" article.
An excessively broad satire.
> [With reference to Florida, I was astonished that postal votes are
> counted much later than the rest of the vote, and that both the media
> and politicians are happy to declare "final" results before those
> votes have even been counted. I don't want to get too far into
> off-topic politics, but that's no way to run an election. ISTM that
> the U.S. needs to put its paper-based voting procedures in order before
> making any further attempts to introduce electronic systems.]
Postal votes are not counted "much" later than the rest of the vote;
some are counted early, and some are counted late. The relatively few
votes from overseas are allowed to be counted up to a week later.
As for declaring results "final", this is a convenience because
otherwise we would have to wait for weeks before we have a result.
Technically the President is not "officially" elected until the
Electoral College has voted and the votes have been recognized by
Congress. There is normally no need to wait this long because the
outcome is practically certain, and people need to get working on the
transition.
However, across the country, there are always a certain percentage of
"final" outcomes which get reversed. These don't get much publicity
except in the local areas affected. This is the first time it has
happened at the Presidential level.
Summing up, while electronic absentee voting poses some risks, most of
the problems are already being dealt with in the existing system. And
the advantage of making voting more convenient and available to voters
cannot be neglected. Voter turnout would probably increase
dramatically under an Internet voting scheme.
The real point is that Internet voting is coming. Purists quibble
over risks that limit cryptographic certainty, not realizing how
riddled with problems existing voting systems are. County voting
offices understand how naive are romantic notions about the purity of
the traditional voting booth. They are eager to move into the modern
era.
Ob
--863VMV5X2OHQZ16CHSJDHZZF0RR--
------------------------------
** 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
******************************
