Cryptography-Digest Digest #168, Volume #13 Thu, 16 Nov 00 15:13:00 EST
Contents:
Re: Big-block cipher, perhaps a new cipher family? (Mok-Kong Shen)
Re: so many fuss about impossibility to backtrace from MD to original ("Douglas A.
Gwyn")
Re: Hitachi - on what grounds ?? ("Douglas A. Gwyn")
Re: Hitachi - on what grounds ?? (Mok-Kong Shen)
Re: vote buying... (David Schwartz)
Re: Q: fast block ciphers (David Schwartz)
Re: vote buying... ("Frog2000")
Re: vote buying... ("Frog2000")
Re: Anyone has read / poses / is found of book by M.Schroeder(not the ("John A.
Malley")
Re: Hitachi - on what grounds ?? ("Paul Pires")
Re: vote buying... (Paul Rubin)
Re: Q: fast block ciphers (Tom St Denis)
Re: vote buying... (Eric Lee Green)
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Big-block cipher, perhaps a new cipher family?
Date: Thu, 16 Nov 2000 19:32:55 +0100
Manuel Pancorbo wrote:
>
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> >
> > It is not clear in your description how the 'diffusion' is
> > achieved through stream encryption. A stream cipher encrpyts
> > each 'unit' independent of the other. The 'state' of the
> > cipher changes with each unit, but this is generally
> > independent of the content of the plaintext unit being
> > processed. So there is no 'interaction' between the units.
>
> Should I name it "stream cipher with feedback"? In my design, state
> depends on the input. Anyway, let me explain how it works.
>
> As I said the chosen unit length is 32 bits. The key (K) can be 128 to
> 256 bit long (in 32 bit steps); let's take 128 bits i.e. 4 units. The
> state vector (S) is also 4 units long.
>
> At the beginning the state vector is filled up with the key:
> S <- K
> In the forward encryption each plaintext unit is ciphered this way:
>
> P'[0] = F(P[0], S[0], S[1])
> S[1] = G(P[0], P'[0])
> .
> P'[1] = F(P[1], S[1], S[2])
> S[2] = G(P[1], P'[1])
> .
>
> And so on. The state cycles over itself (S[0], S[1], S[2], S[3], S
> [0],...). F and G are two 32-bit nonlinear functions. Both propagate
> any single bit change of the P[0] input to 16 bits on the output P'[0]
> and to 24 bits on the new state unit S[1]; in the next step S[1]
> carries the (imperfect) diffusion of P[0] again to F and G which
> amplify it to 32 bits in P'[1] (and S[2]).
>
> You can see how avalanche works forward. At the end a new encryption
> pass is performed backwards:
>
> S <- K
> .
> C[N-1] = F(P'[N-1], S[0], S[1])
> S[1] = G(P'[N-1], C[N-1])
> .
> C[N-2] = F(P'[N-2], S[1], S[2])
> S[2] = G(P'[N-2], C[N-2])
>
> The result is that any single bit change in the plaintext packet
> propagates to the full ciphertext packet (except perhaps if the change
> occurs in the last units).
>
> The point is that it doesn't really matter how F and G are built,
> provided a minimum diffusion, unlinearity and operations economy (I
> think). Anyway I can give details in a further post.
>
> >
> > You can also use any common block cipher to do chaining
> > in the forward direction and, after having processed the
> > whole file, do a second encryption pass in the backward
> > direction. (This is a known method of forcing the opponent
> > to process the whole file, as also mentioned previously in
> > several threads of the group.) In fact, the block cipher
> > is doing 'stream' encryption here if you look on the block
> > as a single 'unit' of the 'stream'.
>
> My goal is to avoid the repetitive rounds and the key scheduling of
> block ciphers, but giving the same diffusion power and disorder. If
> possible, giving the same strength ;-)
But in the scheme you described there are the functions
F and G which you don't specify in detail. If the F is
not good, you wouldn't have good diffusion. One can have
a combination of stream and block techniques. I designed
one with a block size of 640 bits driven by a PRNG with
feedback to the PRNG by hash values obtained during the
processing and with block chaining. In other words, the
state of the PRNG is influenced by the plaintext blocks
and the processing of the blocks is determined by the
PRNG outputs and the successive blocks are chained. See
my web page.
M. K. Shen
================================
http://home.t-online.de/home/mok-kong.shen
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: so many fuss about impossibility to backtrace from MD to original
Date: Thu, 16 Nov 2000 17:51:03 GMT
[EMAIL PROTECTED] wrote:
> Birthday Paradox (if you bring random people into a room, you can only
> have 20 of them on average before 2 of them have the same birthday)
That's not accurate; it's 23 people and the "averaging" is over
the ensemble of sets of 23-random-people, or better expressed:
if you randomly select a sample of 23 people from the whole
population, the probability is greater than 0.5 that at least 2
of that sample were born on the same day of the year.
Suppose a man has a drawer in which there are 100 black socks
and 100 brown socks, thoroughly mixed. It is dark so he cannot
discern the colors. How many socks must he grab from the drawer
to be certain of taking at least one matching pair of socks?
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Hitachi - on what grounds ??
Date: Thu, 16 Nov 2000 17:55:38 GMT
kihdip wrote:
> I just read this passage from an article concerning the choice of AES at
> http://www.nwfusion.com/news/2000/1016apps.html :
> "Another issue is that Hitachi last spring exerted patent
> claims over the four other algorithms (MARS, RC6,
> Serpent and Twofish). The government wants AES to
> be public-domain technology, and given that it was
> stuck in a situation of fighting Hitachi over the four
> algorithms, NIST decided to choose Rijndael, Viega
> says."
Note that that is a claim by Viega, hotly disputed by NIST.
Viega also said that Rijndael was the "weakest" of the
candidates. Sounds like someone with an axe to grind.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Hitachi - on what grounds ??
Date: Thu, 16 Nov 2000 19:55:35 +0100
John Savard wrote:
>
> Mok-Kong Shen<[EMAIL PROTECTED]> wrote:
>
> >I wonder why the other candidates of AES are deemed
> >to violate the patent, while Rijndael's ShiftRow, where a
> >cyclic shift is done, does not. Could someone explain that?
>
> The extent of the shift is fixed, not variable. Thus, not only is it
> not a manifestation of the innovation claimed by Hitachi, but the
> "swap halves" step in DES would be prior art.
Lest Hitachi comes onto further ideas of patenting based
on variability, let's note that variable block sizes,
variable keys, variable substitutions/permutations,
variable number of rounds, variable operator types,
variable parameters, variable round key orderings, variable
cipher stacks, variable processing through PRNG control
and, most generally, a variable 'structure' of the entire
encryption algorithm (see the recent thread 'The ultimate
cipher' initiated by me) have all been discussed in this
group and are therefore already prior art of crypto and
not patentable.
M. K. Shen
=================================
http://home.t-online.de/home/mok-kong.shen
------------------------------
From: David Schwartz <[EMAIL PROTECTED]>
Subject: Re: vote buying...
Date: Thu, 16 Nov 2000 11:04:01 -0800
Paul Rubin wrote:
>
> David Schwartz <[EMAIL PROTECTED]> writes:
> > > That traceability is bad even if the election officials are honest and
> > > the election is fair. Years later, Sheriff Bubba has worked his way
> > > up to being Supreme Dictator Bubba, has the election officials
> > > executed and gets the archived code numbers and uses the ballot data
> > > to locate everyone who voted against him.
> >
> > Won't work. It'll just give him the code numbers of everyone who voted
> > against him. Remember, we were talking about a case where a citizen
> > presents his electronic voting receipt to an official.
>
> Nope. Remember, Bubba already got the receipts from the voters back
> when he was still Sheriff and couldn't decode them. Now he can decode
> them and there is hell to pay.
He only got the receipts of those people who contested the vote. And he
can't even be sure that the people who present the contest are the
original voters. All he knows is that someone presented a voting receipt
for a vote for candidate X and that this vote wasn't correctly counted
for candidate X. Unless the system totally breaks down, the number of
people issuing such disputes should be very small. The disputes could
even be done anonymously. All that's needed to process the dispute are
the numbers on the voting receipt.
> > > The goal of being able to check votes after the election (to detect
> > > fraud) is in conflict with the goal of not being able to check the
> > > votes (to protect voter secrecy).
> >
> > So long as you need the voter's help to check them, you can easily meet
> > both goals.
>
> The whole point of the original Sheriff Bubba scenario was to show
> that receipts are bad even if the voter has to help decode it.
Nonesense. The voter can simply present the receipt to an official
anonymously. The offical can then see that voter number X voted for
candidate Y, and he can also see that voter number X is not in the
official count for candidate Y. He still doesn't know who voter number X
is unless that voter chooses to do things personally.
> Really though, we're talking about Star Trek solutions to a Babylon 5
> problem (I love that description but don't remember who originally
> made it).
Not at all. This is a very real and current problem and I'm confident
that solutions can be found that are significantly better than punch
cards.
DS
------------------------------
From: David Schwartz <[EMAIL PROTECTED]>
Subject: Re: Q: fast block ciphers
Date: Thu, 16 Nov 2000 11:04:56 -0800
Scott Fluhrer wrote:
> Umm, the OP asked for a block cipher. I do believe that RC4 is normally
> considered a stream cipher...
>
> --
> poncho
While a block cipher may be difficult to use as a stream cipher
(actually, it's not hard to use but hard to be sure it's secure), any
stream cipher can trivially be changed into a block cipher.
DS
------------------------------
From: "Frog2000" <[EMAIL PROTECTED]>
Subject: Re: vote buying...
Date: Thu, 16 Nov 2000 14:20:51 -0500
"Paul Pires" <[EMAIL PROTECTED]> wrote in message
news:FIUQ5.10930$[EMAIL PROTECTED]...
>
> Frog2000 <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> >
> > "Eric Smith" <[EMAIL PROTECTED]> wrote in message
> > news:[EMAIL PROTECTED]...
> > > "Kristopher Johnson" <[EMAIL PROTECTED]> writes:
> > > > "Your vote" is not something you own; it is a privilege granted to
you
> > by
> > > > the government,
> > >
> > > In the United States, voting is not a privilege granted by the
> > > government. It is a right held by the people. The Federal government
> > > has no power to restrict it, and the States have only a small amount
of
> > > power to restrict it. The states had more power in this regard before
> > > the ratifications of the 14th, 15th, 19th, 24th, and 26th amendments.
> >
> > Hmmm....mincing words, I think. Anyway, am I to assume you aren't from
US?
>
> Why assume that? Because there is an indication that he was taught
history?
So I goofed. :) I'll never know what country then, not that it's the
end-all.
>
> Paul
>
> >
> > >
> > > In general in the United States the government does not have the
> > > power to grant privileges. Any time you hear about them doing so,
> > > you should immediately be suspicious that they're exceeding their
> > > authority.
> >
> > I wouldn't put you on Gore's or Bush's legal team. We are testing these
> > very notions as we speak.
> >
> >
> >
>
>
>
>
------------------------------
From: "Frog2000" <[EMAIL PROTECTED]>
Subject: Re: vote buying...
Date: Thu, 16 Nov 2000 14:25:27 -0500
"zapzing" <[EMAIL PROTECTED]> wrote in message
news:8v15k4$lfq$[EMAIL PROTECTED]...
> In article <[EMAIL PROTECTED]>,
> "Frog2000" <[EMAIL PROTECTED]> wrote:
> >
> > "zapzing" <[EMAIL PROTECTED]> wrote in message
> > news:8usakb$ne9$[EMAIL PROTECTED]...
>
> > > You can't stop it. That is why democracy
> > > will collapse, as all systems eventually
> > > must.
> >
> > That is an opinion based on pesimism, and not backed up by fact.
>
> History shows that all past empires
> have collapsed for pretty much the
> same reasons. And this one is following
> that trajectory quite well. Corruption
> is increasing and the government is
> turning against its own people.
If you call the US an empire, you MAY be right. The EU, all of Europe,
Africa. Who will be safe?
>
> This sort of behavior is predicted
> by evolutionary biology, because
> altruism is expected to evolve only
> between people with a high degree of
> relatedness, but the "freedom of the
> empire" means that family and tribal
> groups will be severely disrupted.
Sounds more like socialogy, or psychology to me. I don't know any
system/culture that is immune. I mean, they all have flaws.
>
> As to your other point, that I am
> "pessimistic", that is an argument
> ad hominem and is therefore invalid.
Well you tell me, so I don't make an ASS out of myself, which I may have,
but are you optiimistic or pesimistic about things? Or, maybe neither.
>
> --
> Void where prohibited by law.
>
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
------------------------------
From: "John A. Malley" <[EMAIL PROTECTED]>
Subject: Re: Anyone has read / poses / is found of book by M.Schroeder(not the
Date: Thu, 16 Nov 2000 11:29:31 -0800
To those who read postings at Deja.com, my attempts in prior posts to
render the capitalized sigma summation symbol cobbled together out of
dashes and front/back slashes will unfortunately look like garbage and
may make the post hard to read. It comes out fine on a text-based News
reader. So if you see strange clutter be aware it's intended to be the
summation symbol.
John A. Malley
[EMAIL PROTECTED]
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: Hitachi - on what grounds ??
Date: Thu, 16 Nov 2000 11:37:17 -0800
Mok-Kong Shen <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
>
> John Savard wrote:
> >
> > Mok-Kong Shen<[EMAIL PROTECTED]> wrote:
> >
> > >I wonder why the other candidates of AES are deemed
> > >to violate the patent, while Rijndael's ShiftRow, where a
> > >cyclic shift is done, does not. Could someone explain that?
> >
> > The extent of the shift is fixed, not variable. Thus, not only is it
> > not a manifestation of the innovation claimed by Hitachi, but the
> > "swap halves" step in DES would be prior art.
>
> Lest Hitachi comes onto further ideas of patenting based
> on variability, let's note that variable block sizes,
> variable keys, variable substitutions/permutations,
> variable number of rounds, variable operator types,
> variable parameters, variable round key orderings, variable
> cipher stacks, variable processing through PRNG control
> and, most generally, a variable 'structure' of the entire
> encryption algorithm (see the recent thread 'The ultimate
> cipher' initiated by me) have all been discussed in this
> group and are therefore already prior art of crypto and
> not patentable.
Pardon me for butting in.. General theoretical
discussion does not necessarily
mean prior art. A certain amount of "reduction to practice" needs
to occur. The requirement for disclosure is "Teaching the art"
I would immagine that there is a lower limit on how general
a discussion could be and not be considered "Known". I
have read many of the posts you mention and I don't feel
that anything in them "Teaches". Most are speculation,
supposition or untested opinion.
"You could do this or that and this would occur..
No you're a boob!
Am not... Proveit!
Well, your idea was dumb."
I would feel better if examples were cited that adhered to
a less general and more rigorous process. A white paper
with source code, An acedemic publication, a publicized
contest submission. Along those lines.
Rarely are claims drafted as broad as the discussions
mentioned. To anticipate them, the discussions would
need to be a little more substantial and definitive.
I can just see a lawyer calling one of these discussion
participants as a witness.
Lawyer:
"On 12/7/2000, did you post a description
of this process?"
Witness:
"Yep, I'm surprised it works, I just said it to
piss off David Scott"
Paul
>
> M. K. Shen
> ---------------------------------
> http://home.t-online.de/home/mok-kong.shen
>
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: vote buying...
Date: 16 Nov 2000 11:36:03 -0800
Dan Oetting <[EMAIL PROTECTED]> writes:
> Can anyone site a current public election with secret ballots where a
> receipt of the vote is given to the elector?
I've gotten a receipt (i.e. a piece of paper saying that I voted) every
time I've ever voted. It's also recorded in public records.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Q: fast block ciphers
Date: Thu, 16 Nov 2000 19:51:35 GMT
In article <[EMAIL PROTECTED]>,
David Schwartz <[EMAIL PROTECTED]> wrote:
>
> Scott Fluhrer wrote:
>
> > Umm, the OP asked for a block cipher. I do believe that RC4 is
normally
> > considered a stream cipher...
> >
> > --
> > poncho
>
> While a block cipher may be difficult to use as a stream cipher
> (actually, it's not hard to use but hard to be sure it's secure), any
> stream cipher can trivially be changed into a block cipher.
It's actually trivial to turn a block cipher into a stream cipher.
Just encrypt a binary counter using a private key and xor the
ciphertext against your input stream. Sure the keystream is made a
block at a time but you need not use it like so.
And the relevant entropy (assuming the cipher is secure and the key has
not been guessed) is just
-log2(pi (from i=0) (to n) 1/[(2^w) - i])
Where 'pi' denotes the product of the terms and 'w' is the size of the
block in bits. For example if w=64 and you use 128-bits to encrypt
the message the relevant entropy in the keystream is (1/2^64)(1/(2^64)-
1) or about 1/2^128. In other words the probability of guessing the
keystream is very unlikely. It does also allow the attacker to
determine the work factor in guessing the next block of keystream
assuming they know 'n' previous outputs.... etc..
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Eric Lee Green)
Subject: Re: vote buying...
Reply-To: [EMAIL PROTECTED]
Date: Thu, 16 Nov 2000 20:00:56 GMT
On 15 Nov 2000 20:07:04 -0800, Paul Rubin <[EMAIL PROTECTED]> wrote:
>David Schwartz <[EMAIL PROTECTED]> writes:
>> > That traceability is bad even if the election officials are honest and
>> > the election is fair. Years later, Sheriff Bubba has worked his way
>> > up to being Supreme Dictator Bubba, has the election officials
>> > executed and gets the archived code numbers and uses the ballot data
>> > to locate everyone who voted against him.
>>
>> Won't work. It'll just give him the code numbers of everyone who voted
>> against him. Remember, we were talking about a case where a citizen
>> presents his electronic voting receipt to an official.
>
>Nope. Remember, Bubba already got the receipts from the voters back
>when he was still Sheriff and couldn't decode them. Now he can decode
>them and there is hell to pay.
Huh? Why would Bubba get receipts back from voters? And why would
there be voters' names attached to those receipts? And if receipt
numbers are randomly generated and totally unrelated to voter ID
numbers or names, what in the world would tell him that receipt
251-5321592 came from "Eric Lee Green"?
>> > The goal of being able to check votes after the election (to detect
>> > fraud) is in conflict with the goal of not being able to check the
>> > votes (to protect voter secrecy).
>>
>> So long as you need the voter's help to check them, you can easily meet
>> both goals.
>
>The whole point of the original Sheriff Bubba scenario was to show
>that receipts are bad even if the voter has to help decode it.
You are assuming that something is there to be decoded.
I'm assuming that the receipts work like cash register receipts -- the
voter gets one copy, the other copy is on a roll inside the machine.
Receipt numbers may start at 1 and go upwards (with a prefix of
course), but if we do not record the times at which voters voted, then
there's nothing to say that voter "Eric Lee Green" voted for "Pat
Buchanon" (just to pick somebody I would never vote for :-). You might
see that receipt number "251-53400005" voted for Pat Buchanon, but unless
the holder of that receipt comes forth and says otherwise, you have no
idea who this person is.
The idea is to put the database online and for individuals to be able to
check their receipt number against what's in the database to verify that
their vote counted for the candidate on their receipt. Generally the
individuals who would do this sort of thing would be party faithful
and there's no secret involved -- they're often campaign volunteers,
plaster their house with "Bush 2000" or "Guts 2000" signs, etc. With
the entire database online in downloadable form, you could also download
the database, import it into your favorite database application/report
generator, and verify that the totals add up to what the Secretary of
State says they add up to.
>don't see this as helping. Maybe there could be some protocol where
>all the receipts are public, and the statistics of a signed collection
>of votes (signed by the voting machine) can be computed, but nothing
>about individual votes can be computed, and the statistics of unsigned
>collections can't be computed.
The "anonymous receipt" as done by grocery stores fits that bill.
There is nothing on that cash register tape saying who bought these
items (unless you presented some sort of club card or credit card), but
presenting that receipt to the cashier is proof that yes, you did indeed
purchase this item that you're trying to return. All these votes could
be online, but without identifying information in the data, there's no
way to identify individual people.
There's still the problem of "voting the dead" in this scheme, of course.
But there's not much that can be done about that while preserving
anonymity.
(Otherwise, you could find statistics
>of different subsets of the receipts and figure out individual votes
>or votes of small groups).
This is already done on a precinct-by-precinct basis in most jurisdictions.
Heck, some jurisdictions even report votes on a per-ballot-box basis!
> Then the voting machine would spit out
>its signed receipt collection as soon as the polls close, and destroy
>its signing key immediately afterwards, so Bubba wouldn't be able to
>use the key to sign more stuff later (i.e. if the election was honest
>in the first place, the receipts couldn't be retroactively misused).
That's a good idea. But I think your final statement ("A star trek solution
to a babylon 5 problem") was better. Voting machines can always be
rigged. Ghost voters can always vote, as long as we preserve the
anonymity of votes. Cryptographic solutions which purport to preserve
anonymity while removing the possibility of ghost voters are snake oil.
Preventing ghost voters is an exercise in oversight of voter registrations
and of voting places, not an exercise in technology. Simple solutions
such as requiring a street address for each voter, and requiring that each
voter be able to receive a sample ballot at that street address (i.e., not
returned with "addressee unknown"), are better solution to the problem
of ghost voters. Sometimes the best solutions are not technological in
nature.
--
Eric Lee Green There is No Conspiracy
[EMAIL PROTECTED] http://www.badtux.org
------------------------------
** 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
******************************
