Cryptography-Digest Digest #943, Volume #11 Mon, 5 Jun 00 03:13:00 EDT
Contents:
Re: A Ripe Pomegranate (wtshaw)
Re: XTR independent benchmarks (Paul Rubin)
RSA Algorithm ("Andrew Hamilton")
Re: XTR independent benchmarks (David A. Wagner)
Re: RSA Algorithm ("Joseph Ashwood")
Faster than light Cryptanalysis (Greg)
Re: Faster than light Cryptanalysis (S. T. L.)
Re: RSA Algorithm (S. T. L.)
Re: XTR independent benchmarks ("Eric Verheul")
Re: XTR independent benchmarks ("Eric Verheul")
Re: XTR independent benchmarks ("Eric Verheul")
Re: Faster than light Cryptanalysis ("Douglas A. Gwyn")
Re: Is OTP unbreakable? (Greg)
Re: XTR independent benchmarks (Roger Schlafly)
Re: Cipher design a fading field? (Baruch Even)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: A Ripe Pomegranate
Date: Sun, 04 Jun 2000 21:46:26 -0600
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (wtshaw) wrote:
> b47: RU--32; RUN--2257; RUNE--more than 1 million characters
> b47 was really a surprise
I seemed to have a little overflow with the last figure. I don't know the
length of the series, except that it is lots more characters than I wanted
to display, >25K lot of >.
I added the ability to do custom bases, 10 as a minimum, and the durn
thing can harvest from whatever text it gets in a gulp of 255 characters.
It allows editing of any internal set, and does not get hung up on the
finer points of what uppercase letter needs to be with what lower
caseletter.
This allows something like base 13 to work.
Consider: the quick brown fox jumps over the lazy dog
That source is made into "thequickbrownfxjmpsvlazydg" as a source for
uppercase and lowercase, upper being "thequickbrown", and lower being
"fxjmpsvlaxydg".
Since the application passes through cases, all letters can be treated,
but since true uppercase letters are missing, any encountered would pass
through unaffected.
Using quick as the key and 0 as the dump value, here is what happens to
the source text used above: nei bhbti tnoci dqg vwydy wycw rrt mzmv aoy
Pardon me, but didn't a fox almost become a dog?
Note that uppercase letters are represented by uppercase letters, and
lowercase letter are represented by lowercase letters.
I suppose you need to take the idea of case on a case by case basis; a is
an upper case letter....true, as it depends on what is is.
--
If you wonder worry about the future enough to adversely limit
yourself in the present, you are a slave to those who sell security.
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: XTR independent benchmarks
Date: 5 Jun 2000 04:54:45 GMT
In article <[EMAIL PROTECTED]>,
David Hopwood <[EMAIL PROTECTED]> wrote:
>> Where your LUCDIF parameter generation on a
>> smartcard (!) takes the time of generation of a 1024 RSA key,
>> i.e. up to 10 minutes, XTR's parameter generation takes seconds.
>
>... which explains why RSA is a poor choice for such applications,
>but *any* of the DL-based schemes (e.g. DH over GF(p), ECC, LUC*,
>or XTR) would be perfectly reasonable with respect to key generation
>time.
RSA is commonly used on smart cards for SSL client certificate
authentication. The Schlumberger cards I'm using take about 30
seconds for 1024 bit RSA key generation. Of course it would be better
if it were instantaneous, but since it's something that only happens
when the user first enroll in the system, it's not a problem. These
same cards take about 1 second to do a 1024 bit RSA signature, which
is comparable to a fast 486-based PC. Since many people used PGP on
that generation of hardware, key generation must have been acceptably
fast then too. Remember that this is persistent keys we're talking
about. You generate them once and use them for a long time.
For ephemeral key generation with forward secrecy, yes, it's better to
use something like DH.
------------------------------
From: "Andrew Hamilton" <[EMAIL PROTECTED]>
Subject: RSA Algorithm
Date: Mon, 5 Jun 2000 00:48:48 -0400
I am investigating the RSA algorithm as a means of compression. I have
noticed that taking a random message, with an entropy of 1 bit per bit, and
encrypted it with the RSA algorithm, which results in an encrypted message
containing a higher amount of either binary digit, and therefore a lower
entropy. Due to the fact that that encryption seems to lower the entropy,
it appears to be possible to compress the message.
Although Huffman coding works on each individual message, a different system
is necessary each time, so some extra information must be included, such as
a header to determine which Huffman code will be used. This seems to reduce
the information saved by the Huffman code. As the message length increases,
the probabilities for the binary digits approach .5, so any Huffman
compression must be performed on sections of the message. I have wondered
if there is any way that a compression system could be implemented by the
RSA algorithm such that a message with an entropy of 1 bit per bit could be
reduced. I am curious to know if this seems to be a useful line of
investigation, and whether anyone knows of any work which has been done in
this area.
Thanks,
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: XTR independent benchmarks
Date: 4 Jun 2000 21:56:24 -0700
In article <8hdghu$i2r$[EMAIL PROTECTED]>,
Eric Verheul <[EMAIL PROTECTED]> wrote:
> Moreover, when generating parameters for a public key
> for digital signatures, this
> typically needs to be done on a trusted device, like a
> smartcard. If this takes too long,
> users will pull out the smartcard of the reader: generation time
> is crucial.
I don't know if I'd go so far as to make this the prime desiderata!
It'd be nice to have keypair generation be relatively fast, but you
only generate a keypair once in the lifetime of the smartcard, so
maybe you don't care if it is a little slow, no? On the other hand,
if it takes many seconds each time you want to do a decryption, that's
a more serious problem that can't be so trivially brushed aside.
In general, many of your posts don't seem to make a clear distinction
between encryption times and keypair-generation times, unless I am
confused somewhere in how I am reading them... Anyway, I find that
the distinction is important. Omitting it can be confusing and even
misleading. I hope you'll agree.
> [...] using short exponents are theoretically
> risky as you don't get security from a genuine
> DL problem anymore.
I must admit don't see it yet. Why should short exponents be any
more risky than any other restricted subset of the full field?
XTR justs uses a different subset (a subgroup, instead of a set of
elements with small discrete logarithm), right? Help me out: What
am I missing here?
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: RSA Algorithm
Date: Sun, 4 Jun 2000 21:44:22 -0700
I think you need a restatement of one of crypto's basic
lemmas, the output of a strong cipher MUST be
indistinguishable from a random number. Your idea can be
distinuished from a random number by a human, therefore your
idea must not be a strong cipher. If you'd care to argue
your point a bit more, I suggest you also consider that what
you have proposed is the application of 2 algorithms, not
just one, the first one being 3DES (keyed), the second being
a keyless alteration. The strength of the first is of course
not being questioned, what I am stating is that the nesting
of the two functions, becomes highly distinguishable from
random data, and hence the stream is no longer as strong as
possible (as covered by my assertion above).
Joe
"tomstd" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> In article <OGpvl4oz$GA.326@cpmsnbbsa09>, "Joseph Ashwood"
> <[EMAIL PROTECTED]> wrote:
> >That would of course result in a cipher that would be
less
> >than perfect because it would very clearly reveal the
> >difference between your encrypted stream and random data,
> >thus what you have proposed is a method of weakening
triple
> >DES. It is well known that one can through untelligent
moves
> >weaken security.
>
> Nope afraid you are wrong again. It depends if you are
trying
> to hide the ciphertext. If not my idea is just
inefficient not
> insecure. Of course if you want to hide the ciphertext
> symmetric encryption is not the way to go about it.
>
> Just by inserting zero bits doesn't change the actual
ciphertext
> comming out of 3des (note I am not changing the input
either).
>
> Tom
>
>
> * Sent from RemarQ http://www.remarq.com The Internet's
Discussion Network *
> The fastest and easiest way to search and participate in
Usenet - Free!
>
------------------------------
From: Greg <[EMAIL PROTECTED]>
Subject: Faster than light Cryptanalysis
Date: Mon, 05 Jun 2000 05:15:23 GMT
I was just reading an article about a scientist that broke the speed of
light and how a light pulse in his experiment actually existed in two
locations simultaneously. This has severe implications for computer
technology, in that a light pulse can carry information and it can be
analyzed more independently of time.
See:
http://www.sunday-
times.co.uk/news/pages/sti/2000/06/04/stifgnusa01007.html
What this means for cryptanalysis is that solving the problem of a
brute search of a key space may not take much time as one might think
once this technology is better developed. One might be able to
eventually build a computer in which a key is tested in its entirety by
the same time the test starts, thus no time is taken to test a key.
Thus a key space may be tested in relatively no time compared to today.
Think of the implications!
How far off is this? Anyone's guess. I would not be surprised if I
saw a first generation computer in my life time. Not at all.
--
There is only one gun law on the books- the second amendment.
The only vote that you waste is the one you never wanted to make.
RICO- we were told it was a necessary surrender of our civil liberties.
Asset Forfeiture- the latest inevitable result of RICO.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (S. T. L.)
Subject: Re: Faster than light Cryptanalysis
Date: 05 Jun 2000 05:39:26 GMT
<<I was just reading an article about a scientist that broke the speed of
light>>
The article you referenced said:
<<The process, known as tunnelling, has been used to make some of the most
sensitive electron microscopes. >>
This is an already-known phenomenon, discussed in Discover magazine. When a
wave packet hits a barrier and tunnels through, it is shifted forward but the
actual speed of the packet is unaffected. It's a QM "cheat" and GR is
unaffected, but it may be useful in technology.
-*---*-------
S.T.L. Quotes page: http://quote.cjb.net Now playing: Half-Life
"Never invest in something that violates a conservation law" - John Walker
"If anyone wants a hole in the ground, nuclear explosives can make big holes" -
Edward Teller
------------------------------
From: [EMAIL PROTECTED] (S. T. L.)
Subject: Re: RSA Algorithm
Date: 05 Jun 2000 05:44:25 GMT
<<I am investigating the RSA algorithm as a means of compression.>>
This is like investigating a Buick as a means of food preparation. It won't
work.
<<I have noticed that taking a random message, with an entropy of 1 bit per
bit,>>
A completely, true random message, you mean.
<<and encrypted it with the RSA algorithm, which results in an encrypted
message containing a higher amount of either binary digit, and therefore a
lower entropy.>>
A lower entropy PER BIT, because it's been inflated by RSA to the size of the
modulus.
<<[REGARDLESS] to the fact that that encryption seems to lower the entropy [PER
BIT], it appears to be [IM]possible to compress the message.>>
RSA output is incompressible - otherwise, we could break RSA much easier than
we can now. The golden rule is: compression _after_ encryption is worthless.
There are supposed to be no patterns in securely encrypted data, and
compression algorithms work by finding patterns. Gain a greater theoretical
understanding of the subject, as it seems you know compression much better than
RSA. Sorry for being nasty, but this seems to be the second time you've posted
this.
-*---*-------
S.T.L. Quotes page: http://quote.cjb.net Now playing: Half-Life
"Never invest in something that violates a conservation law" - John Walker
"If anyone wants a hole in the ground, nuclear explosives can make big holes" -
Edward Teller
------------------------------
From: "Eric Verheul" <[EMAIL PROTECTED]>
Subject: Re: XTR independent benchmarks
Date: Mon, 5 Jun 2000 07:15:29 +0200
> In general, many of your posts don't seem to make a clear
distinction
> between encryption times and keypair-generation times, unless
I am
> confused somewhere in how I am reading them... Anyway, I find
that
> the distinction is important. Omitting it can be confusing
and even
> misleading. I hope you'll agree.
I agree.
> > [...] using short exponents are theoretically
> > risky as you don't get security from a genuine
> > DL problem anymore.
>
> I must admit don't see it yet. Why should short exponents be
any
> more risky than any other restricted subset of the full field?
> XTR justs uses a different subset (a subgroup, instead of a
set of
> elements with small discrete logarithm), right? Help me out:
What
> am I missing here?
Theoretically I said. The underlying problem is a DL problem
with
a non algebraic restriction (namely on the size of the DL), i.e.
not a
genuine DL problem.
Eric
------------------------------
From: "Eric Verheul" <[EMAIL PROTECTED]>
Subject: Re: XTR independent benchmarks
Date: Mon, 5 Jun 2000 07:22:26 +0200
> > And yes, if you precompute the LUCDIF parameters the actual
> > public key generation will take seconds, but then a lot of
users
> > will share the same parameters (like with ECC): this is not
advisable.
>
> Why is it not advisable? Just like any other DL-based
cryptosystem,
> parameters for LUC* should be chosen conservatively large
enough to
> make the precomputation stage of index calculus discrete log
algorithms
> infeasible. In that case it doesn't matter that users share
parameters.
Because, then "attackers" can focus on a few (common)
parameters,
both cryptanalytically and computationally. Perhaps for certain
parameters
(if you focus on them) there exist non subexponential time
attacks.
In other words: don't let the security of many (all?) people
depend of
the quality of one lock.
Eric
------------------------------
From: "Eric Verheul" <[EMAIL PROTECTED]>
Subject: Re: XTR independent benchmarks
Date: Mon, 5 Jun 2000 07:31:10 +0200
> >The point is that you said: "XTR is actually slower than
> >LUCDIF", and I'm disproving that.
>
> No, what I said was that "XTR is actually slower than LUCDIF
in this
> test", which clearly does not include parameter generation.
Plus I
> already said that I agree with you about LUCDIF having slower
> parameter generation. What else do you want?
Ok.
> >This seems like an implementational issue to me. By choosing
the
> >right optimalizations, XTRDIF can be made a lot faster than
> >LUCDIF.
>
> I have already improved XTR's performance beyond the claims in
your
> own paper. If you believe XTR can be made even faster (which I
do
> think is possible given enough effort), then please show us
how,
> preferably with code.
We're working on it.
> And what are the practical ways to avoid a group membership
validation
> in XTR? I didn't see anything in the paper about this issue.
Group membership validation can be avoided in higher layers as
well.
And we have more results on XTR, than in the crypto paper. There
will
be more papers on XTR.
Eric
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Faster than light Cryptanalysis
Date: Mon, 05 Jun 2000 05:59:14 GMT
"S. T. L." wrote:
> It's a QM "cheat" and GR is unaffected, but it may be useful in
> technology.
In particular, information is not transmitted (in any controlled
fashion) faster than light. It appears to be just the difference
between phase velocity and group velocity, which is not new.
------------------------------
From: Greg <[EMAIL PROTECTED]>
Subject: Re: Is OTP unbreakable?
Date: Mon, 05 Jun 2000 06:13:02 GMT
> My estimates always assume that the adversaries are smarter,
> richer, and better-looking than me.
Do they also have beautiful babes hanging off their arms in skimpy
bikinis? If so, your adversary may be in fact 007!
--
There is only one gun law on the books- the second amendment.
The only vote that you waste is the one you never wanted to make.
RICO- we were told it was a necessary surrender of our civil liberties.
Asset Forfeiture- the latest inevitable result of RICO.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Roger Schlafly <[EMAIL PROTECTED]>
Subject: Re: XTR independent benchmarks
Date: Sun, 04 Jun 2000 23:58:42 -0700
"David A. Wagner" wrote:
> Does the following summary of XTR advantages and disadvantages look right?
> + Pro: low-bandwidth, like ECC
Lower bandwidth than RSA or DH, but still over twice the
bandwidth of ECC.
> + Small pro: relatively fast keypair generation
> (but this is probably less important, except where you want forward secrecy)
> - Con: it's slow
it looks like the jury is still out on the speed question.
------------------------------
From: Baruch Even <[EMAIL PROTECTED]>
Subject: Re: Cipher design a fading field?
Date: Sun, 04 Jun 2000 21:29:19 +0200
In article <8hduhf$brk$[EMAIL PROTECTED]>, [EMAIL PROTECTED]
wrote:
> (b) I wish professional cryptographers would quit inventing a plethora
> of new encryption schemes a.k.a. AES, until the have figured out how to
> defeat the existing ones e.g. DESX, Triple-DES, IDEA, Blowfish, GOST, ad
> infinitum. This is exactly my point, why use a new cipher when it may
> or may not be more secure than the old one?
>
>> > Will AES be the -final- cipher?
>>
>> Of course not. It won't even be the final encipherment scheme that
>> somebody eventually figures out how to crack.
>
> No one has figured out how to 'crack' the old ones. DES has never been
> cracked in a practical sense. In fact, cryptanalysis has done more to
> prove the strength of DES than to prove the weakness.
>
> With all the cryptanalysis going on, almost no -practical- attacks have
> been invented. Is the reason that no practical attacks exist? If no
> practical attacks can be proven to exist, why use something new?
>
> --Matthew
The "problem" with cryptanalysis is that for mostly everything it does
not say "this encryption is strong" it usually can say "this encryption
has some weakness". The whole notion of security lies with the fact
that for a certain accepted cipher there is no known near practical
weakness. If a weakness is such that within a decade or so it will be
practical to attack the cipher with it then the cipher is weak now since
we do not know the computation power of our "enemy".
DES for example has already reached its end of life since for about
$200,000 you can build a machine that will find the encryption key
in about 3 days. So for all practical means it is broken.
Triple-DES is secure but is rather slow, so the AES intention is to
bring forth a cipher that will both be at least as secure as 3DES
and at least as fast as DES.
Regarding your complaint that cryptographers should stop spewing
ciphers and start breaking the ones we know, well, it is by trying that
you learn, so if you just stick your head in a wall, it might be better
to try and design a cipher and attack it, maybe you'll learn how to
better attack something, you might find a new attack that is easier
to employ on your new cipher and use that on something else (though
FEAL is being used to field-test new attacks already).
Anyway, non-practical attacks might become practical in a few years.
Nothing is learned in a big-bang, usually a slow and tedious process
will bring forth the knowledge required to practically attack a known
cipher.
Baruch
------------------------------
** 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
******************************
