Cryptography-Digest Digest #106, Volume #12 Sun, 25 Jun 00 23:13:01 EDT
Contents:
Re: "And the survey says" ("Scott Fluhrer")
Re: How Uncertain? (Future Beacon)
Re: DES 64 bit OFB test vectors (zapzing)
Re: Encryption 4 the Masses? (Tim Tyler)
Re: How Uncertain? (tomstd)
Re: Comments please: A protocol for Digital voting (zapzing)
Re: DES and questions (rick2)
Re: "And the survey says" (David A Molnar)
Fish Book (Jim Reeds)
Re: DES and questions (tomstd)
Re: Question about lja1 (Andru Luvisi)
newbieish question (Benjamin Goldberg)
----------------------------------------------------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: "And the survey says"
Date: Sun, 25 Jun 2000 17:31:02 -0700
Paul Pires <[EMAIL PROTECTED]> wrote in message
news:uct55.40228$[EMAIL PROTECTED]...
> Scott Fluhrer <[EMAIL PROTECTED]> wrote in message
> news:8j5c0i$tr6$[EMAIL PROTECTED]...
> >
> <Snip>
> > Ok, if you want a fantasy list of what properties the perfect symmetric
> > cipher would have, how about:
>
> My thanks, As I noted, this thread was an accident but it is something
that
> facinates me. I am easily amused.
>
> > 1. Provable security. A formal proof that any Turing machine with an
> > encryption/decryption constrained [1]oracle, given a ciphertext
encrypted
> > with a random key, is unable to find the corresponding plaintext with
> > probability greater than epsilon in less than (huge number) of steps.
Or,
> > a proof of something at least as interesting.
>
> You should probably incude the inability of the attack to determine any
> portion of the key with any probability greater than random chance.
Well, there are "ciphers" where it is provably impossible to guess the keys
(with probability greater than epsilon). These ciphers simply ignore the
keys, and transform the plaintext in a key independant way. I wrote the
above to take account of such silliness. A
>
> But that's cheating! I feel bad enough fantasizing about the Ideal cipher,
a
> postulated God machine makes even me a little edgy. More to the point,
what
> would be the attributes of the cipher that make it pass such a test if it
> existed?
We have no idea. We don't know what such a cipher would look like. We have
no idea what the proof would look like. I don't believe that we even know
if such a cipher is possible. But, you asked why my perfect cipher would
look like...
>
> > 2. Efficiently implementable. It can be done with a minimum of
> memory/gates
> > on hardware, and any CPU anyone is interested in
>
> Definately.
>
> > 3. Fast. It should be take perhaps 1 cycle per byte encrypted/decrypted
> on
> > a high end CPU, and not that much slower on low end CPUs. Oh, and it
> should
> > be blazingly fast in hardware too.
>
> Wouldn't you want to combine #2 and #3 and use a measure of speed per unit
> resource used?
Not really. Some applications rather want #2, and don't really push the
speed performance. Other applications depend #3, and are willing to throw a
lot of resources at it to get that performance. In a good cipher, a
trade-off would be quite acceptable. However, we're talking about the
perfect cipher, so why not ask for anything.
Another thing is that most ciphers appear to be designed for a certain type
of implementation, and do less well when implemented elsewhere. For
example, DES is wonderful when implemented in hardware, and less wonderful
when implemented in software. RC4 is wonderful on an 8 bit microprocessor,
and not that much better on platforms with much greater capabilities. Of
course, the perfect cipher would work well everywhere.
>
> > 4. Key agility. There should be no penalty for switching keys.
>
> I'm a little slow. Does this mean that the key is used raw with no
hashing,
> pre-processing ?
I don't care how the cipher does it -- there exists applications which sends
out lots of short messages, each under a different key. There should be no
penalty for using the cipher in that fashion.
>
> > 5. Build in MAC. The algorithm should have an optional MAC property
that,
> > if you switch it on, causes minor ciphertext expansion and possibly
minor
> > slowdown, and has provable forgability resistance.
>
> I notice you said resistance and not immunity. So a probability of 1 in X
of
> accidentally spoofing it is OK where X is comfortably large?
Well, unless you have infinite ciphertext expansion, that's rather
unavoidable. Assuming that there exists 1 N bit message that is legitimate,
the attacker can guess an N bit message at random, and have a (at worse)
2^{-N} probability of forging the legitimate message.
One nice thing is that this property in MACs appear to be achievable.
Several have been published recently that have this provable forgability
resistance (assuming some other ciphergraphical primitive is secure, of
course), and they run impressively fast.
>
> > 6. Plaintext size. It should be able to encrypt/decrypt any length of
> > plaintext, not just those at a particular 'block boundary'.
>
> Ok.
>
> > 7. Ciphertext expansion. Without the MAC feature turned on, there
should
> be
> > no ciphertext expansion.
>
> Does this include extra info for a salt or IV?
There are applications where there is no ciphertext expansion can be
tolerated. For example, if you are encrypting blocks on a disk below the
level of the file system -- there really isn't any good place to store any
expansion.
>
> > 8. Moderate key size. Key size should not need to be any longer than
what
> > can be convienently transported using current public-key operations.
> > 256-512 bits would be good. I'm willing to make them a bit larger to
get
> > property #1 (:-)
>
> This is how I see it. Projections of increases in computational ability
> have to have a "knee" in the curve considering the short time we have been
> collecting data points. 512 bits has a comfortable feel based on my
biases.
> How about a characteristic that speed or resources used should be a linear
> effect of key size and not exponential. I think this ties in with #2 and
#3
> above.
>
> > Now, obviously, no known cipher has all, or even most, of these
> properties.
> > For that matter, I don't know of any cipher (practical or impractical)
> that
> > has property #1 (with an Oracle, you can break an OTP trivially). Those
> > ciphers that do fufill (or at least come close to fufulling) a subset of
> > these properties have other drawbacks that make them inapplicable to
other
> > applications. In other words: you need to select the appropriate cipher
> for
> > the application.
>
> Hey, since we're dreaming, why not throw in resistance to known plaintexts
> of a number below that produced during the maximum life of the key used?
Already covered by #1: the Oracle can encrypt known (or for that matter,
chosen) plaintexts.
>
> > I'll let others decide whether all the items on the list are relevant
> > (although, I believe every item is useful for some application), or
there
> > are other items that should be on the list. And, I'll let others list
how
> > various ciphers come close to meeting items on this list.
> >
> >
> > [1] The constraint on the Oracle is that you can't ask the decryption of
> the
> > input ciphertext.
> >
> >
> > --
> > poncho
>
> And back to the beginning. I enjoy cipher design but it seems that there
is
> no *reason* to do it other than self-satisfaction. It seems that all of
the
> pieces are laying around for an encryption oracle suitable for any
> application but the goal of a general purpose cipher with a good score
> across the board might still be needed.
>
> Thanks for your time.
>
> Paul
>
>
>
>
>
------------------------------
From: Future Beacon <[EMAIL PROTECTED]>
Subject: Re: How Uncertain?
Date: Sun, 25 Jun 2000 20:58:02 -0400
Tom,
Thank you for trying to explain this to me:
On Sun, 25 Jun 2000, tomstd wrote:
> Future Beacon <[EMAIL PROTECTED]> wrote:
> >
> >
> >Files A and B are composed of the least significant two bits of
> >bytes found in news group messages (excluding headers, carriage
> >returns, line feeds, and spaces). A and B contain one megabyte
> >each of this data. In each case, these bits are strung together,
> >four pairs per byte. At least three quarters of the original
> >data available in the news group messages is not used.
>
>
> Maybe you missed a very important point. ASCII DATA IS NOT
> RANDOM!!!
>
> There will be strong biases from ANY bit you take from ascii
> characters...
I don't understand it. ASCII is a seven bit code communicated in
bytes. About a quarter of the text characters end with each of 00,
01, 10, and 11. The bias due to which letter is likely to follow
which other letter is somewhat diminished by ignoring all of the
byte except the last two bits. The question is not whether file
A or file B is perfectly random. Here is the most important of the
two questions I asked:
Can anybody characterize the degree of orderliness or predictability
of RAND (without knowing A or B)?
If it is perfectly orderly (can be described by some formula or
program) I would be amazed, but need it explained further. I don't
just "see" that the extracted data is not at all unpredictable.
To XOR the data with a message still seems make the reading of the
message difficult. Can anybody suggest a method of attack?
Here is the rest of the setting (original message):
File B is divided into two files (BP and BQ) this way: If the
first bit in A is a 0, then the first bit in B becomes the first bit
in BP. If the first bit in A is a 1, the first bit in B becomes the
first bit in BQ. In this way, each next bit in A determines whether
the next bit in B becomes the next bit in BP or BQ. When the bits
of A and B are exhausted, BQ is appended to BP and the resultant
file is called RAND.
Two people wishing to send and receive encrypted messages use the
one-time-pad method but instead of using a random number generator
to create their shared random numbers, they use the file called
RAND.
Nobody except these two people know how the news group messages are
selected and all of the files are kept secret. Does anybody know
how to attack the encrypted messages? Can anybody characterize the
degree of orderliness or predictability of RAND (without knowing A
or B)?
Thank you for your help.
Jim Trek
Future Beacon Technology
http://eznet.net/~progress
[EMAIL PROTECTED]
------------------------------
From: zapzing <[EMAIL PROTECTED]>
Subject: Re: DES 64 bit OFB test vectors
Date: Mon, 26 Jun 2000 00:57:40 GMT
DES test vectors are becoming very hard to
come by. I have this fantasy that they will
be *the* contraband of the 21st century.
People will trade them in seedy bars with
hushed voices while wearing treanch coats
and wide brimmed hats. You know, just like
those "neighborhood watch" signs. This
neighborhood cares, and all that. I always
wondered what they have against wide brimmed
hats.
In article <[EMAIL PROTECTED]>,
Jack Spencer <[EMAIL PROTECTED]> wrote:
> Hi,
>
> I need some test vectors for DES 64 bit OFB mode.
> I already have a tested DES module so OFB implementation
> is trivial. Still, it's better if I have some independent vectors.
>
> I serched the web but I only found some stale links and
> useless information.
>
> Please post the information here if you can help.
>
> Thanks,
>
> JS
>
>
--
If you know about a retail source of
inexpensive DES chips, please let
me know, thanks.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Encryption 4 the Masses?
Reply-To: [EMAIL PROTECTED]
Date: Mon, 26 Jun 2000 00:32:27 GMT
tomstd <[EMAIL PROTECTED]> wrote:
: "Pig Ear" <[EMAIL PROTECTED]> wrote:
:> Is this program any good? Has it stood up to the scrutiny of
:> the crypto community?
: What program? PGP?
Probably the one at http://www.e4m.net/
It says it uses triple-DES, IDEA, DES, Blowfish, CAST, and MDC/SHA as its
algorithms.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ VIPAR GAMMA GUPPY.
------------------------------
Subject: Re: How Uncertain?
From: tomstd <[EMAIL PROTECTED]>
Date: Sun, 25 Jun 2000 18:07:13 -0700
Future Beacon <[EMAIL PROTECTED]> wrote:
>I don't understand it. ASCII is a seven bit code communicated
in
>bytes. About a quarter of the text characters end with each of
00,
>01, 10, and 11. The bias due to which letter is likely to
follow
>which other letter is somewhat diminished by ignoring all of the
>byte except the last two bits. The question is not whether file
>A or file B is perfectly random. Here is the most important of
the
>two questions I asked:
ASCII data is not random simply because we use a language that
has a bias towards certain chars. Have you ever wondered how
programs like pkzip can compress a text file with a 75% ratio or
more? That's because it's hardly random.
So if you take a MB of text and take any bits from the chars
your output is hardly going to be random.
Tom
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
From: zapzing <[EMAIL PROTECTED]>
Subject: Re: Comments please: A protocol for Digital voting
Date: Mon, 26 Jun 2000 01:28:44 GMT
In article <[EMAIL PROTECTED]>,
Roadkill <[EMAIL PROTECTED]> wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
>
> zapzing wrote:
>
> > I think you're right. the first anonymous broadcast
> > is not needed. So only the vote needs to be broadcast
> > anonymously,
>
> Why is that? Cypherpunk and Mixmaster remailers are functioning fine
> without broadcast mechanisms <http://anon.efga.org/Remailers>. It
would
> be near impossible to track remailed messages to their origin. Only
the
> stats pages posted dayly to <news:alt.privacy.anon-server> with show
> uptime and reliability of known remailers are broadcasted.
Well when I say "anonymous broadcast protocol" I
just generally mean any old anonymous broadcast
technique that you might have lying around.
Mixmasters would probably do just fine, if you're
into that.
> Thanks for replying, I feel this subject could become important in the
> near future. (At least in the EU, where they are pushing for
> legislation against anonymising techniques)
They would have to make it illegal to
send emails outside of the EU. Come to
think of it, they would have to make
it illegal to post to usenet, too.
--
If you know about a retail source of
inexpensive DES chips, please let
me know, thanks.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: rick2 <[EMAIL PROTECTED]>
Subject: Re: DES and questions
Date: Mon, 26 Jun 2000 01:58:44 GMT
In article <[EMAIL PROTECTED]>, tomstd
<[EMAIL PROTECTED]> wrote:
> I don't know the very specifics but I believe the meet-in-the-
> middle attack is much more efficient for even-usage of DES so 2-
> des or 4-des would be easier to break then 3-des or 5-des.
>
> Here's a tip. DONT USE DES!
>
Hard to resist, it's free!
(I mean in terms of program size; it's already in the Palm ROM)
> Why not just encrypt a fixed block. The chances of getting the
> passwd wrong and the block right would be slim.
>
Thanks, that makes sense.
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: "And the survey says"
Date: 26 Jun 2000 01:35:23 GMT
Paul Pires <[EMAIL PROTECTED]> wrote:
>> second, you should also maybe consider a cipher where even if you DO know
>> part of the key, it does not help you any more than cutting down on your
>> guessing time.
> Or an indication that it is beginning to succum to cryptanalysis?
Yeah - you don't want any of those "movie" scenarios where once you get
the first digit of the PIN it locks in place and tells you you're done. :)
> I heard somewhere (and I could be wrong) that Phil Rogaway (SP?) was doing
> something similar.
Would not suprise me. He and Bellare have some very neat stuff...
-dmolnar
------------------------------
From: [EMAIL PROTECTED] (Jim Reeds)
Subject: Fish Book
Date: Mon, 26 Jun 2000 01:56:36 GMT
Readers interested in the history of 20th century cryptography
will be glad to know this news, copied from the Mersenne email
list:
THE BRITISH SOCIETY FOR THE HISTORY OF MATHEMATICS
http://www.dcs.warwick.ac.uk/bshm/
You will be glad to know that at the BSHM meeting on the history of
cryptography held in Cambridge on 24 June, one of the speakers, Professor
Donald Michie (Edinburgh), had a significant piece of good news to impart.
His news was that the report he, Good and Timms wrote about the
activities of the 'Newmanry' at Bletchley Park on WWII - cracking 'Fish'
ciphers and eventually building the Colossus machines - has now been
declassified and, after some paperwork is completed, will find its way to
the Public Records Office.
--
Jim Reeds, AT&T Labs - Research
Shannon Laboratory, Room C229, Building 103
180 Park Avenue, Florham Park, NJ 07932-0971, USA
[EMAIL PROTECTED], phone: +1 973 360 8414, fax: +1 973 360 8178
------------------------------
Subject: Re: DES and questions
From: tomstd <[EMAIL PROTECTED]>
Date: Sun, 25 Jun 2000 18:59:41 -0700
rick2 <[EMAIL PROTECTED]> wrote:
>In article <[EMAIL PROTECTED]>,
tomstd
><[EMAIL PROTECTED]> wrote:
>
>> I don't know the very specifics but I believe the meet-in-the-
>> middle attack is much more efficient for even-usage of DES so
2-
>> des or 4-des would be easier to break then 3-des or 5-des.
>>
>> Here's a tip. DONT USE DES!
>>
>
>Hard to resist, it's free!
>(I mean in terms of program size; it's already in the Palm ROM)
Well in that case I spose it could be a good idea.
Tom
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
From: Andru Luvisi <[EMAIL PROTECTED]>
Subject: Re: Question about lja1
Date: 25 Jun 2000 19:39:47 -0700
Benjamin Goldberg <[EMAIL PROTECTED]> writes:
> I saw a cipher posted some time back called lja1, but I don't remember
> any cryptanalysis on it. I have it included here since the original
> post seems to have expired.
[snip]
I did come up with an attack against one cycle, which required 2^16
chosen plaintexts and then a maximum of 2^15 trial encryptions. The
idea is to attack the last two inputs to the first round. Run them
through every possible value. For one of the values available for the
second to last, the accumulator will be zero when the last input to
the first round is processed. When this happens, what you will get as
the output is the value two ahead of it in the cycle. Now you have
the odds and evens in order, but you don't know how they go, so you
have to do 2^7 trial encryptions to figure out which way they fit
together. If none of them work, try another value for the second to
last input to the first round.
I haven't figured out how to extend this attack to any more cycles,
and I haven't identified any weak keys. This does not mean the cipher
is secure, but I have more confidence in lja1 than in my other two
entries.
Andru
--
==========================================================================
| Andru Luvisi | http://libweb.sonoma.edu/ |
| Programmer/Analyst | Library Resources Online |
| Ruben Salazar Library |-----------------------------------------|
| Sonoma State University | http://www.belleprovence.com/ |
| [EMAIL PROTECTED] | Textile imports from Provence, France |
==========================================================================
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: newbieish question
Date: Mon, 26 Jun 2000 02:54:07 GMT
In a recent post I put up, I said that a function I was looking for
should have the following two properties:
1) For any fixed key, if any bit changes in the input, approximately
half of the bits in the output should change, and
2) For any fixed input, if any bit changes in the key, approximately
half of the bits in the output should change.
I was wondering... are these properties always considered important in
cryptographic functions?
------------------------------
** 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
******************************
