Cryptography-Digest Digest #562, Volume #14 Fri, 8 Jun 01 05:13:00 EDT
Contents:
Re: DES not a group proof (David A Molnar)
Algorithms (abhijeet)
Re: Brute-forcing RC4 (S Degen)
Re: Simple C crypto (Nicol So)
Re: Def'n of bijection (Tim Tyler)
Re: Help with Comparison Of Complexity of Discrete Logs, Knapsack, and (Mok-Kong
Shen)
Re: Some questions on GSM and 3G (Mok-Kong Shen)
Re: DES not a group proof (Pascal Junod)
Re: Best, Strongest Algorithm (gone from any reasonable topic)
([EMAIL PROTECTED])
Re: Def'n of bijection ([EMAIL PROTECTED])
Re: Def'n of bijection (Tim Tyler)
Re: Best, Strongest Algorithm (gone from any reasonable topic) (Mok-Kong Shen)
Re: Def'n of bijection ([EMAIL PROTECTED])
Re: Def'n of bijection (Tim Tyler)
----------------------------------------------------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: DES not a group proof
Date: 8 Jun 2001 07:13:37 GMT
JPeschel <[EMAIL PROTECTED]> wrote:
> bucks and it appears to be a book and a CD. The on-line review, however, says
> the CD isn't
> easily readable. Has anyone here actually seen the product?
I picked up what must have been one of the first copies. It's a godsend
when trying to find papers like this. Every paper available in PDF format,
most of them from scans of the original. Some of the earlier volumes are
difficult to read onscreen, but I've never had any problem reading the
printed versions.
(I always print everything out anyway; better to mark the margins).
It's a bargain at the price. Especially if you don't have a well-equipped
library nearby.
-David
------------------------------
From: [EMAIL PROTECTED] (abhijeet)
Subject: Algorithms
Date: 8 Jun 2001 00:33:01 -0700
Hi,
I am writing my thesis on cryptography in Digital signature.
Can anyone suggest me of any book or paper where I can get
the full C or C++ code for the algorithms.
thanking you
regards
------------------------------
From: S Degen <[EMAIL PROTECTED]>
Subject: Re: Brute-forcing RC4
Date: Fri, 08 Jun 2001 09:36:53 +0200
Scott Fluhrer wrote:
>
> S Degen <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> >
> > Howmuch time would it take to brute-force a 40 bit RC4 key? (Ofcourse
> > depending on the processor-speed, but lets say a PIII 500)
> >
> > This is the case:
> > You have a 128 bit (ASCII) text, and the encyphered version of it. This
> > version is encyphered with a 64 bit secret key, but of those 64 bits, 24
> > bits are known. (Leaving 40 unkown bits)
> >
> > I would like to know how long it would approximately take to calculate
> > the 40 bit secret key.
>
> Would you mind very much if I asked what system you were attacking?
Ofcourse not, dear sir.
I am relating to the encryption of data in a Wireless LAN.
The 802.11 protocol has a 'mode' where the server uses an encryption
challenge to authorize a client. Both the server and the client have
the same secret key. The server sends the client a plaintext challenge
(unencrypted) and the client sends the encrypted challenge back,
including the Initialisation Vector used. The server checks if the key
that the client used is the correct key. The key used for encryption
is 64 bits, but the (known) IV is 24 bits. This leaves 40 bits of the
key unknown, but with the plaintext and encrypted challenge available,
it should be possible to figure out the key.
>
> --
> poncho
------------------------------
From: Nicol So <[EMAIL PROTECTED]>
Subject: Re: Simple C crypto
Date: Fri, 08 Jun 2001 03:41:17 -0400
Reply-To: see.signature
Dirk Bruere wrote:
>
> > Why even bother with crypto? Just xor the file with 0xAA.
>
> Quite likely a variant of that will be used, unless there is some
> almost-as-simple and stronger alternative.
> Hence my inquiry.
If you're willing to even consider simple obfuscation scheme like
XOR'ing with 0xAA, you can do better by XOR'ing the text to be
obfuscated with a pseudorandom sequence generated by the random()
library function of your development tool. Typically you can control the
pseudorandom sequence by specifying the seed.
This is very simple to explain to a programmer/coder, although it
provides little security in a real sense. However, that seems to be what
you're looking for.
--
Nicol So, CISSP // paranoid 'at' engineer 'dot' com
Disclaimer: Views expressed here are casual comments and should
not be relied upon as the basis for decisions of consequence.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Def'n of bijection
Reply-To: [EMAIL PROTECTED]
Date: Fri, 8 Jun 2001 07:39:23 GMT
[EMAIL PROTECTED] wrote:
: Tim Tyler <[EMAIL PROTECTED]> writes:
:> [EMAIL PROTECTED] wrote:
:>: Um, it's a mathematical term, Tim. A statement is vacuously true when
:>: it cannot possibly be false. In other words, the statement contains
:>: no information.
:>
:> I guess you think Fermat's Last Theorem is vacuous, then. It's negation
:> is known to be an impossiblity, after all.
: No. Read it again: ``vacuously true'' is a mathematical term. It can be
: looked up.
: Fermat's last theorem is only known to be true after a lengthy proof. [...]
...but now it /is/ *proven* to be true - so it cannot possibly be false.
According to you "a statement is vacuously true when it cannot possibly be
false".
Or are you now telling me you botched that definition of that
"mathematical term"? Perhaps you would like to try again?
:>: Sigh. If no compression is performed, then the likelihood of false
:>: positive decryptions is for most practical purposes zero.
:>
:> Um, plaintext: 129 bits. Key 128 bits. What on earth can you possibly
:> be talking about?
: You can't assume that |ciphertext| ~= |key|.
I'm not. I'm asserting that *sometimes* |ciphertext| ~= |key|. On other
occasions |ciphertext| may be very large compared to |key|.
:> Compression takes plausible messages and moves them (and perhaps lots of
:> other stuff) into smaller-numbered bins, while moing other files the other
:> way.
: Sure. But do you have the faintest freaking clue how many possible
: binary files there are of size less or equal to, say, this post?
What has that got to do with whether compression increases the density
of plausible-looking decrypts?
You are arguing for the density in that particuar case being low.
I agree - the density in that particular case *is* low. How does that
make the slightest difference to anything I've said?
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Help with Comparison Of Complexity of Discrete Logs, Knapsack, and
Date: Fri, 08 Jun 2001 09:56:38 +0200
sisi jojo wrote:
>
> > Joseph Ashwood <[EMAIL PROTECTED]> wrote:
> >
> > > Take a simpler problem 1+1=2, everyone learns that in 1st grade (some
> > > earlier, some a little later), but it takes a doctorate in
> > > mathematics, and a few hundred pages of very intricate math to prove
> > > it without assuming things.
> >
> > I don't have such a doctorate, but... What other meaning of the symbol
> > `2' did you have in mind that might conflict with it being the value
> > formed by adding the multiplicative identity of the ring of integers to
> > itself? (Proof that 1 + 1 is not equal to 0 or 1, the two integers
> > actually named in the integer axioms, is immediate from the properties
> > of the ordering on integers, so a separate symbol is justified.)
> >
> > -- [mdw]
>
> Actually we had to prove 1+1=2. I was a freshman. It was the first math
> assignment I had in Univ. The course was proving technique. Back then I
> thought Univ edu was very weird.
I suppose Joseph Ashwood was referring to the known fact
that in the book of Whitehead and Russell 1+1=2 was only
proved after having first developed sufficient foundations
that occupied several hundred pages of other materials
in logic. Depending on where one starts (matters assumed
or established as theorems), a mathematical proof can be
more or less long/involved.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Crossposted-To: alt.privacy
Subject: Re: Some questions on GSM and 3G
Date: Fri, 08 Jun 2001 10:09:07 +0200
Gregory G Rose wrote:
>
[snip]
> There is, indeed, a COMP-128-2, but that still
> belongs to the GSM Association, and I know
> nothing about it. This should be looked at as a
> "fix" for existing GSM rather than an evolution,
> although operators have always been able to use
> their own algorithms rather than COMP-128 anyway.
> There is a corresponding set of algorithms called
> Milenage (the name appears to be a Francophone
> in-joke, I don't know what it means) that are
> based on Rijndael, to be used for UMTS and GERAN.
> Again, that specification is available off the
> above URL.
Does this imply that there would be a free choice
between Kasumi and AES? Thanks.
M. K. Shen
------------------------------
Date: Fri, 8 Jun 2001 10:20:47 +0200
From: Pascal Junod <[EMAIL PROTECTED]>
Subject: Re: DES not a group proof
On 8 Jun 2001, JPeschel wrote:
> This sounds like it includes what Patrick wanted and more. The cost is 109
> bucks and it appears to be a book and a CD. The on-line review, however, says
> the CD isn't
> easily readable. Has anyone here actually seen the product?
Yes. There is an HTML interface and the papers are scanned and stored in
PDF format. Furthermore, there is a search engine. It's a nice CD.
A+
Pascal
--
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
* Pascal Junod, [EMAIL PROTECTED] *
* Security and Cryptography Laboratory (LASEC) *
* INF 240, EPFL, CH-1015 Lausanne, Switzerland ++41 (0)21 693 76 17 *
* Place de la Gare 12, CH-1020 Renens ++41 (0)79 617 28 57 *
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
------------------------------
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
From: [EMAIL PROTECTED]
Date: 08 Jun 2001 04:37:21 -0400
Tim Tyler <[EMAIL PROTECTED]> writes:
> [EMAIL PROTECTED] wrote:
>:
>: Don't go easy on me--give me the full-bore mathematical proof [...]
>
> You expect me to create a "full-bore mathematical proof" for something so
> obvious as to be totally unpublishable - just to satifsy your curiousity
> on usenet?
Two things you don't seem to grasp here. (1) You called this a ``forum for
scientific discussion''. Did you not know that scientific discussion is
about proving the things you say? (2) The reason I keep asking for proof
is that I've already sketched the proof that you're full of beans--but
you keep not understanding it.
You keep saying that false decrypts are ``more likely''--when what that
means is, ``before they were essentially impossible. But Now! Now they're
essentially impossible.''
> Sorry - but I have better things to do with my time than trying to
> educate the demonstrably uneducatable.
Which of us is uneducable? I have a degree which (if nothing else)
certifies me as 24-karat educable.
> I've shown you the form of the proof twice now.
Something about fish. Somehow fish were the reason that ``1 in 2^15 000''
doesn't mean ``never gonna happen before the sun turns to coal''.
>:>:> Did you miss my 129 bit message?
>:>
>:>: If that's not the only message you send, then we're NOT dealing with
>:>: only 129 bits; we're dealing with all the bits you encrypted with that
>:>: key.
>:>
>:> No - not if there are multiple messages and key per message.
>
>: If there is a separate key per message, you do realize that you have
>: a serious key distribution problem, don't you?
>
> No I don't. What if keys are already distributed?
You're right! Distributing OTPs is a *snap* if they're already distributed!
I wonder why nobody told that idiot Schneier about this? ``Bruce, there's
no problem with OTPs: what if the keys are already distributed?''
> What if I'm swapping emails with uncle Boris - and we have a whole
> floppy disc's worth of keys that we exchanged when we met a year ago?
And you didn't exchange OTPs at the time? What a boob your uncle must
be. If I you I wouldn't read his email anyway.
>: Hint: That's why one-time-pads aren't used for everything.
>
> I'm not talking about one time pads! That would be a complete waste of
> keyspace.
Cough. And one 128-bit key per 129-bit message *isn't* a complete waste
of key space? I suppose not: it saves *hundreds* of key bits per year!
Len.
--
Frugal Tip #5:
Instead of children, consider raising sea monkeys.
------------------------------
Subject: Re: Def'n of bijection
From: [EMAIL PROTECTED]
Date: 08 Jun 2001 04:45:55 -0400
Tim Tyler <[EMAIL PROTECTED]> writes:
>
> According to you "a statement is vacuously true when it cannot possibly be
> false".
No. An implication is vacuously true if it's premise cannot possibly be
true.
Since I doubt you know what that means...
The statement ``A ==> B'' means ``whenever A is true, B is of necessity
true.'' The implication can only be false if, under some condition,
A can be true while B is false. If in fact A can never be true, then
the statement ``A ==> B'' is vacuously true.
My thesis advisor (who dislikes pretentious boobs) has a pat answer
for mathematicians who say, ``Yes, I believe that the result in MY paper
implies the result in YOUR paper.'' He answers, ``True. But my result does
not imply yours.'' They usually miss the implication that ``everything is
implied by a false statement.'' If he had answered, ``Yes, vacuously,''
they would immediately realize he was calling their result false.
> I agree - the density in that particular case *is* low. How does that
> make the slightest difference to anything I've said?
Because you seemed to think that BICOM does some good in the *real*
world. In the *real* world, messages are not 129-bits long. In the
*real* world, the estimates I offered are more like it.
Len.
--
Frugal Tip #23:
Instead of installing an expensive garbage disposal, keep a small dinosaur
under your kitchen sink, like on "The Flintstones."
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Def'n of bijection
Reply-To: [EMAIL PROTECTED]
Date: Fri, 8 Jun 2001 08:43:33 GMT
[EMAIL PROTECTED] wrote:
: Your assertion to the contrary rests on the assumption that trial decrypts
: are highly likely to decompress into something which I will mistake for the
: plaintext. In other words, you are hoping that false positives are more
: likely. Unfortunately, this needs to be proven--the fact that BICOM is
: bijective (if it is indeed a fact) is not enough to conclude increased
: security.
: And by the way, that means you *DO* care how densely meaningful messages
: are mapped to compressed messages. The ``added security'' of BICOM depends
: critically on the increased likelihood that wrong keys will yield plausible
: decrypts.
Lest anyone be misled by this sort of material, I did some experiments:
Recall that the unicity distance is defined as being the length
of the cyphertext at which it becomes very likely that there is
only one correct plausible looking decrypt. (Unicity distance is
defined with respect to a language, and depends on the redundancy
of that language).
Bruce Schneier in applied cryptography gives the unicity distance for
ASCII text encrypted with varying key sizes (see page 236).
For the 256-bit key that BICOM uses the unicity distance of English text
messages is given as being 37.6 characters.
So - I took a few messages of a length that *exceeded* the unicity
distance and compressed them with BICOM.
The results are here:
Message size before size after
=========================================+===========+==========
"The weather is fine this time of year." 38 30
"There's no time quite like the present" 38 31
"The rain in Spain falls in the plains." 38 26
"There are storm clouds on the horizon." 38 31
The messages get a bit shorter.
Let's see what effect that has on the number of plausible-looking decrypts:
While I won't calculate the number of decrypts at each file size,
I will calculate how many decrypts would be plausible if the
files had been compressed to 32 characters (a figure conservatively
larger than all the actual sizes of the compressed messages).
32 characters represents 256 bits - which happens to be the size of the
BICOM key. Consequently compression to that point would have resulted
in a system where the key is as large as the message.
That won't *quite* result in every possible decrypt being possible (as it
would with a OTP) - because we are using a block cypher (where multiple
keys may decrypt a cyphertext to the same result) - but it *will* result
in more than half of the possible cyphertexts of that length being
possible - so we are dealing with the number of possible English
sentences in the decompressions of over half the 32-byte decrypts.
How many plausible-looking English sentences compress with BICOM to
32-byte files? I won't do the sums, but it is obviously a *huge*
number. I estimate that compressing a 41-byte sentence will
find one about 10% of the time - and over half of them will be
possible decrypts from a 32-byte cyphertext.
That represents a huge increase over the ~= 1 decrypt that was plausible
if encryption was applied /before/ compression.
Hopefully this demonstrates the effect that compression can have of the
proportion English plaintexts in the decompressed decrypts of
encrypted messages like the ones I gave as examples.
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Date: Fri, 08 Jun 2001 10:54:00 +0200
Tom St Denis wrote:
>
> <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > Tim Tyler <[EMAIL PROTECTED]> writes:
> > > [EMAIL PROTECTED] wrote:
> > >:> The fish are plausible plaintexts. The tank represents files
> > >:> sorted by size. Files at the end of the tank are shorter than ones
> > >:> further away. The directional swimming of the fish represents
> > >:> compression.
> > >
> > >: GLORY, GLORY HALELUJAH! NOW I GET IT! Please, please, write this up and
> > >: submit it to the Acta Mathematica...
> > >
> > > I assume you didn't understand :-( I figure that makes you a lost cause.
> >
> > Don't go easy on me--give me the full-bore mathematical proof. If you
> > like, we can trade: I'll send you a copy of my PhD thesis, and you send
> > me a copy of your actual proof.
>
> What's your thesis on? Mind sending me a copy?
Unless you are a 'collectioner' by nature, I wouldn't
in your (and my own) place access thesis in math, for these
are invariably virtually 'undigestable' by non-mathematicians.
If you already feel very comfortable reading graduate
textbooks in math (I don't unfortunately), that may not
apply for you though.
M. K. Shen
------------------------------
Subject: Re: Def'n of bijection
From: [EMAIL PROTECTED]
Date: 08 Jun 2001 05:04:49 -0400
Tim Tyler <[EMAIL PROTECTED]> writes:
> [EMAIL PROTECTED] wrote:
>:
>: Your assertion...rests on the assumption that trial decrypts are
>: highly likely to decompress into something which I will mistake for
>: the plaintext. In other words, you are hoping that false positives
>: are more likely. Unfortunately, this needs to be proven...
>
> Lest anyone be misled by this sort of material, I did some
> experiments...I took a few messages of a length that *exceeded* the
> unicity distance and compressed them with BICOM.
>
> The results are here: The messages get a bit shorter.
Holy Moly! ``Compressed messages are a bit shorter''! Stop the
presses! Get the Fields Medal committee out of bed!
> How many plausible-looking English sentences compress with BICOM to
> 32-byte files? I won't do the sums, but it is obviously a *huge*
> number.
Obviously a *huge* number, you say? Oh man, now I see it! How could I
have been so misguided before?
> Hopefully this demonstrates the effect that compression can have of
> the proportion English plaintexts in the decompressed decrypts of
> encrypted messages like the ones I gave as examples.
Yup--works like a charm for messages which are as big as 120 bytes or
so. Too bad that typical emails are 10-50 times larger than that...
Len.
PS See http://www3.sympatico.ca/mtimmerm/bicom/bicom.html#performance
for the compression ratio I assumed above.
--
Huh? There are lots of packages with compiled-in pathnames. Ever tried
moving X?
-- Dan Bernstein
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Def'n of bijection
Reply-To: [EMAIL PROTECTED]
Date: Fri, 8 Jun 2001 08:54:58 GMT
[EMAIL PROTECTED] wrote:
: Because you seemed to think that BICOM does some good in the *real*
: world. In the *real* world, messages are not 129-bits long. In the
: *real* world, the estimates I offered are more like it.
In the real world, messages can vary in length, from quite small,
to rather large.
All that can be compressed will have the liklihood of false positive
decrypts arising increased by compressing before encryption.
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
** 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
******************************
