Cryptography-Digest Digest #407, Volume #12 Fri, 11 Aug 00 02:13:00 EDT
Contents:
Re: Knowing when you've cracked an encryption (John Savard)
idear for new cipher (tomstd)
Re: OTP using BBS generator? (Bryan Olson)
Re: 1-time pad is not secure... ("Joseph Ashwood")
Re: Destruction of CDs ("CMan")
Re: OTP using BBS generator? (Bryan Olson)
Re: OTP using BBS generator? (Terry Ritter)
Re: OTP using BBS generator? (Terry Ritter)
Cross-platform secure chat ("Adam Smith")
Re: Destruction of CDs (tomstd)
Re: Destruction of CDs (jungle)
Re: chap authentication scheme? (Taekyoung Kwon)
Re: Cross-platform secure chat (Paul Rubin)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Knowing when you've cracked an encryption
Date: Fri, 11 Aug 2000 03:53:20 GMT
On Thu, 10 Aug 2000 17:31:56 -0700, "David C. Barber"
<[EMAIL PROTECTED]> wrote, in part:
>Anyway, afterwards there was a picture of a whole wall of rotor machines --
>at least a couple hundred -- clicking along in parallel, trying out
>combinations by mechanical brute force. BUT THEY NEVER EXPLAINED what this
>big cracking machine was doing.
The reason for that was obvious.
No, the producers weren't afraid of being shot.
But trying to explain the operating principle of the Turing Bombe on
television would
a) take too much time, and
b) cause the audience to lose interest.
There is only so much a TV show can do, and the Bombe is somewhat
complicated.
Maybe they could have added a brief comment or two to *partially*
explain what was going on, though. Like:
"This machine acted like several Enigma machines in step, testing for
relationships between successive letters in a message that would be
present if a phrase or name was in the spot in the plaintext version
of the message that the cryptanalysts had guessed."
This is about as good as a TV show could do, and it isn't terribly
illuminating.
John Savard (teneerf <-)
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
Subject: idear for new cipher
From: tomstd <[EMAIL PROTECTED]>
Date: Thu, 10 Aug 2000 20:49:06 -0700
Since newer computers are swinging to 64-bit registers it seems
like a good idea to use them but our i86 friends don't have 64-
bit registers? or do they? Hmm well the MMX registers look
pretty neato but we can't do Z math in them... oh well what
about GF math? yuppers..
What about making a cipher that uses multiplication in GF(2)^64
(I forget is that GF(2^64) or what?) since addition is xor
(pxor) and multiplication is just shifting and xoring...
we can use a round function like
F(x) = a.x + b, a != 0
the 64-bit computers and intel computers can do this very
easily.
Perhaps re-write DFC abit to use this instead of 2^64 + 13?
Tom
===========================================================
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: OTP using BBS generator?
Date: Fri, 11 Aug 2000 03:48:55 GMT
Mok-Kong Shen wrote:
[...]
> I want on the other hand once again to stress that the
> short (or long) cycles being very heatedly disputed up
> till now in this thread are those of the direct output of
> the congruence relation and NOT of the LSB. There need
> not necessarily exist a mathematically definite and
> practically useful relationship between these two types
> of cycle lengths. Since the user is using LSB, ONLY the
> cycle length of LSB is of interest to him.
The reductions from QR and factoring holds for the
unpredictability of the least significant bit (and a few
other bits at the low end according to more recent results).
All that the open question means is that even if one does
filter out short state cycles, one still has not proven a
long output cycle. This is only a problem for those who
thought the state-cycle test would prove security for each
possible key, and that would be nonsense even if we knew the
output cycle to be long.
--Bryan
--
email: bolson at certicom dot com
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: 1-time pad is not secure...
Date: Thu, 10 Aug 2000 21:12:28 -0500
> In article <OEwOLsyAAHA.138@cpmsnbbsa08>,
> "Joseph Ashwood" <[EMAIL PROTECTED]> wrote:
> > Actually the more important theory that was brought up
was quantum
> theory
> > where we do have information that indicates that unless
you can
> predict the
> > future you can't predict the future of the bit-stream.
> Believe it or not, I think we can predict the future. :)
Not everything
> of course, but something. Like predicting the US stock
market will go
> down because Greenspan has raised interest rates to slow
economic
> growth. But more importantly, science and technology
advances rapidly.
> What seems impossible now will be possible to your
grandchildren. So
> you think nothing can go faster than light? Well keeping
watching...
I didn't mean in hand waving terms. We know for example that
the sun will burn out, but we cannot determine the value to
the millisecond for the time. By how much will the stock
market go down? Of course we haven't proven that the stock
market is uncorrelated, or unpredictable, as a matter of
fact we have plenty of evidence that it is not entirely
either.The problem is that your argument is backwards, the
stated requirement for a OTP-useful RNG is that given
symbols 0-(n-1) and (n+1)-inf you cannot determine the value
of symbol n beyond a certainty of 1/(number of symbols) for
any n.
>
>
> > > And here's my original conclusion that nobody
commented on. Since
> the
> > > key is random, if someone attacks the scheme at the
key generation
> > > level, OTP is the LEAST secure because of its enormous
key length.
> > > Well, just imagine encrypting the Netscape 4.74
installation file,
> > > 19Megabytes. The key has 160,000,000 binary digits.
That's like
> > >
>
010101100...................................................
...........
> > >
>
............................................................
...........
> > > Oh Boy! If you can only guess some small key patches
with some
> > > certainty, there are 160,000,000 places for you to try
them out!
> >
> > But how do you verify it? Let's make it a bit more real.
If I encrypt
> a
> > plaintext P with 3DES, there exists a (XOR)OTP that will
generate the
> > plaintext (because under OTP all possible ciphertexts
are possible,
> and 3DES
> > must generate a subset of that). How would you begin to
generate that
> pad?
> > Of course you have only 1/(2^64) possible values to
guess, so please
> feel
> > free.
> Well lets say it wasn't an executable file but a long
series of love
> letters between a Canadian and a British spy in ascii.
Then you'll get
> meaningful plaintext if you get the right key patch at the
right spot.
Fine it's a long series of love letters say 2^38 characters,
all 3DES encrypted with a different and completely
uncorrelated and unbiassed key. There exists a pad that maps
those love letters to the original, that pad is exactly 2^38
characters long, that pad has forcibly more order than pure
random (by virtue of the knowledge that the mapping occurs
in 3DES). How would you even begin to find that pad? If you
guess a series of 1 character in the pad, then that
character is almost certainly one of the characters, but how
do you determine where it was correct from information that
looks like this (Well actually it will look much worse):
fyilsevi asdtydo ughzDFuig dwFYI LAREIPH' WRGYIF
One of those characters is actually a part of the correct
sentence, which one is it?
If you guess a 2 symbol series you have the same problem.
Only once you get into significantly sized guesses, you can
finally see words, but you'll see every word with equal
probability, so which of these words is actually the right
word in the right spot in the right letter:
Love
Lunch
Dinner
Home
Now
Help
New
Bike
Computer
Speaker
letter
miss
grill
baja
restaurant
sea
pacific
meat
here
cape
blue
water
white
sand
beaches
great
place
kick
back
to
relax
with
you
cool
fish
a
the
and
I
Take your pick, odds are only one of them is right. If you
try symbol lists much larger you'll start to guess pieces
that don't exist in the letters.
> I made a guess that this guy came up with these numbers on
a rush. And
> I'm 99% sure of that. It's not a 100% guess but under the
circumstance,
> I know I'm right! :)
Perhaps we should start over and derive the proof. It's
really not hard. Here it goes:
Unproven assumption: A random number generator exists such
that every bit has at least 1 bit of entropy.
Provable claim: XOR can not lower the entropy content of the
bits involved.
Given a text T that is unknown to the attacker.
Given a pad P taken from the perfect random number generator
perform the operation C=T XOR P
>From the assumption C MUST have at least 1 bit of entropy
per bit
Therefore C is completely unpredictable, contains no order,
and is therefore PROVEN immune to cryptanalysis.
There is no unless involved. There is no prediction of P
(otherwise it would not have entropy = 1bit/bit). There is
no prediction of T from C (by provable assumption).
Joe
------------------------------
From: "CMan" <[EMAIL PROTECTED]>
Subject: Re: Destruction of CDs
Date: Thu, 10 Aug 2000 21:19:28 -0700
Just re-label them as AOL free Internet. Nobody will ever look at them
again.
JK
--
CRAK Software
http://www.crak.com
Password Recovery Software
QuickBooks, Quicken, Access...More
Spam bait (credit E. Needham):
root@localhost
postmaster@localhost
admin@localhost
abuse@localhost
webmaster@localhost
[EMAIL PROTECTED]
[EMAIL PROTECTED]
[EMAIL PROTECTED]
Thomas Kellar <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> There was a thread on this topic a couple of weeks ago.
> I received an advertisement for a device that shreds
> CDs. If anyone is interested the company name/address is
>
> Schleicher & Co. of America, Inc.
> 5715 Clyde Rhyne Dr.
> Sanford, NC 27330-9909
>
> ph: 1 800 775 7570 email: [EMAIL PROTECTED]
>
> They claim their "501 CD shredder" can eliminate 800 to
> 1200 CDs or credit cards per hour.
>
> A disinterested party. (Actually uninterested, I would burn them
> myself.)
>
> Thomas
> --
> w8twk Freelance Systems Programming http://www.fsp.com
>
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: OTP using BBS generator?
Date: Fri, 11 Aug 2000 04:15:53 GMT
Terry Ritter wrote
[...]
> And we have yet another problem: How can we believe that the short
> cycle insecurity is the *only* one which this proof allows to exist?
> We *can* prevent the short-cycle insecurity, because we know about it.
> But we *can't* prevent other security problems about which we know
> nothing.
Well, that was a long time coming. For those who spent a
lot of effort trying to convince Mr. Ritter that the
cycle-length test didn't change the nature of the theorem, I
expect that's as close to a concession as we're going to
get.
Will he ever understand the rest? The important results on
the BBS generator is that it covers _any_ algorithmic method
of predicting the output, whether we know about that method
or not. Any security problem that happens would imply we've
run into a case where someone can factor.
--Bryan
--
email: bolson at certicom dot com
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: OTP using BBS generator?
Date: Fri, 11 Aug 2000 04:32:09 GMT
On Fri, 11 Aug 2000 13:59:33 +0100, in
<[EMAIL PROTECTED]>, in sci.crypt David Hopwood
<[EMAIL PROTECTED]> wrote:
>-----BEGIN PGP SIGNED MESSAGE-----
>
>Terry Ritter wrote:
>> [...]
>> I DO NOT ACCEPT that a cryptosystem which has a known potential
>> weakness can legitimately be called "proven secure."
Well, "preventable" weakness.
>OK, in that case you must not accept that BBS is proven secure at all,
>under any assumptions, and with or without the cycle checks.
>
>It might clarify the argument if you could confirm whether or not that is
>actually your view.
I don't really have a view about whether BB&S is secure.
On the other hand, I *know* that any random number generator is
insecure when it has traversed a cycle, and I *know* that short cycles
do exist in BB&S. Thus, I *know* that failing to prevent the use of a
short cycle is a risk.
But I also *know* the prescription in BB&S will prevent the use of
short cycles, which makes the short cycle problem an unnecessary and
preventable risk. So I *know* that "real" BB&S is arguably
"strong*er*" than the "reduced" or "simplified" BB&S which does not
check for short cycles.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: OTP using BBS generator?
Date: Fri, 11 Aug 2000 04:47:20 GMT
On Fri, 11 Aug 2000 13:59:44 +0100, in
<[EMAIL PROTECTED]>, in sci.crypt David Hopwood
<[EMAIL PROTECTED]> wrote:
>[...]
>Proofs in this area of cryptology are generally probabilistic, but they are
>*not* statistical
A distribution of values (here weakness) is a statistical entity.
When x0 values are selected at random they are random variables, which
are definitely statistical entities
The effect of random sampling from a distribution is inherently
statistical in nature.
>(there are no "statistical tests" involved).
Right. So?
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: "Adam Smith" <[EMAIL PROTECTED]>
Subject: Cross-platform secure chat
Date: Fri, 11 Aug 2000 05:07:05 GMT
Anyone know of such a thing? I know the idea of a PGPChat has been bounced
off the walls in alt.security.pgp...
I did a search on it, and it appears someone made a PGPChat back in like '94
that operated by the two users dialing into each other...LOL! : )
Although someone said it wasn't very secure...
But anyway, something in java would be great...needs to run on a
PC/Mac...any links?
Thanks!
------------------------------
Subject: Re: Destruction of CDs
From: tomstd <[EMAIL PROTECTED]>
Date: Thu, 10 Aug 2000 22:03:44 -0700
"CMan" <[EMAIL PROTECTED]> wrote:
>Just re-label them as AOL free Internet. Nobody will ever look
at them
>again.
This is the best idea so far.
Tom
===========================================================
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
From: jungle <[EMAIL PROTECTED]>
Subject: Re: Destruction of CDs
Date: Fri, 11 Aug 2000 01:40:13 -0400
tomstd wrote:
>
> "CMan" <[EMAIL PROTECTED]> wrote:
> >Just re-label them as AOL free Internet. Nobody will ever look
> at them again.
nobody with average or higher IQ ...
> This is the best idea so far.
------------------------------
From: Taekyoung Kwon <[EMAIL PROTECTED]>
Subject: Re: chap authentication scheme?
Date: Thu, 10 Aug 2000 17:11:31 -0700
Then, why don't you make CHAP stronger than you think?
One simple example is given below. Let's call this, A-CHAP (AMPlified CHAP) because it
is based upon the
amplified password proof idea; a preliminary paper on AMP is available from
http://eprint.iacr.org/2000/026.)
[assumption]
Assumption given by CHAP is that a server authenticates a client within "TWO STEPS"
only using a password. (not
mutual authentication) * two steps! cannot provide mutual authentication using a
password-like secret.
[setup]
- A client ALICE and a server BOB shares g and N. (N must be a safe prime or a secure
prime; a secure prime must
be preferred. In that sense, set M as a "suitable" prime factor of N-1 and g as a
generator of Z_M . Of course,
ALICE can register her-chosen g and N under estimation of BOB.) * suitable : large :)
- ALICE chooses her password p and registers it "securely".
- BOB coverts p to the verifier v such that v = h(s,p) for implicit salt s. (implicit
salt s can be computed from
f(ALICE, BOB) for some suitable function f(); see Boyko's paper on Eurocrypt 2000.)
*salt is only optional for
preventing text-equivalance.
- BOB stores g, N, and v.
[protocol run]
1. Server sends his random challenge to Client.
ALICE <--- g^x --- BOB
2. Client responds to Server
ALICE --- g^y, (g^xg^v)^y ---> BOB
[how it works]
Step 1: BOB chooses x at random from Z_M and computes g^x mod N.
Step 2.0: ALICE computes v from p and implicit salt s. (note again; regard s only
optionally)
Step 2.1: ALICE chooses y at random from Z_M and computes g^x mod N.
Step 2.2: ALICE computes (g^xg^v)^y mod N. <-- she may use a simultaneous
exponentiation method for efficiency.
Step 2.3: BOB fetches v and computes X = (x + v)^-1 mod M. (We called this, the
inverse of the amplified
password, but now it is the amplified verifier :)
Step 2.4: BOB computes {(g^xg^v)^y}^X and compares it to g^y.
[what it has done]
password authentication in two steps! (one-way authentication) --> more secure CHAP!
[disadvantage]
Not in step. :) Message 2 must be twice as big as message 1.
[if we use Diffie-Hellman directly]
for example, make message 2 g^xyv. It will add one more exponentiation step to BOB for
having g^yv.
[for the amplified password proof]
http://eprint.iacr.org/2000/026
Bill Unruh wrote:
> In <8mqcri$c4r$[EMAIL PROTECTED]> [EMAIL PROTECTED]
>(David A. Wagner) writes:
>
> >By the way, the vulnerability you did not mention is that, in practice,
> >most passwords are fairly easily guessable. Neither the Unix password
> >hashing scheme nor the CHAP PPP protocol provide any protection against
> >guessing attacks on your password. Your protocol does not, either.
> >In contrast, protocols like SRP (and many others in that vein) _do_
> >provide protection for low-entropy passwords.
>
> Yes, dictionary attacks are always a problem. However, if I demand that
> you are allowed only one challenge, and the respondent one response, I
> do not think that you can design anything which would be dictionary
> resistant--or can you?
--
Taekyoung Kwon [EMAIL PROTECTED]
Computer Science Division [EMAIL PROTECTED]
University of California, Berkeley How can you prove yourself?
http://www.cs.berkeley.edu/~tkwon/ (510)642-4751 ICQ#13782855
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: Cross-platform secure chat
Date: 11 Aug 2000 06:04:04 GMT
In article <ZRLk5.564$[EMAIL PROTECTED]>,
Adam Smith <[EMAIL PROTECTED]> wrote:
>Anyone know of such a thing? I know the idea of a PGPChat has been bounced
>off the walls in alt.security.pgp...
>
>I did a search on it, and it appears someone made a PGPChat back in like '94
>that operated by the two users dialing into each other...LOL! : )
Nautilus (see http://www.lila.com/nautilus/ for more info) runs on
MSDOS, Windows, and Unix/Linux. Somebody was working on a Mac port
but didn't finish, I think.
------------------------------
** 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
******************************
