Cryptography-Digest Digest #757, Volume #9 Thu, 24 Jun 99 02:13:04 EDT
Contents:
Re: authentication wish list (John Wasser)
Re: one time pad (Greg Ofiesh)
Re: On an old topic of internet publication of strong crypto (Greg Ofiesh)
Re: Encryptor that fits on a disk? (Hate Spam)
Re: one time pad (Terry Ritter)
Re: Wired magazine: What does it do? SOLUTION (John Wasser)
Re: CAST-256 implementation (?) ([EMAIL PROTECTED])
Re: Secure broadcast ([EMAIL PROTECTED])
Re: one time pad (Christopher)
Link Error Compiling FreeLIP on Win/NT VC 6.0 ([EMAIL PROTECTED])
Re: one time pad (William Tanksley)
Re: Hasty Pudding Cipher -- update (Richard Schroeppel)
----------------------------------------------------------------------------
From: John Wasser <[EMAIL PROTECTED]>
Subject: Re: authentication wish list
Date: Wed, 23 Jun 1999 22:24:17 -0400
[[ This message was both posted and mailed: see
the "To," "Cc," and "Newsgroups" headers for details. ]]
In article <[EMAIL PROTECTED]>, Eric Boesch <[EMAIL PROTECTED]>
wrote:
> Can one achieve all of these goals simultaneously? All the
> methods I know of fall short.
I think you will need to have a challenge/response system to get some
of the features you want. You memorize a formula that you use to
transform a random number or string that a systems presents when you
are required to identify yourself. The challenges and responses
continue until the system is sure that you know the formula. The
random prompts are chosen from a large-enough set that anyone watching
will almost never see the same prompt twice.
> Shortness: My password is short and easily memorized (a weak secret).
I don't know how long the secret formula needs to be to be reasonably
secure. The simpler the formula the fewer samples someone will have
to know to discover it.
> Trustlessness: I need trust no one and no machine, except possibly
> the machine I type my password into. No other person or machine
> knows my password or can otherwise assume my identity.
You can't trust any machine or transmission medium with a password
that can be used to impersonate you everywhere! Somone watching over
your shoulder or capable of reaching the data anywhere along the path
would have your identity to use at-will.
> Transportability: I need only my password in order to authenticate
> myself, as long as I have access to the network and to client
> programs that implement this protocol.
No problem. Do you want the system to both identify you and
authenticate you with a single secret? It could be done...
The first few challenges should be enough to identify you
(assuming no two people have the same formula). Further
challenges would make the authentication more secure.
> Globality: I can use my password to prove my identity to anyone on the
> network (this may be via the authority of a certifying authority,
> key server, etc.).
No problem. All you need is your formula.
> Uncrackability: I can detect and stop dictionary/brute-force attacks
> on the password before it becomes compromised. (Brute-force attacks
> on strong secrets, such as random 128-bit keys, are not a problem.)
No problem. Authentication fails if you get any answer wrong. You
realy have to know the formula to get every answer correct.
------------------------------
From: Greg Ofiesh <[EMAIL PROTECTED]>
Subject: Re: one time pad
Date: Thu, 24 Jun 1999 02:18:01 GMT
Now put yourself in the cryptologist's position a minute. All you have
is the cipher stream and the algorithm used to build it. Let's say you
had your PC take the 100 byte segment of cipher text and:
1. produce every possible permutation of candidate pad segment
2. determine the corresponding plain text candidate
3. examine the plain text candidates and reject those that do not hold
english words
4. print out plain text candidates that appear (to the PC) to be
possible english sentences along with their pad segment candidates
And then you look through the list only to discover one plain text
candidate actually has 100 0xa7's and the message looks valid to you.
Now are you saying that you would not find that too fantastic not to
give that candidate plain text much greater weight as the possible
plain text trying to be discovered?
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: Greg Ofiesh <[EMAIL PROTECTED]>
Subject: Re: On an old topic of internet publication of strong crypto
Date: Thu, 24 Jun 1999 02:27:40 GMT
This sounds the sanest of all!
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: Hate Spam <[EMAIL PROTECTED]>
Subject: Re: Encryptor that fits on a disk?
Date: Wed, 23 Jun 1999 23:38:03 -0400
> You might want to try PGP 2.6x. Remove the documentation and
> it will fit on a disk.
you can even compress the executible using say PKLite. PGP 2.6.x becomes
about 105K. Dunno if something like that exists for UNIX (That's what I
guess you're using?)
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: one time pad
Date: Thu, 24 Jun 1999 03:25:52 GMT
On Thu, 24 Jun 1999 00:23:06 GMT, in <7krtp0$mpl$[EMAIL PROTECTED]>, in
sci.crypt Greg Ofiesh <[EMAIL PROTECTED]> wrote:
>you said:
>
>> False. The key word here is "guarantees." Unless we have a proof
>> which applies in practice, there can be no such "guarantee" in a
>> realized cipher.
>>
>> The difference is that we have no absolute *proof*.
>> And that places the OTP firmly into the body of ciphers we know.
>
>You can say that EC or IFP encryption cannot guarantee encryption
"EC"? "IFP"?
>because it is possible to attack it using various methods. In any of
>these methods, if successful, the result is certain to be correct
>because there can only be one solution that fits the puzzle with only
>the cipher stream in hand.
Not always. Some techniques can have sufficient keyspace to produce
every possible encryption for messages of some maximum length.
In any case, we believe that finding the correct key can be very, very
difficult. It does not seem to matter much that only one possibility
will fit the mold if we cannot find that one possibility.
>You cannot say this with OTP. OTP, even if rough, as long as it lacks
>any obvious conclusions, does not let an attacker have a clue as to
>which candidate is correct.
False, if the generator produces a sequence which is in some way
predictable. And there is no way to prove that a real generator is
unpredictable.
>In this lies the guarantee (it would seem
>to me) that OTP cannot be broken, even in rough implementation.
>
>Now, let me clarify what I mean by rough implementation. I mean that
>the random numbers adhere to some rules such as a minimal number of bit
>fluctuations in the stream to prevent obvious patterns to the naked
>eye. Not much more than that.
10101010101010: lots of fluctuations, little surprise. Evidently we
need more rules. And when we have them we will need still more, and
more, and so on.
We cannot generate randomness with rules. We cannot improve
randomness with rules. We may be able to collect randomness, but that
is about it.
>If a pure and perfect (okay,
>theoretical) random generator can produce any sequence of bits, and no
>bit is dependent on any other, then you could theoretically produce
>streams of obvious patterns.
Accidental patterns are inherent in randomness.
>And this should produce weaknesses in the
>pad.
Nope. Finding "patterns" in known random data is not the problem.
The problem is any ability to *predict* specific patterns.
>Therefore, I put forth that some control must be maintained and
>that the random bits cannot be whole random. Furthermore, the controls
>must have wide margins to avoid weaknesses within itself.
As soon as we start messing with ("controlling") the generator, it is
no longer random. The opponents can take advantage of that.
Were it possible to tell whether sequence s + '0' was more random than
s + '1', we could produce the one sequence which was most random. But
everybody would know that sequence so it would be useless for
cryptography. The whole point of crypto random is the hope that it is
not possible to know what the sequence will be.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: John Wasser <[EMAIL PROTECTED]>
Subject: Re: Wired magazine: What does it do? SOLUTION
Date: Wed, 23 Jun 1999 22:34:08 -0400
[[ This message was both posted and mailed: see
the "To," "Cc," and "Newsgroups" headers for details. ]]
John Savard <[EMAIL PROTECTED]> wrote:
> Obviously, any cryptogram can be claimed to be an OTP encryption of
> any text of equal length and character set.
It doesn't even have to be the same character set.
------------------------------
Date: Wed, 23 Jun 1999 09:32:32 -0400
From: [EMAIL PROTECTED]
Subject: Re: CAST-256 implementation (?)
Now will you tell us how you *really* feel?
Horst Ossifrage wrote:
>
> [EMAIL PROTECTED] wrote:
> >
> > In article <7ke9k3$bdi$[EMAIL PROTECTED]>,
> > "Serge" <[EMAIL PROTECTED]> wrote:
> > > Do you have some reason to doubt in CAST's security? This is
> > interesting for
> > > me.
> >
> > Well at 48-rounds I seriously doubt the effectiveness of Cast-256.
> > While it may be a secure process I would rather not use a UFN because
> > the diffusion is not balanced and therefore biased. It has the reverse
> > rules but I still would not like to use it.
> >
> > I personally like pure substitution (i.e SAFER) or feistel type ciphers
> > (where the block is divided).
>
> Who gives a flying fuck what you personally think?
> If you were a 16 year old Irish girl, then maybe
> someone would care about your personal opinion,
> but as a 17 year old American boy, your
> opinion is about as valuable as a
> 3 day old cow pie.
>
> > The diffusion and mixing is rather
> > balanced which means there is a quick avalanche after very few rounds.
>
> The avalanche is slow, due to the "quad-block" structure.
> Do your homework before slapping spam all over
> my badwith.
>
> > I personally don't think CAST-256 is unsafe (what would I know
> > anyways), I just like the 64-bit versions because they are not UFNs
> > (and only have 8 rounds...)
> >
> > Tom
>
> You can take your UFNs and shove them up your UFOs, sideways!
------------------------------
Date: Wed, 23 Jun 1999 09:48:22 -0400
From: [EMAIL PROTECTED]
Subject: Re: Secure broadcast
Gene Sokolov wrote:
>
> Medical Electronics Lab <[EMAIL PROTECTED]> wrote in message > > I.
> Description:
> > > 1. The data is sold on subscription basis at about US$500/month. A
> > > 20-minutes delay would cut the value of the data 10 fold. A 2 hour delay
> > > would make this data nearly worthless.
> >
> > What about for the attacker? If it takes longer than 2 hours, is the
> > data worthless to them as well?
>
> yes.
>
> > > 3. All clients obtain individual user id/password combination once (for
> > > example when they sign the contract). Password is about 52 bit long
> > > (36**10). We assume that our way of distibuting passwords is secure. We
> also
> > > assume the password distribution procedure to be difficult/expensive to
> > > repeat often.
> >
> > 56 bit keys can be cracked in days. Call it 32 hours. A 52 bit key
> > can be cracked by brute force in 32/16 = 2 hours. You're already
> > at a marginal limit here, if it's possible you should increase this
> > key length!!
>
> I realize that 56 bit can be cracked on expensive hardware in a couple of
> days. Even worse: if password is cracked in 32 hours, it would still
> compromize the security completely because these passwords are issued just
> once. An attacker spends 32 hours once and then receives data for free
> untill password is changed (some don't change passwords in months).
> The point here is that we don't believe anyone would use anything better
> than a fast Pentium on cracking. The payoff is just too small to justify
> better hardware. When hardware gets faster, we can simply increase the
> number of characters in the password to 12 and have 62 bit. Or move to
> case-sensitive passwords and have 59 bits in 10 chars.
>
> > > II. Goal:
> > > 1. The data stream should be encrypted in such a way, that brute-force
> > > decryption is too expensive (I.1).
> >
> > Is US$250,000 too expensive? If you have 52 bit keys, you're in
> > trouble here.
>
> Yes, it is too expensive. That's why in I.1 I wrote how much data is worth
> ($500/month). I guess "too expensive" starts at about $10K.
You may be underestimating the value of a cracked password. The threat
model you presented includes only potential customers using your data
without paying for it. What about competitors? A competitor could
spend $500,000, twice what a 56-bit cracker cost a while ago, and recoup
the investment in one year with only a hundred
customers.
>
> > > 2. There should be a way to add/remove clients easily. We don't want to
> > > distribute new passwords every time a client is dropped.
> > Not a problem, but you'll have to send a session key encrypted with
> > every possible client's secret key.
>
> First you say that password can be guessed in a few hours (true), then
> suggest to use public/private encryption. That means keys are issued
> individually and stored locally. Then passwords, I can assume, would be used
> locally just to access the public keys. Then the length of the password
> would not mean much.
> On the other hand, use of RSA would require key management & royalties.
> That's something to be avoided. Is there a known way to convert
> password->symmetric key?
> How about hashing user id + password + random number and using the hash
> as a key to symmetric cypher to encrypt the session key? Individually
> encrypted session key and random number(s) would be transmitted openly with
> the stream.
>
> > to broadcast to? How much time between broadcasts and how many
> > broadcasts per hour? You may need multiple channels, but that shouldn't
> > be too much of a problem
>
> About 50 clients, 1 broadcast in 40 seconds, 200 byte each broadcast. I can
> broadcast the security data every other hour for example.
>
> > (I bet you'd like to have that problem!).
>
> My boss would love to have this problem :-)
>
> > Dr. mike
> Dr. Gene
> hook(at)aktrad(dot)ru
------------------------------
From: [EMAIL PROTECTED] (Christopher)
Subject: Re: one time pad
Date: Thu, 24 Jun 1999 00:35:45 -0400
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Terry Ritter) wrote:
_ But if we leak *any* information, then, clearly, our
_ "guarantee" is something less than one might expect.
Which would happen if it is known that there are definitely no sequences
of 100 bytes (or more) in the pad, as an example.
------------------------------
From: [EMAIL PROTECTED]
Subject: Link Error Compiling FreeLIP on Win/NT VC 6.0
Date: Thu, 24 Jun 1999 04:43:28 GMT
Hi,
I'm trying to compile FreeLIP so I can learn about generating large
primes used in public key encryption.
Lip.c compiles ok, but unfortunately I get a linker error for function
htonl
which is used in function zbfwrite.
Can anyone help me out here? Is this something that is available only
under unix?
I checked VC 6.0 help, and there is a function htonl: is this the same
one that I need to use for FreeLIP?
htonl
The Windows Sockets htonl function converts a u_long from host to
TCP/IP network byte order (which is big-endian).
u_long htonl (
u_long hostlong
);
Thanks,
Ron Bondy
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED] (William Tanksley)
Subject: Re: one time pad
Reply-To: [EMAIL PROTECTED]
Date: Thu, 24 Jun 1999 05:04:43 GMT
On Thu, 24 Jun 1999 02:18:01 GMT, Greg Ofiesh wrote:
>Now put yourself in the cryptologist's position a minute. All you have
>is the cipher stream and the algorithm used to build it. Let's say you
>had your PC take the 100 byte segment of cipher text and:
>1. produce every possible permutation of candidate pad segment
>2. determine the corresponding plain text candidate
>3. examine the plain text candidates and reject those that do not hold
>english words
>4. print out plain text candidates that appear (to the PC) to be
>possible english sentences along with their pad segment candidates
100 bytes yields 100^256 possible messages. How many of those are
plausibly valid English? And what if the sender did the right thing and
ran a compression over the data first?
If you assume that a plausibly valid message is all ASCII, you have about
100^100 messages to eyeball. Assume that there are spaces on the average
every five letters, and you have about 80^100 potential messages.
So far, your computer has rejected a huge number of messages, so huge that
it cann't be done.
>And then you look through the list only to discover one plain text
>candidate actually has 100 0xa7's and the message looks valid to you.
How many aeons did you say you had to look through this list?
>Now are you saying that you would not find that too fantastic not to
>give that candidate plain text much greater weight as the possible
>plain text trying to be discovered?
If I tried all 256 possible 'simple' keys, as you suggest, and I found
that one of them worked, I would consider myself implausably lucky,
exactly the same as if I'd started going through the keyspace in any other
order annd found a likely key.
I would stop right there and try to take it to the bank, because there is
NO WAY I'm ever going to be anything close to that lucky again in my life.
No, that's not true -- I would stop before I even started, because that's
a stupid way to try to make money. I would have to be stupider than a
person who buys a lottery ticket and thinks that "this time I might win".
And that's actually a HUGE understatement.
Space is big, right? Really, really big. Well, the number of ways to
spell a valid English message with 100 bytes makes space look small.
--
-William "Billy" Tanksley
Utinam logica falsa tuam philosophiam totam suffodiant!
:-: May faulty logic undermine your entire philosophy!
------------------------------
From: [EMAIL PROTECTED] (Richard Schroeppel)
Subject: Re: Hasty Pudding Cipher -- update
Date: 23 Jun 1999 22:28:40 -0700
I posted a note announcing my "recent progress" paper for the
Hasty Pudding Cipher at
http://www.cs.arizona.edu/~rcs/hpc
and remarked that HPC is the fastest AES candidate for bulk
encryption on 64-bit machines.
Roger Schlafly grumbled ...
> But only fastest if you use a 512-bit blocksize, something that is
> not part of the AES spec.
The AES minimum requirements are 128-bit blocksize, with 128, 192,
and 256-bit keysizes. You get extra credit for more blocksizes and
keysizes, and several of the other candidates also offer them. HPC is
the most extreme, allowing any blocksize and keysize.
My claim is that HPC is fastest for BULK encryption, such as large
files and video streams. For these data, the blocksize doesn't matter
much, while speed is important. Assuming security is adequate, would
you switch from a 128-bit to a 512-bit blocksize to double bandwidth?
Do you expect net videophones in a few years? Will you still be
using a 32-bit machine? (HPCs bulk encryption speed on an Alpha is
double DFCs, and triple the other candidates.)
Noah Paul asks (paraphrasing)
> What's 1/3 of a bit?
Most generally, a symbol chosen from a non-uniform probability
distribution can have any positive real number of bits of entropy:
A randomly chosen letter has entropy log2(26) = 4.7 bits.
A random letter chosen from English text has perhaps 3 bits.
A symbol randomly chosen from {0,1} has exactly 1 bit of entropy.
However, if the probablity of 0 is 89%, the symbol entropy is .5 bit.
(A compression program that ignores context and only considers
single-symbol probabilities will achieve these results.)
A regular block cipher does a permutation on a set of 2^N numbers,
where N is 64 for DES, and 128 for most of the AES ciphers.
Hasty Pudding can permute any set, such as digits, letters, dates, or
10-digit phone numbers. The size of the set need not be a power of 2.
If we are using HPC to encrypt single digits, then the blocksize is
log2(10) = 3.32 bits. I'm describing that as "fractional bit
encryption", for want of a better phrase. HPC doesn't work on
blocksizes of pi bits or 1/3 bit; the available sizes are 0, 1,
1.58, 2, 2.32, 2.58, ... log2(N) ... bits.
An example of an application is dealing out a Bridge hand: Each
player, and perhaps the tournament director, contributes some data
to a key (or the Spice), and then HPC is used to permute the numbers
{0,...,51}, which represent playing cards. East receives the
cards HPC(0), HPC(4), HPC(8), etc.; North gets HPC(1), HPC(5), ... .
Helger Lipmaa explains fractional blocksizes, but then asserts
> You can use any block cipher for that.
I'm puzzled about this assertion-- the constructions I've seen
amount to a Caesar cipher, which is far from a random permutation.
If the job is to shuffle a deck of cards, then "any" block cipher
can be called 52 times to generate 52 random numbers, and permute
accordingly, but this breaks badly when the deck has, say, 10^10
cards. (Imagine permuting SSNs, or phone numbers.) HPC handles
this case well, because it can encrypt any size block without
expansion.
Rich Schroeppel [EMAIL PROTECTED]
------------------------------
** 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
******************************
