Cryptography-Digest Digest #442, Volume #13 Mon, 8 Jan 01 19:13:00 EST
Contents:
Re: Comparison of ECDLP vs. DLP (David Hopwood)
Bluetooth security? ("Ingmar Grahn")
Re: xor'd text file - Cryptanalyis of Simple Aperiodic Substitution Systems
(Warning: LONG post) ("Paul Pires")
Re: xor'd text file - Cryptanalyis of Simple Aperiodic Substitution Systems
(Warning: LONG post) (Benjamin Goldberg)
Re: Differential Analysis (nobody)
Re: Comparison of ECDLP vs. DLP (Roger Schlafly)
Re: Linear analysis (Simon Johnson)
Re: Idiots guide to Montgomery multiplication (Paul Rubin)
Re: Fastest way to factor primes? (Simon Johnson)
Re: Seeking frequency distributions - freq.zip (0/1) (Michael Hamilton)
Re: Differential Analysis (David Schwartz)
Re: Need of very simple algorithms? (Mok-Kong Shen)
Re: Idiots guide to Montgomery multiplication (Simon Johnson)
Re: Fastest way to factor primes? (Bryan Olson)
Re: Fastest way to factor primes? (John Myre)
----------------------------------------------------------------------------
Date: Mon, 08 Jan 2001 21:46:11 +0000
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Comparison of ECDLP vs. DLP
=====BEGIN PGP SIGNED MESSAGE=====
DJohn37050 wrote:
> A security proof on ECDSA will be showing up shortly.
Perhaps you could post a reference here when it is available.
> It is interesting to note that in this case, the proof does not
> apply to DSA.
That *is* interesting. Do you know what the obstacle is to the proof
applying to DSA? (with assumptions about ECDHP or ECDLP replaced by the
corresponding assumptions in a subgroup of GF(p), of course)
- --
David Hopwood <[EMAIL PROTECTED]>
Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOln1cjkCAxeYt5gVAQEyPAf/ZPhLPGSKUnslAoGYt1D+xWWjGfKq6j/e
9lvMBVihDjtxW+Ter/t7tIlEulJYRWjob+lawI2ki8pU33nAEQDAONT1Aw+2vqD4
w3Sd96FpKnLJgKAKqqpJyfaHQqw+JRhdb9aOE0rposierKn7TPHfJuGdIW0kdLpX
vB8FQe2czVYepSXFuOoKTJZNVA07rbLD9PN72lezcOw4TKQ5B9MivfahlLaOm9z6
Q53V5mT9ZnYws9WrhRzM9YS2q+EF3qpr8gpfyhOlo0ZHLLMiXmFtT5MI3Pe+X+JF
qThzaBL+k5lhmvpsOK0/F+g07HlrZwe+4bg06yAwn8YN1gamLu5WKQ==
=Rz56
=====END PGP SIGNATURE=====
------------------------------
From: "Ingmar Grahn" <[EMAIL PROTECTED]>
Subject: Bluetooth security?
Date: Mon, 8 Jan 2001 23:25:01 +0100
Hi!
Are there any scientific papers that have been written about Bluetooth
security? What I'm looking for is a security/crypto analysis like the ones
that have been done for SSL/TSL or WTLS(WAP security layer)? Any hints of
where I can find this kind of info, preferably on the Internet...?
Thanks in advance!
/Ingmar Grahn
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: xor'd text file - Cryptanalyis of Simple Aperiodic Substitution Systems
(Warning: LONG post)
Date: Mon, 8 Jan 2001 14:35:12 -0800
Douglas A. Gwyn <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Paul Pires wrote:
> > ... To me, It seems that:
> > *if you can make a stream cipher that breaks the locational relationship
> > between ciphertext, state and plaintext. AND
> > *if you can make a stream cipher that automagically authenticates. AND
> > *if you can do these things without loosing the speed and simplicity
> > advantages......
> > Then, it might just be interesting.
>
> Genuine stream ciphers (e.g. those long used by government)
> often meet these requirements. It is only with the advent
> of amateur cryptology that "stream cipher" has been confuted
> with "XOR with a key stream". XORing with a key stream is
> more properly designated as a "key generator" style of
> cryptosystem, and its vulnerabilities are quite well known.
Thanks! I guess I've been asking the wrong question then.
I'll try again. Where does one go to find out about cryptanalysis
of "Genuine Stream ciphers"? By the above definition, RC-4,
Seal, Wake nor any others I have heard of seem to fit the bill.
Maybe I'm missing something again. Is it the nature of the cipher
or the mode of operation or the protocol used that transforms it
into a "Genuine stream cipher"?
Please, resist the temptation to answer with a simple yes :-)
I guess what I really want to know is what is the threshold an
idea must cross in order to become interesting to those who
know?
If I had a "Genuine stream cipher", immune to bit flipping attacks,
naturally authenticating, and can do all that for around
5 clocks per byte in software on a P2, would that illicit a
response like:
A, "Pretty mundane, why look at new methods when we
can already do that"?
Or would it be;
B, "Can I have some of that stuff you've been smoking"
What is the state of the art for the good stuff?
Thanks,
Paul
====== Posted via Newsfeeds.Com, Uncensored Usenet News ======
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
======= Over 80,000 Newsgroups = 16 Different Servers! ======
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: xor'd text file - Cryptanalyis of Simple Aperiodic Substitution Systems
(Warning: LONG post)
Date: Mon, 08 Jan 2001 23:05:43 GMT
Paul Pires wrote:
>
> John Savard <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > On Sun, 7 Jan 2001 13:14:47 -0800, "Paul Pires" <[EMAIL PROTECTED]>
> > wrote, in part:
> >
> > >What's wrong with a good stream cipher based on a
> > >cryptographically secure PRNG, used in the proper way
> > >That is different from block ciphers under the same
> > >assumptions?
> >
> > One weakness that remains, with even the one-time-pad, let alone a
> > secure PRNG, is that if an active attacker happens to _know_ one
> > particular plaintext, a bit-flipping attack, in which inverting
> > selected bits of the ciphertext results in inverting exactly the
> > same bits of the plaintext allows the attacker to alter the
> > plaintext despite not having broken the cipher, is possible.
> >
> > So this needs to be remembered, and authentication needs to be used.
>
> This is exactly what I was getting at. Stream ciphers are discussed as
> if their developement or evolution is complete. Kind of like, "These
> are the constraints of the process" rather than "More work needs doing
> on these issues". To me, It seems that:
>
> *if you can make a stream cipher that breaks the locational
> relationship between ciphertext, state and plaintext. AND
I'm confused, what do you mean by this item?
> *if you can make a stream cipher that automagically authenticates. AND
For a cipher, stream or otherwise, to authenticate, you need one of two
things: it either must output garbage if an opponent changes some bits
of the ciphertext, or it must have appended to it some sort of secure
error checking code.
For a stream cipher, the second can be done by appending a CRC or secure
hash. To do the first with a stream cipher, I would guess that if XOR
of keystream and plaintext was replaced with dynamic substitution, this
might work (maybe). See Terry Ritter's pages on that, and on his Cloak2
stream cipher.
For any block cipher, flipped ciphertext bits will result in that block
being garbage. For the error to propogate to the entire file, one
should use some sort of chaining, perhaps PCBC.
> *if you can do these things without loosing the speed and simplicity
> advantages......
>
> Then, it might just be interesting.
>
> I have been playing around with a few ideas that lead me to believe
> that the first two ideals and "Stream" are not incompatible. The third
> is a little tougher :-)
Well, the second is surely possible, and without adding significant time
or complexity, but I don't know what you mean by the first.
--
Power interrupts. Uninterruptable power interrupts absolutely.
[Stolen from Vincent Seifert's web page]
------------------------------
From: nobody <[EMAIL PROTECTED]>
Subject: Re: Differential Analysis
Date: Mon, 08 Jan 2001 23:11:45 +0000
>were fooling themselves. I wonder if it's just sci.crypt,
>or if they also send neurologists their new techniques for
>brain surgery, or NASA their designs for spaceships.
from what i can gather, this phenomenon is rampant throughout usenet
and the net generally. go to compression groups and you'll find ppl
sending out their algorithms which give 500000:1 compression...
--
pel
------------------------------
From: Roger Schlafly <[EMAIL PROTECTED]>
Subject: Re: Comparison of ECDLP vs. DLP
Date: Mon, 08 Jan 2001 15:22:11 -0800
David Hopwood wrote:
> DJohn37050 wrote:
> > A security proof on ECDSA will be showing up shortly.
> Perhaps you could post a reference here when it is available.
> > It is interesting to note that in this case, the proof does not
> > apply to DSA.
> That *is* interesting. Do you know what the obstacle is to the proof
> applying to DSA? (with assumptions about ECDHP or ECDLP replaced by the
> corresponding assumptions in a subgroup of GF(p), of course)
My hunch is that it is not really a security proof.
------------------------------
From: Simon Johnson <[EMAIL PROTECTED]>
Subject: Re: Linear analysis
Date: Mon, 08 Jan 2001 23:18:47 GMT
In article <[EMAIL PROTECTED]>,
Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
> I've read a bit about linear analysis, and I want to attempt it on my
> hypercrypt cipher, which is available at:
> http://users.powernet.co.uk/eton/guest/beng/hypercrypt.txt
>
> However, I'm having trouble seeing how to do so. I want to try and
find
> a break on reduced round (OROUNDS=1) version of hypercrypt, using
either
> the currently listed sbox (which is taken from TC5), or with the AES
> sbox.
>
> Both of the sboxen I'm considering are fairly nonlinear. I fail to
see
> how to even begin doing the linear attack on even the mixing component
> (a 4 round 16 bit fiestel), let alone on the entire cipher.
>
> The fiestel is 4 rounds since that is the minimum number needed to be
> secure against differential analysis.
>
> --
> Power interrupts. Uninterruptable power interrupts absolutely.
> [Stolen from Vincent Seifert's web page]
>
How did i know this was comming ;)
I don't have the foggest how to attempt linear cryptanalysis, where did
u find out how to do it?
Simon.
--
Hi, i'm the signuture virus,
help me spread by copying me into Signiture File
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: Idiots guide to Montgomery multiplication
Date: 08 Jan 2001 15:33:33 -0800
[EMAIL PROTECTED] writes:
> I need an idiots guide to montgomery multiplication, i have read
> numerous paper,thesis and web pages and i'm still no closer to sorting
> it out. I have a degree in electronics so i need something that
> doesn't go too deep into the maths...in fact i'm not that bothered
> abount the math i just need to know how to implemement one. I need a
> step by step guide on where each parameter comes from, how to calc
> them. I have noticed that the "mod" operator is used in many of the
> desciptions but i am tring to find a "mod" so..arrragggg..i don't
> know...please someone put me out of my misery...
The basic description is in Kaliski and Dusse's paper in Crypto 90,
called "A Cryptographic Library for the Motorola 56000" or something
similar. If you're not comfortable with the math it'll probably
be more effective to get someone to explain it to you in person than
here. It's not that difficult, just a bit much for a news post.
------------------------------
From: Simon Johnson <[EMAIL PROTECTED]>
Subject: Re: Fastest way to factor primes?
Date: Mon, 08 Jan 2001 23:30:06 GMT
In article <93dbla$ae3$[EMAIL PROTECTED]>,
Bob Silverman <[EMAIL PROTECTED]> wrote:
> In article <93d5g4$4fl$[EMAIL PROTECTED]>,
> Simon Johnson <[EMAIL PROTECTED]> wrote:
> > > > is different to asking 'Is N prime'. The complexity of factoring
> is
> > > > believed to increase expodentially with an increase in input
size.
> > >
> > > Where did you get this misinformation?
> > >
> > > (1) It is not a matter of 'belief'. Noone 'believes' your
statement.
> >
> > The meaning of the word 'belief' was not aimed at the belief that
this
> > was an expondential problem
>
> Huh? I quote from above:
>
> "The complexity of factoring is believed to increase expodentially
> (sic) with an increase in input size."
>
> That is a pretty clear statement and directly contradicts your
rejoinder
> on its own merits.
>
> >(the reason i used expondential is because
> > i was unsure or not about the actual difficultly of the problem),
>
> Then SAY THAT. Don't make a misleading mathematical statement!
>
> > > (2) The complexity most certainly is NOT exponential, as we
> > > have algorithms that are faster than exponential.
> >
> > Well if it isn't, i'm sorry for providing disinformation. But in
> > Applied Cryptography the NFS time estimate is given by the following
> > function, is this not an expondential function:
> >
> > e^(1.923+0(1))(ln(n))^(1/3)(ln(ln(n)))^(2/3)
> >
> > And if so, why not?
>
> May I suggest that you study some math before making further
> pronouncements?
> I am NOT saying "don't participate". I AM saying
> "stop making mathematical pronouncements".
> The complexity function clearly is not exponential! Why do you think
> that it is? It certainly grows more slowly than e^x. Why is this
> an issue?
Yeah, Pronouncements are fine as long as they are corrected by someone
who knows what their talking about. To be honest, its quite an
effective method of learning, what i should have done is covered my
back by saying *i'm not sure* etc... rather than proclaiming it is
fact; Which is clearly wrong.
Thanks,
Simon.
--
Hi, i'm the signuture virus,
help me spread by copying me into Signiture File
Sent via Deja.com
http://www.deja.com/
------------------------------
From: [EMAIL PROTECTED] (Michael Hamilton)
Subject: Re: Seeking frequency distributions - freq.zip (0/1)
Date: Mon, 08 Jan 2001 23:40:29 GMT
On Sun, 7 Jan 2001 00:42:18 +0100, "Erik Edin" <[EMAIL PROTECTED]>
wrote:
>Hi.
>I'm seeking frequency distributions of letters for use in cryptanalysis of a
>simple monoalphabetic cipher. I'm specifically looking for frequency
>distributions of the German language, but I'm also interested in all other
>languages. They seem to be less than easy to find on the Internet.
>Thanks.
>Erik Edin
>
>
Erik,
There must be about a billion words on the Internet written in German.
Why not count the frequencies yourself? You can do much, much more
than just simple letter frequencies in this case. For instance one
out of eight English letters is 'E', but it only starts one out of
every 50 words.
Furthermore, if you know something about the plaintext of the
messages you're trying to crack (i.e. some plaintexts omit the word
"the" hosing up the frequencies), then you can run your
program on that kind of plaintext and get a better frequency table.
Lastly, you can take much larger samples than one typically finds
in published frequency tables.
I did this for English on 2MB of text from news stories and novels
shamelessly nicked from various web sites. Thank you, Project
Gutenberg. :)
Here are some of the stats I collected. I'll attach the program, and
two examples using the statistics collected. It's written in perl,
for portability and unreadablity. It should be easy to extend to
count other statistics or other languages. It should also be easy to
find programming errors and inefficiencies. :)
English letters:
A - 0.0826 F - 0.0226 K - 0.0071 P - 0.0167 U - 0.0282 Z - 0.0007
B - 0.0158 G - 0.0198 L - 0.0426 Q - 0.0011 V - 0.0105
C - 0.0262 H - 0.0577 M - 0.0253 R - 0.0607 W - 0.0222
D - 0.0434 I - 0.0699 N - 0.0694 S - 0.0646 X - 0.0017
E - 0.1271 J - 0.0013 O - 0.0741 T - 0.0891 Y - 0.0198
English letters that start words:
A - 0.1163 F - 0.0386 K - 0.0049 P - 0.0295 U - 0.0086 Z - 0.0003
B - 0.0476 G - 0.0198 L - 0.0266 Q - 0.0025 V - 0.0084
C - 0.0411 H - 0.0538 M - 0.0476 R - 0.0236 W - 0.0668
D - 0.0303 I - 0.0814 N - 0.0241 S - 0.0759 X - 0.0002
E - 0.0212 J - 0.0045 O - 0.0650 T - 0.1462 Y - 0.0149
English letters that end words:
A - 0.0329 F - 0.0377 K - 0.0098 P - 0.0058 U - 0.0089 Z - 0.0003
B - 0.0005 G - 0.0295 L - 0.0267 Q - 0.0000 V - 0.0002
C - 0.0019 H - 0.0288 M - 0.0154 R - 0.0601 W - 0.0119
D - 0.1171 I - 0.0227 N - 0.0742 S - 0.1129 X - 0.0008
E - 0.1966 J - 0.0000 O - 0.0429 T - 0.1020 Y - 0.0606
Michael Hamilton
My email address has been encrypted using a Caesar shift of 3 to prevent spam.
------------------------------
From: David Schwartz <[EMAIL PROTECTED]>
Subject: Re: Differential Analysis
Date: Mon, 08 Jan 2001 15:35:48 -0800
nobody wrote:
> >were fooling themselves. I wonder if it's just sci.crypt,
> >or if they also send neurologists their new techniques for
> >brain surgery, or NASA their designs for spaceships.
> from what i can gather, this phenomenon is rampant throughout usenet
> and the net generally. go to compression groups and you'll find ppl
> sending out their algorithms which give 500000:1 compression...
Someone got a patent for a compression algorithm that basically says to
sort the ones and the zeros into seperate piles and then compress each
pile.
The funniest part of it is the section that attempts to explain why the
classic proof against such an algorithm is incorrect. Essentially, they
correctly state the argument that there are more patterns of 2^40 bits
than there are patterns of 2^20 bits, and hence you can't compress every
2^40 bit pattern to 2^20 bits. Then it says that this argument is
incorrect because this algorithm only compresses one pattern.
Kooks abound.
DS
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Need of very simple algorithms?
Date: Tue, 09 Jan 2001 00:47:02 +0100
Robert Scott wrote:
>
> "Brian Gladman"<[EMAIL PROTECTED]> wrote:
> >
> >What does your 'handy user' have to do encryption with? If he or she has
> >anything more than their brain it may well be good enough to run AES.
> >
> >AES is simple enough to implement in mobile phones, in hand held devices
> >like the Palm Pilot (where it is already available) and in a number of
> >scientific calculators (e.g. TI86).
>
> If you want an application that could benefit from the best security
> but still may not have the resources to run AES, consider remote
> keyless entry. A generalized crack in a widely-used cipher could
> be of great interest to a car theft ring. But the market dictates
> that the keyfobs that implement this technology have to cost under
> $1 and generally have severe RAM and ROM limitations. Can you
> implement AES is a Microchip 12C508?
Sorry that I have knowledge neither in the technical nor in
the business aspect of the application you mentioned. But
I am extremely surprised to learn that there are applications
at all that demand on the one side the level of security
offered by AES, which implies that the value/secret to be
protected is farily non-trivial, and on the other side needs
the cost of protection to be as little as less than $1.
(How much does a packet of cigarettes cost in US?) It may
be that this is simply a very bad feature of my character:
I personally consider any use of AES for such 'cheap'
applications (if such implementations are possible) to
be a high disgrace for AES. And I like to ask all who have
at least some minimum respect for the science of crypto to
refuse ever taking part in any implementation for such
applications.
M. K. Shen
================================
http://home.t-online.de/home/mok-kong.shen
------------------------------
From: Simon Johnson <[EMAIL PROTECTED]>
Subject: Re: Idiots guide to Montgomery multiplication
Date: Mon, 08 Jan 2001 23:35:53 GMT
In article <93c8qf$ar7$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> Hi,
>
> I need an idiots guide to montgomery multiplication, i have read
> numerous paper,thesis and web pages and i'm still no closer to sorting
> it out. I have a degree in electronics so i need something that
> doesn't go too deep into the maths...in fact i'm not that bothered
> abount the math i just need to know how to implemement one. I need a
> step by step guide on where each parameter comes from, how to calc
> them. I have noticed that the "mod" operator is used in many of the
> desciptions but i am tring to find a "mod" so..arrragggg..i don't
> know...please someone put me out of my misery...
>
> Thanks
>
> Jonathan
>
> Sent via Deja.com
> http://www.deja.com/
>
Yeah, x Mod y, means find the remainder when x is divided by y.
example:
7 mod 3 = 1
4 mod 2 = 0
5 mod 7 = 5
As for a paper, and idiots guide
Yours,
Simon
--
Hi, i'm the signuture virus,
help me spread by copying me into Signiture File
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Fastest way to factor primes?
Date: Mon, 08 Jan 2001 23:44:35 GMT
Simon Johnson wrote:
[...]
> Well if it isn't, i'm sorry for providing disinformation. But in
> Applied Cryptography the NFS time estimate is given by the following
> function, is this not an expondential function:
>
> e^(1.923+0(1))(ln(n))^(1/3)(ln(ln(n)))^(2/3)
Well, no it isn't.
> And if so, why not?
There are a few issues arguably worth noting:
(1.923+0(1)) is nonsense. That should be a lower-case
"o", not a capital "O" as in Applied Cryptography, or a
zero as above.
Under normal precedence rules, you need another pair of
parenthesis, around the entire exponent (everything after
"e^").
The given function is sub-linear. Note that "n" stands
for the number to be factored, not the size of bits.
As a function of the bit-size of n, the expected running
time of the GNFS is super-polynomial, but sub-exponential.
--Bryan
Sent via Deja.com
http://www.deja.com/
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: Fastest way to factor primes?
Date: Mon, 08 Jan 2001 17:01:26 -0700
Simon Johnson wrote:
<snip>
> Yeah, Pronouncements are fine as long as they are corrected by someone
> who knows what their talking about. To be honest, its quite an
> effective method of learning,
It may be "effective" to post misinformation as bait for
corrections, but it is very irritating (to those who know
you are wrong), and risks confusing large numbers of people
(who don't know you are wrong). Have a heart, and try to
stop doing this.
> what i should have done is covered my
> back by saying *i'm not sure* etc... rather than proclaiming it is
> fact; Which is clearly wrong.
<snip>
It isn't about covering yourself; it's about your effects
on everybody else. It's why we have the social contract
(i.e., netiquette).
JM
------------------------------
** 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
******************************
