Cryptography-Digest Digest #211, Volume #13 Wed, 22 Nov 00 23:13:01 EST
Contents:
Re: Entropy paradox ("Matt Timmermans")
Re: Entropy paradox ("Trevor L. Jackson, III")
Re: Entropy paradox (Bryan Olson)
Re: OCR Encryption (Steve Portly)
Re: Entropy paradox ("Trevor L. Jackson, III")
Re: vote buying... (Benjamin Goldberg)
Re: Algorithm with minimum RAM usage? (Benjamin Goldberg)
Re: A Simple Voting Procedure (Benjamin Goldberg)
Re: DES S-Box question ("Scott Fluhrer")
Re: New Dynamic Algo + Contest + Doc (Richard Heathfield)
Re: A Simple Voting Procedure (David Schwartz)
Re: A Simple Voting Procedure (David Schwartz)
----------------------------------------------------------------------------
From: "Matt Timmermans" <[EMAIL PROTECTED]>
Subject: Re: Entropy paradox
Date: Wed, 22 Nov 2000 19:40:22 -0500
Reply-To: "Matt Timmermans" <[EMAIL PROTECTED]>
Mok-Kong Shen <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> This is a re-formulation of an issue that I questioned
> previously. Suppose one has m perfectly random bits and
> uses that in some appropriate way to get a BBS generator
> to generate u bits, with u >> m.
Ok. we have m perfectly random bits.
> We know that (accepting
> certain plausible assumptions) the u bits are provably
> secure. It seems thus that we have obtained more entropy
> that way, i.e. having obtained an amount of additional
> entropy from nothing.
What do you mean by entropy? Do you mean "provably secure bits", or do you
mean "perfectly random bits". These are different things.
"Provably secure", in BBS, means that predicting bits without knowing the
state of the generator or the factors of the modulus is proven to be about
as difficult as factoring the modulus. We think that factoring the modulus
is infeasible if it is big enough, and so your u bits are practically
unpredictable.
"perfectly random" means unpredictable in principle (with no ifs).
Your u bits are secure, but not random. If u is bigger than m, then I have
deterministic (but infeasible) procedures available to me to determine what,
exactly, your original m bits were, and that allows me to predict the rest
of the generator's output.
------------------------------
Date: Wed, 22 Nov 2000 20:50:43 -0500
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Entropy paradox
Mok-Kong Shen wrote:
> John Savard wrote:
> >
> > Mok-Kong Shen<[EMAIL PROTECTED]> wrote:
> >
> > >So you conclude that BBS is fairly unsafe (against all
> > >the commonly seen claims of unpredictability to the left
> > >and the right)? Thanks.
> >
> > It is still vulnerable against trying all 2^m combinations of the true
> > random bits that were started with, since no entropy has been gained.
> >
> > But if m is big enough so that this is not a concern, the part about
> > BBS being 'provably secure' means that with more than m of the u bits
> > produced by the BBS generator, using cryptanalysis to work out what
> > the m true random bits were, to predict others of those u bits, in
> > less than 2^m steps, is not possible.
> >
> > Cryptosecure does not equal truly random.
> >
> > If it did, we could never use any other system of encryption but the
> > one-time-pad.
>
> So you mean that one can't use more than m bits of the
> u bits coming out of BBS, if one wants unpredictability
> (of whatever nature that term is understood in the
> literature)? That would greatly deprecate the value
> of BBS, isn't it? Thanks.
In principle yes. But principle all non-OTP ciphers share this "weakness".
Since the principle indicates the difference between unreasonably difficult
and impossible, it has little bearing on most ciphers. For background see
Shannon's definition of unicity and D. Scott's rants about distinguishable
plaintext ;-)
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Entropy paradox
Date: Thu, 23 Nov 2000 01:44:23 GMT
Mok-Kong Shen wrote:
> The problem is, as I said elsewhere, explaining HOW,
> through inputting m full entropy bits into BBS (regarded
> as a black box), one can obtain u >> m bits of output
> that are normally claimed in the crypto literature to
> be unpredictable and hence having at least almost full
> entropy
Please cite the crypto literature to which you refer.
I have not seen any of the papers on BBS make such
claims about the entropy of the stream. The papers
show that the BBS prediction problem is super-polynomial
in the size of the modulus if factoring is
super-polynomial.
--Bryan
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Steve Portly <[EMAIL PROTECTED]>
Subject: Re: OCR Encryption
Date: Wed, 22 Nov 2000 20:47:37 -0500
[EMAIL PROTECTED] wrote:
> In the mac community a group of people have got
> a rather bad idea that the following icon in Mac
> OS X has a readable text in it. I doubt that.
>
> http://johnlockard.tripod.com/ReadMeICON.png
>
> Anyway, there must be a limit say an area of 25
> pixels per character that prevents text from being
> read by man or machine. Am I right?
>
> Cheers!
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
It's a paradox for retirees. As folks get older it gets harder to read
the screen without bifocals, yet the print keeps getting smaller with
each new monitor they buy. I doubt surfing the web at 1920 X 1440 would
be any fun at all for them ;)
------------------------------
Date: Wed, 22 Nov 2000 20:56:34 -0500
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Entropy paradox
Mok-Kong Shen wrote:
> John Savard wrote:
> >
> > Mok-Kong Shen<[EMAIL PROTECTED]> wrote:
> >
> > >This is a re-formulation of an issue that I questioned
> > >previously. Suppose one has m perfectly random bits and
> > >uses that in some appropriate way to get a BBS generator
> > >to generate u bits, with u >> m. We know that (accepting
> > >certain plausible assumptions) the u bits are provably
> > >secure. It seems thus that we have obtained more entropy
> > >that way, i.e. having obtained an amount of additional
> > >entropy from nothing. How is this apparent paradox to be
> > >properly explained?
> >
> > There is no paradox whatever.
> >
> > The u bits are provably secure, because the computation that produced
> > them cannot, subject to the assumptions, be cryptanalyzed.
> >
> > But that in *no* way prevents a brute force search over the 2^m
> > possibilities for the truly random bits, so nothing is obtained from
> > nothing.
> >
> > Only if m is large enough that that brute force search is impossible
> > are the u bits genuinely secure, and their cryptosecurity is the
> > result of the work factor required to cryptanalyze them - not a single
> > bit of extra entropy.
>
> If the u bits are very secure, what would the same number
> u of perfectly random bits (we suppose that these are
> obtainable) distinguish themselves from these? They
> are totally equivalent for the practice, aren't they?
No, the bits from the BBS generator come in a logarithmically compact form
called a seed. This is much more convenient in practice.
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: vote buying...
Date: Thu, 23 Nov 2000 02:25:56 GMT
Paul Rubin wrote:
>
> 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.
That receipt only records the fact that you voted, and indicates nothing
whatsoever about who you did [or did not] vote *for*.
Unless you are worried about your vote being recorded incorrectly, this
is a Good Thing (tm).
--
There are three methods for writing code in which no bug can be found:
1) Make the code so straightforward that there are obviously no bugs.
2) Make the code so complicated that there are no obvious bugs.
3) Insist that any apparent bugs were really intentional features.
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Algorithm with minimum RAM usage?
Date: Thu, 23 Nov 2000 02:25:58 GMT
Guy Macon wrote:
>
> I sometimes program microcontrollers where my old standby ARCFOUR
> can't be used because it takes too much RAM. What strong encryption
> algorithm uses the minimum amount of RAM?
>
> I have virtually unlimited amounts of ROM, and the application
> is such that I have a virtually unlimited amount of CPU time to
> burn, so efficiency and size are non-issues.
Assuming that you are writing the expanded key (the results of the key
schedule) in EPROM, not storing in RAM, there are a large number of
ciphers which can fit your needs.
If you don't mind that it has very little analysis, my cipher Hypercrypt
needs only 5 loop counters and the key to turn the plaintext into
ciphertext and vice versa, and some of those loops can be unrolled.
--
There are three methods for writing code in which no bug can be found:
1) Make the code so straightforward that there are obviously no bugs.
2) Make the code so complicated that there are no obvious bugs.
3) Insist that any apparent bugs were really intentional features.
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: A Simple Voting Procedure
Date: Thu, 23 Nov 2000 02:25:59 GMT
David Schwartz wrote:
>
> Stanley Chow wrote:
>
> > David Schwartz wrote:
>
> > > It allows the voter to convince themself that their vote
> > > was counted and counted for the correct candidate. If somehow
> > > their vote doesn't appear in the count for the correct candidate,
> > > or appears in the count for the wrong candidate, the voting
> > > receipt would be proof that their vote was incorrectly tallied.
>
> > It seems there are some terminology confusion here. There are
> > several distinct points:
> > 1) the voter can tell if his vote is correctly counted
> > 2) the voter can prove if his vote is incorrectly counted
> > 3) 3rd party can force voter to reveal the vote
>
> > Note that 2) is pretty much the same as 3) in that there are lots of
> > scenarios involving corrupt official, revolutions, vote-buying, etc.
> > that turns 2) into 3). So if you claim 1) and 2), you are logically
> > claiming 3), which is objectionable to many people.
>
> No, I think you can have both 1 and 2 without having 3. So
> either I'm misunderstanding your argument, your argument is incorrect,
> or your statement (or my understanding) of one of those three
> requirements is wrong.
>
> Consider a system where each voter has an ID but no voter can
> prove which ID is his and no official can map an ID to a particular
> voter. When you vote, you are given a receipt (which is also
> ultimately made public) that proves that your ID voted for whichever
> candidate you actually voted for.
>
> When the election is complete, the list of voter IDs that
> voted for each candidate is presented.
>
> You have '1' because if you can check if your ID is on the
> correct list and you know your ID.
>
> You have '2' because you have a receipt that says that your ID
> voted for your candidate. If it appears on the wrong list, presenting
> your receipt demonstrates this error.
>
> You don't have '3' because no third party could ever be sure
> you were presenting your own receipt, as opposed to one some other
> voted made public. If all receipts are made public after the election,
> you can present anyone's receipt you choose -- that of literally any
> voter.
What happens if, after the election, you convince/coerce a couple dozen
people into giving you their election receipts. You check these against
the public list, and discard the ones which are for the candidate whom
you want in office. You then give the remainder to your trusted
friends, who already voted for your favorite candidate. They each call
in to the election office, and report that the machine registered their
vote wrong, and give show the election officials their receipts, and get
the votes changed.
--
There are three methods for writing code in which no bug can be found:
1) Make the code so straightforward that there are obviously no bugs.
2) Make the code so complicated that there are no obvious bugs.
3) Insist that any apparent bugs were really intentional features.
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: DES S-Box question
Date: Wed, 22 Nov 2000 18:28:56 -0800
Brian McKeever <[EMAIL PROTECTED]> wrote in message
news:8vgtd4$j88$[EMAIL PROTECTED]...
> One of the design criteria (according to AC) for the DES s-boxes was that
> for fixed values of bits 0 and 5, each symbol 0..15 should appear exactly
> once as bits 1-4 vary (that is, as presented in AC, each row is a
> permutation). What is the reasoning behind this structure? Does
> it have anything to do with avalanche? Would DES be appreciably weaker
(all
> other things being equal, if possible) if the s-boxes were more like
random
> functions? What attacks would be facilitated by removing this
restriction?
Well, AFAIK, this criteria was chosen to limit the number of ways that you
could have a nonzero differential input to the sboxes, and a zero
differential out. If this criteria wasn't followed, then it may be possible
to have a several round differential, in which a nonzero differential exists
on one side, and a zero differential exists on the other, and in which all
the sbox outputs just happen to be zero.
Now, as it is currently designed, it is possible for a nonzero sbox input
differential to translate into a zero output differential, by confining the
bit differentials in bits 0 and 5 of the sbox inputs. However, it turns out
that, if this does happen, then one of the next two rounds will have always
have a nonzero differential, and so no long term differential like I
described above can exist.
--
poncho
------------------------------
Date: Thu, 23 Nov 2000 03:06:01 +0000
From: Richard Heathfield <[EMAIL PROTECTED]>
Subject: Re: New Dynamic Algo + Contest + Doc
David Wagner wrote:
>
> proton wrote:
> >Lets just halt innovation altogether.
>
> Don't misquote me.
>
> I said: If the point is to experiment, sure, post the algorithm,
> but don't tell people to use it operationally until it has been
> well-scrutinized.
>
> Experimental research cipher ideas should not be confused with
> stuff to be used operationally.
But it is. You see, "operationally" doesn't necessarily mean anything
terribly important.
I don't know why it is that people feel compelled to devise their own
cryptographic algorithms. I have felt this compulsion myself, and still
tinker with my own algorithm, trying to find ways to make it faster/more
secure/easier to use...
I, too, have posted my algorithm here in the hope of getting some
serious cryptanalytic input. Unfortunately, I got extremely serious
cryptanalytic input, which was basically "don't bother". :-) And that
was the right advice. (Not that I let it discourage me from finding ways
to make my algorithm faster/more secure/easier to use...)
But people continue to do this, even though it's 99.999% likely to be a
futile exercise.
*Why* do we do this?
I've never tried to write my own sort algorithm. I just use Quicksort
(or, strictly speaking, I just use qsort!). Likewise, I've never tried
to write my own search algorithm. I just use bsearch(). I might,
conceivably, /implement/ bsearch - indeed, I have implemented it, and
for good reason - but I don't try to invent my own. But when it comes to
cryptography, I must have invented a couple of dozen algorithms.
Hypothesis: we (meaning the non-cryptographers who plague sci.crypt and
make life so tedious for the rest of you) can't shake the notion that
obscurity lends a little security. What we really want to do is publish
our algorithm, get it cryptanalysed (partly for security, and partly for
pose value), modify it until it gets a grudging thumbs-up from
sci.crypt, then modify it ***just a little bit more*** (EVEN THOUGH we
know full well that this will invalidate the cryptanalysis it's received
- because we don't really *believe* it'll matter), and start using it.
Not for anything serious, I hope and trust...
Well, children will play. And I'm just as big a children as the rest of
them.
Anyone for CDX-3?
--
Richard Heathfield
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R answers, C books, etc: http://users.powernet.co.uk/eton
------------------------------
From: David Schwartz <[EMAIL PROTECTED]>
Subject: Re: A Simple Voting Procedure
Date: Wed, 22 Nov 2000 19:26:16 -0800
Benjamin Goldberg wrote:
> What happens if, after the election, you convince/coerce a couple dozen
> people into giving you their election receipts. You check these against
> the public list, and discard the ones which are for the candidate whom
> you want in office. You then give the remainder to your trusted
> friends, who already voted for your favorite candidate. They each call
> in to the election office, and report that the machine registered their
> vote wrong, and give show the election officials their receipts, and get
> the votes changed.
Since the receipt will show the vote for the other person, they'll be
of no use. The 'receipt' is actually a digitally signed string of
numbers that decodes to 'some voter voted for candidate X'. All the
receipts will be made public as part of the results of the election. The
receipt contains no information to identify the identity of the voter.
DS
------------------------------
From: David Schwartz <[EMAIL PROTECTED]>
Subject: Re: A Simple Voting Procedure
Date: Wed, 22 Nov 2000 19:57:22 -0800
David Schwartz wrote:
> > > Are you alleging that it's impossible to devise a system that meets the
> > > requirements in my paragraph above? I'm not saying it's easy or even
> > > desirable, I'm simply saying it's possible. In order for the
> > > requirements to be contradictory, it would have to be impossible.
> > Your saying it is possible does not make it so. You have to prove
> > that it is in fact possible. In fact, an existance proof does not
> > allow you to build such a system; you need a constructive proof
> > that is also practical - a remarkly rare beast.
I just realized that this requires a fuller development. There's
actually a philosophical issue here regarding the standards of proof for
impossibility or possibility.
The person who alleges something's impossibility bears an extremely
heavy burden of proof. He cannot simply challenge someone to devise a
means of accomplishing what he claims is impossible. He must demonstrate
that there could not exist any way to accomplish it that doesn't
conflict with what is already known to near certainty.
Consider if, in 1950, I alleged that it might be possible to construct
a scheme such that anyone could encrypt a message to me but only I could
decrypt it. Someone might concoct an on the spot impossibility proof. It
would go like this: Whatever anyone can do to encrypt the message, she
can reverse to decrypt it. One might consider this impossibility proof
valid, and unrefuted, it's quite strong.
Now ask yourself what the burden of proof is for someone who wishes to
overthrow this impossibility argument. Must he devise a scheme that
meets the requirements? Certainly not. All that's needed is the
following, "perhaps it's possible to devise a scheme where the
encryption process cannot be reversed, but information is not lost. The
receipient might have some special knowledge that allows him to descrypt
it by a means other than reversal of the encryption process. Perhaps the
information in the message is 'scattered' by the encryption process in a
way that the recipient can 'gather' but nobody else can."
I would submit that this is sufficient to refute the impossibility
proof. After all, if what is claimed above is possible, then meeting the
requirements is possible. And clearly no one can prove that that's not
possible, (especially because we know for a fact that it is possible).
What I'm trying to say is - don't build your assumptions into your
requirements. Because this only assures you'll get a result that doesn't
challenge your assumptions. Ask, in the requirements, for what you
really want. You may find that some of your assumptions were incorrect,
and an extremely bright person might devise a scheme you wouldn't have
thought possible. Even if your assumptions were correct, you'll still
wind up writing better requirements by leaving them out, and that may
also result in a better system in the end.
DS
------------------------------
** 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
******************************
