Cryptography-Digest Digest #826, Volume #13 Wed, 7 Mar 01 06:13:01 EST
Contents:
Re: super strong crypto, phase 3 (David Wagner)
Re: Super strong crypto (David Wagner)
Re: super strong crypto, phase 3 (Mok-Kong Shen)
Semi-super-strong crypto? (Benjamin Goldberg)
Voting (Benjamin Goldberg)
Re: Voting (Paul Rubin)
Re: => FBI easily cracks encryption ...? ("John Niven")
Re: Any news on the KFB mode? (Volker Hetzer)
Austin Cypherpunks Physical Meet: Tue. Mar. 13 (Jim Choate)
Re: => FBI easily cracks encryption ...? ("Mxsmanic")
One time authentication (Tim Tyler)
Re: One-time Pad really unbreakable? (Tim Tyler)
Re: Super strong crypto ("Bryan Olson")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: super strong crypto, phase 3
Date: 7 Mar 2001 08:13:06 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
John Savard wrote:
>If you have
>
>E(P1,K1)
>E(K2,K1)
>E(P2,K2)
>E(K3,K2)
>E(P3,K3)
>E(K4,K3)
>E(P4,K4)
>...
Forgive me for interrupting, but it seems that this scheme is
insecure unless special measures are taken.
Here's a chosen-ciphertext attack. I observe the packet
E(P3,K3), E(K4,K3)
on the wire. I prevent it from reaching the recipient, and substitute
instead the following replacement:
E(K4,K3), E(K4,K3).
The receiving host's crypto-engine will decrypt and pass K4 as plaintext
up to the recipient. Then if I can arrange to read just this single
block of plaintext, I recover K4 and can read all subsequent traffic
sent over this channel.
Thus, any adversary who has control over the network and who can obtain
a copy of a single selected plaintext block can learn the entire rest
of the plaintext.
This is a very bad property for a "super-strong" scheme. See, e.g.,
my post on the practical relevance of chosen-text attacks for an example
scenario where this could cause serious problems (the IPSEC case study).
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Super strong crypto
Date: 7 Mar 2001 08:21:39 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
Douglas A. Gwyn wrote:
>David Wagner wrote:
>> E_k(x) = AES_0(F_k(x)),
>> where F_k(x|y) = (DES_0(x) xor k) | (DES_0(y) xor k),
>
>I *guess* that by this you mean DES_0 is repeated on the
>separate subblocks of the actual input (masked_PT|new_key)
>as often as required to span the whole block, e.g. 8 times
>in my straw-man example.
To be more concrete, it is repeated exactly twice in my
example. I'm giving an example of a cipher with a 64-bit
key and a 128-bit block, but you could take the same idea
to build a cipher with a n-bit key and a 2n-bit block some
larger value of n if you like.
>> your mode is insecure when used with this E().
>
>Please elaborate. AES_0 can obviously be inverted with
>little work,
Yes, the AES_0 adds no security.
If we combine my construction with your mode (where you
transport a whole new 64-bit session key for each 64 bits
of plaintext enciphered), we'll have
x = the current plaintext,
k = the current session key,
y = the next session key, and
E_k(x|y) = the current ciphertext.
So assume we know x and c = E_k(x|y). Then
k = DES_0(x) xor AES_0^{-1}(c)
and from k we can recover y, so we can read all subsequent
plaintexts.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: super strong crypto, phase 3
Date: Wed, 07 Mar 2001 09:26:08 +0100
"Douglas A. Gwyn" wrote:
>
> Mok-Kong Shen wrote:
> > Sorry, I expressed myself wrongly. I meant that in one case
> > one never sends in the bit sequences anything that has to
> > do with the (new) keys, for these are generated according
> > to some scheme at the timepoints of need by both communication
> > partners, while in the proposal of Douglas Gwyn these keys
> > are chosen by the sender and transmitted to the receiver in
> > encrypted form. (I should have said 'over the line' instead
> > of 'online'.) I guess that it may be better to arrage to have
> > the new keys be generated rather than sending them encrypted.
> > Anyway, a comparison seems worthy of being studied.
>
> The trouble with generating new keys is that (except possibly
> for quantum methods) randomness cannot be used, only some
> algorithm. One then lumps the key generation in with the
> "general system" and whatever mutually agreed parameters for
> the key generator become the true key for the overall system.
>
> Note that Rabin's recent method was an attempt to extract
> true randomness according to some algorithm, and his opinion
> was that security would require an immense amount of random
> data (accessible to both communicants) sampled over a long
> enough time that the adversary could not capture all of it.
> My straw-man approach from phase 1 has instead tried to find
> a secure way to ship random key bits from one communicant to
> the other; the OTP paradox is avoided by stretching use of
> each key bit as far as it is safe to do so, which in general
> isn't very far (depends on the PT source and system structure).
I thought that one could be satisfied with the pseudo-
random keys generated (e.g. with a block cipher in counter
mode) for practical security. If, however, one really
desires (more) perfection (a term I leave here undefined),
then I'll suggest that each new key be sent in a separate
block and encrypted by another dedicated key. Since by
assumption the new keys are perfectly random (in contrast
to the block of encrypted messages that contain information
bits that are exploitable depending on the assumed model
of attacks), these blocks that contain new keys could only
be brute-forced. And a successful brute-force of a key block
only gives the opponent a small number of the immediately
following message blocks, i.e. before the key is again
changed. (Thus the domino effect is blocked. How frequently
one needs to send blocks containing the new keys is an issue
to be considered separately.) Would this scheme be eventually
better than your proposal? I guess that it at least avoids
some of the critiques being raised. (BTW, the clear separation
also makes the operations a bit simpler.) Thanks.
M. K. Shen
==========================
http://home.t-online.de/home/mok-kong.shen
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Semi-super-strong crypto?
Date: Wed, 07 Mar 2001 08:35:40 GMT
Having read the straw man stuff, I was inspired to write my own design,
for doing something with similar but (I hope) stronger effects.
You start out with a key, k0, and two secret IVs, IV0 and IV1.
There is also a series of values called k.
k(i) = encrypt_k0( IV0 + i )
ct(-1) = IV1
ct(i) = encrypt_(k(i/N))( pt(i) ^ ct(i-1) )
Where N is chosen to be as many blocks as can be 'safely' encrypted with
one key (And division is done with integers). Unlike in the straw man
idea, changing keys takes no extra bandwidth.
This isn't information theoretically secure, either, since brute force
against k0 is all that's needed, but I think it's still pretty good.
I'm sure someone has thought of this idea, or one like it, before, but I
don't think I've ever seen it posted. Or at least, I don't recall it.
--
The difference between theory and practice is that in theory, theory and
practice are identical, but in practice, they are not.
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Voting
Date: Wed, 07 Mar 2001 09:01:58 GMT
Greg Ofiesh wrote:
> In light of the electronic voting booth that Florida wants to deploy,
> I think the equipment should be a case study for this group on how
> flawed the entire system really is. It would be really good to see
> statistics on how unlikely someone would actually not tamper with the
> results in down town central bomb shelter.
Personally, I think the only kind of voting machine which can be trusted
not to have been tampered with is one that's purely mechanical, and can
easily be inspected by eye for whether it's been messed with or not.
The voting machines in NY, while a bit old, fit this requirement quite
well. However, I will admit that there are some ways improvements could
be made. The NY machines have (IIRC) a mechanical counter, which has an
odometer-like display. It's easy for someone to accidentally miscopy
the digits, and there is nothing remotely like a hard-copy of the votes;
the only record of them is the counter. A useful improvement would be
to have, in addition to the mechanical counter, a digital one, which
prints out the number of votes for each candidate on a printer. Well,
actually, which has a serial port or something so it can transfer the
count to a device which has a printer (same effect, less hardware).
Also, moving the levers should result in it punching a ballot. Since
the ballot is not punched by a human, but a precise machine, the
problems with partially punched ballots can't happen. Also, there's the
mechanism which prevents votes for more than one person for an office,
which should eliminate another kind of invalid ballot.
Being able to look at a mechanical counter, compare it to a digital
counter, and (if neccessary) compare it to a manual count of ballots,
should result in an election which whose results are fast, accurate, and
tamper resistant.
We can check that the mechanical count hasn't been tampered with simply
by looking at the machine's innards; it's just an arrangement of gears
and levers, and anything which shouldn't be there should be obvious.
We can check that the digital count hasn't been tampered with by looking
at the mechanical count.
If we think that the digital count was tampered with, and someone
somehow seperated the mechanical counter from the mechanism to advance
it by hand (which is the only way you could tamper and still have them
match), we can go and count punched ballots.
It's trivial to see if the number of ballots is similar to, or vastly
different from the counters, so someone fudging the counters would have
to fudge the ballots, as well.
Also, in designing new machines, it should not be too difficult to avoid
the mistakes of the past. To avoid wadded chad isn't that hard, don't
you think?
--
The difference between theory and practice is that in theory, theory and
practice are identical, but in practice, they are not.
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: Voting
Date: 07 Mar 2001 01:23:08 -0800
Benjamin Goldberg <[EMAIL PROTECTED]> writes:
> The voting machines in NY, while a bit old, fit this requirement quite
> well. However, I will admit that there are some ways improvements could
> be made. The NY machines have (IIRC) a mechanical counter, which has an
> odometer-like display.
I bet by mounting a small hidden microphone on or near one of those
machines, you could tell who was being voted for, because the internal
levers make different sounds. So much for the secret ballot.
------------------------------
From: "John Niven" <[EMAIL PROTECTED]>
Crossposted-To: alt.security.pgp,talk.politics.crypto
Subject: Re: => FBI easily cracks encryption ...?
Date: Wed, 7 Mar 2001 09:40:17 -0000
> > what their citizens are watching on TV or listening to
> > on radios. (Does England still do that?).
> Can you post details about this? I've always thought it was an urban
> myth except under lab conditions.
Britain's TV Licensing Department used to claim that they had handheld
detectors capable of not only detecting that you were watching TV, but also
which channel. I don't know anyone who's been caught by such a device,
though I do know people who have been caught for other reasons. The current
advertising drive suggests that all they know, and need to know, is who
doesn't own a TV license.
Sorry, hardly conclusive either way, but suggesting that earlier detection
claims may have lacked foundation.
John
--
John Niven
(Reply through newsgroup)
"Paul Rubin" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> CR Lyttle <[EMAIL PROTECTED]> writes:
> > I've seen and built system for less than $100 that can read your monitor
> > from across the street. Several countries have regular patrols checking,
> > from the street, what their citizens are watching on TV or listening to
> > on radios. (Does England still do that?). Such technology has been
> > available for over 50 years. It just keeps getting cheaper.
>
> Can you post details about this? I've always thought it was an urban
> myth except under lab conditions.
------------------------------
From: Volker Hetzer <[EMAIL PROTECTED]>
Subject: Re: Any news on the KFB mode?
Date: Wed, 07 Mar 2001 10:55:12 +0100
Paul Crowley wrote:
>
> Volker Hetzer <[EMAIL PROTECTED]> writes:
> > However, BBS was "proven" once too and later it turned out that
> > nevertheless it wasn't the perfect solution either.
>
> You mean BBS is detectably biased? Gosh - tell me more!
No, I didn't mean that.
If I remember correctly there was something about short cycles
or so. As soon as google has the articles in his earch engine
you can look up the original discussion there.
Greetings!
Volker
--
They laughed at Galileo. They laughed at Copernicus. They laughed at
Columbus. But remember, they also laughed at Bozo the Clown.
------------------------------
From: [EMAIL PROTECTED] (Jim Choate)
Subject: Austin Cypherpunks Physical Meet: Tue. Mar. 13
Date: 7 Mar 2001 01:14:21 -0600
Time: March, 13, 2001
Second Tuesday of each month
7:00 - 9:00 pm (or later)
Location: Central Market HEB Cafe
38th and N. Lamar
Weather permitting we meet in the un-covered tables.
If it's inclimate but not overly cold we meet in the
outside covered section. Otherwise look for us inside
the buidling proper.
Identification: Look for the group with the "Applied Cryptography"
book. It will have a red cover and is about 2 in. thick.
Contact Info: http://einstein.ssz.com/cdr/index.html#austincpunks
--
____________________________________________________________________
Before a larger group can see the virtue of an idea, a
smaller group must first understand it.
"Stranger Suns"
George Zebrowski
The Armadillo Group ,::////;::-. James Choate
Austin, Tx /:'///// ``::>/|/ [EMAIL PROTECTED]
www.ssz.com .', |||| `/( e\ 512-451-7087
-====~~mm-'`-```-mm --'-
--------------------------------------------------------------------
------------------------------
From: "Mxsmanic" <[EMAIL PROTECTED]>
Crossposted-To: alt.security.pgp,talk.politics.crypto
Subject: Re: => FBI easily cracks encryption ...?
Date: Wed, 07 Mar 2001 10:51:45 GMT
"Jerry" <[EMAIL PROTECTED]> wrote in message
news:1104_983925735@sdhqlt0098...
> TEMPEST "eavesdropping" is very resource intensive and
> not something that's done at random. If that van's
> parked across the street, you did something to bring it
> there.
I know. That's why I don't worry about it. I think it best that other
parties be forced to use resource-intensive techniques for surveillance;
this helps prevent frivolous surveillance and "fishing expeditions."
Indeed, a good argument for routine encryption of e-mail is that it
greatly discourages untargeted, random surveillance. Since even the
most trivial cipher requires orders of magnitude more effort to decrypt
(even with the key) than does plaintext, using any encryption at all
rules out whole categories of routine but unnecessary surveillance.
Strong encryption has the additional advantage of resisting active
attack, if that is necessary.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: One time authentication
Reply-To: [EMAIL PROTECTED]
Date: Wed, 7 Mar 2001 10:50:33 GMT
The OTP has long been regarded as providing "perfect secrecy" - assuming
a shared unguessable stream exists.
However, the OTP provides no authenticatio - it is subject to
bit-flipping attacks (unless message signatures are used) and
a known plaintext recovers the entire key.
I have heard that there is an authentication scheme that works on a
similar principle to the OTP - rather than relying on "confusion"
sequences.
While not providing "perfect" authentication, I hear this offers the
guarantee that the recipient is who they claim to be, and that their
message has not been tampered with with a probability of failure of
1/2^N where N is the number of bits of signature employed.
Again, this is subject to the proviso that a siutably "random" shared
secret is available.
I have not succeeded in locating further details of such a "perfect"
signature scheme. Can anyone provide a pointer to something like this?
Or offer a brief description?
--
__________ http://alife.co.uk/ http://mandala.co.uk/
|im |yler [EMAIL PROTECTED] http://hex.org.uk/ http://atoms.org.uk/
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: One-time Pad really unbreakable?
Reply-To: [EMAIL PROTECTED]
Date: Wed, 7 Mar 2001 10:54:54 GMT
Mxsmanic <[EMAIL PROTECTED]> wrote:
: [...] since OTPs offer perfect security [...]
Not in practice they don't. The normal term is "perfect secrecy" - but
indeed, no known implementation can be shown to offer that either.
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
From: "nospam"@"nonsuch.org" ("Bryan Olson")
Subject: Re: Super strong crypto
Date: Wed, 07 Mar 2001 11:03:01 GMT
Douglas A. Gwyn wrote:
[...]
> A detailed method for that would depend on the
>specific block cipher (the only requirement so far is that that
>cipher mixes well). This is where one really needs a good theory
>of the way that system structure interacts with information, in
>particular how to compute a lower bound on the expected work factor
>for the solution of such a problem.
Exactly. As I wrote in my first post to the thread, the
straw-man system (now multiple systems) rests by unproven
computational security. Of course "unproven" means not yet
proven, and there is no final result that such proofs are
impossible. But the news is not good...
>Looking
>just at the "information content" without consideration of how
>much work is required to extract the information is a waste of
>time (unless it shows extraction to be impossible, which is not
>the case here). Is there a well-developed theory into which we
>could plug the problem parameters and turn the crank to get the
>lower bound? (I'm not aware that any have been published.)
The answer is that despite colossal effort, and some
stunningly brilliant theorems, there is currently no proof
that computational security even exists. Establishing
interesting lower computational bounds is today the great
challenge facing the theory of computing.
In certain areas the theory might be called "well developed"
such as complexity theory dealing with nondeterministic
polynomial time languages, but even there the basic
conjectures upon which computation security rests are open.
There are problems proven to take exponential time, or even
greater, but none of these seem useful in cryptography
because there is no way to set them up to be easy for the
key-holder.
As important as the asymptotic theory is to cryptography, it
is not necessarily definitive. Unfortunately the results on
fixed-size inputs are even weaker. There are some results on
circuit complexity for trivial size problems, but no
cryptographically useful lower bounds.
I think I now see why you thought I was not following the
direction you took. I assumed you were aware of lack of
complexity results, and thus I could not understand why you
didn't see the chasm between your system and provable
security. You've now noted that the missing piece is a
provable lower bound on computation, when given enough
information to fix the answer. It's a great problem and I
certainly don't want to talk anyone out of working on it.
But understand it's no small detail. Thousands have tried
to bridge that chasm, and so far all have failed.
--Bryan
------------------------------
** 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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
