Cryptography-Digest Digest #220, Volume #14 Mon, 23 Apr 01 23:13:00 EDT
Contents:
bogus speed claims (just wondering) ("Tom St Denis")
Re: 1024bit RSA keys. how safe are they? ("Brian Hetrick")
Re: 1024bit RSA keys. how safe are they? ("Tom St Denis")
Re: OTP WAS BROKEN!!! ("Alexis Machado")
Micro Video Camera Suitable for Documents? (MrDbol)
Re: Micro Video Camera Suitable for Documents? ("Tom St Denis")
Re: Gurus: Please show weaknesses in this (Brett)
Re: Micro Video Camera Suitable for Documents? (Samuel Paik)
Re: Current best complexity for factoring? (Benjamin Goldberg)
Re: Current best complexity for factoring? (David Wagner)
Re: compare PRNG (Gregory G Rose)
Re: compare PRNG ("Tom St Denis")
Re: OTP breaking strategy (Steve Portly)
Re: OTP breaking strategy ("Joseph Ashwood")
Re: Wolf's Secure Channel Theorem ("Joseph Ashwood")
Re: OTP breaking strategy ("Tom St Denis")
Re: OTP breaking strategy ("Joseph Ashwood")
Re: Wolf's Secure Channel Theorem ("Mark G Wolf")
----------------------------------------------------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: bogus speed claims (just wondering)
Date: Tue, 24 Apr 2001 01:11:09 GMT
I am just wondering who verifies the speed claims done by authors in
algorithm designs? I know a few algorithms (read anything by the counterpane
team) are a bit off. I wrote a simple cipher that employs a four 8x32's as
a round function and I get about 20 cycles per byte as compared to the 18.
Also the Twofish speed is far off afaik. Also they claim RC5 is slower then
Blowfish which is not true since my version of RC5 can encrypt at 14 cycles
per byte (RC5 with 16 rounds) as compared to the 24 they list.
What am I missing? I know they hand optimize their asm code but if they
compare them against other designs shouldn't they hand optimize those too?
Also on some smart cards I have to wonder. Rijndael is claimed to encrypt
at 4500 cycles per block on an 8051. That seems quite far fetched IMHO
since the 8051 is not the best for indexing tables etc (you can use MOVC and
MOVX but they take the acc and an extra 16-bit register DPTR). Most of the
time afaik in the designs i have done is taken addressing tables and
fetching/storing bytes.
Do people "optimisticazize" their results or are they just better coders
than myself and my friends? (The latter of which is possible but I doubt it
consider one of my friends has tons of experience in embedded software
development).
--
Tom St Denis
---
http://tomstdenis.home.dhs.org
------------------------------
From: "Brian Hetrick" <[EMAIL PROTECTED]>
Subject: Re: 1024bit RSA keys. how safe are they?
Date: Tue, 24 Apr 2001 01:16:47 GMT
"Tom St Denis" wrote ...
> I bet I could break a 1024-bit RSA key I make with under 15 seconds
> of work on a normal desktop computer.
Yes, and I can "break" my own PGP key in ten seconds by typing in my
passphrase. And if you give me five minutes' physical access to your
normal desktop computer I can "break" your PGP key, too, the next time
you decrypt something.
I interpreted the question as a query on the difficulty of
brute-forcing a 1024 bit RSA key. Clearly, a straightforward attack on
the cryptosystem mathematics is likely not the attack of choice in any
particular set of real circumstances, but I believe that was a
reasonable interpretation of the question asked. As you pointed out in
a previous post, the reasonableness of the question itself is somewhat
questionable.
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: 1024bit RSA keys. how safe are they?
Date: Tue, 24 Apr 2001 01:19:59 GMT
"Brian Hetrick" <[EMAIL PROTECTED]> wrote in message
news:3u4F6.31953$[EMAIL PROTECTED]...
> "Tom St Denis" wrote ...
> > I bet I could break a 1024-bit RSA key I make with under 15 seconds
> > of work on a normal desktop computer.
>
> Yes, and I can "break" my own PGP key in ten seconds by typing in my
> passphrase. And if you give me five minutes' physical access to your
> normal desktop computer I can "break" your PGP key, too, the next time
> you decrypt something.
>
> I interpreted the question as a query on the difficulty of
> brute-forcing a 1024 bit RSA key. Clearly, a straightforward attack on
> the cryptosystem mathematics is likely not the attack of choice in any
> particular set of real circumstances, but I believe that was a
> reasonable interpretation of the question asked. As you pointed out in
> a previous post, the reasonableness of the question itself is somewhat
> questionable.
Bingo. I've made my point. ShaZam.
Too many people ask that question "Is a XXX-bit key safe?" when they should
ask "Is a XXX-bit key in YYY doing ZZZ safe?"....
Tom
--- I lost my .02c now I can't afford university... oh well should goto the
bank and get my 10g line of credit... ShaZam I'm broke!
------------------------------
From: "Alexis Machado" <[EMAIL PROTECTED]>
Subject: Re: OTP WAS BROKEN!!!
Date: Mon, 23 Apr 2001 22:24:43 -0300
Reply-To: "Alexis Machado" <[EMAIL PROTECTED]>
"nugatory" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> newbie wrote:
> >
> > OTP was broken!
> > It is not a joke.
>
> There's an interesting but underappreciated
> class of problems: minimal-length proofs. When
> I was in college, I watched a really excellent physicist
> write down at the top of a piece of 8.5x11 notebook
> paper the statement that the speed of light is constant
> in all inertial frames. The challenge was to find a
> convincing argument that got to E=mc^2 at the bottom of
> the same sheet of paper.
>
> So here's a challenge: What is the shortest possible
> argument that will convince an intelligent layman
> that an OTP cannot broken (as long as the "one-time" part
> is honored)? It should be *much* shorter than a
> derivation of E=mc^2.
Consider
1) c = m xor k the relation of ciphertext, message and key bits
2) P(x) the probability of x = 1
3) "+", " " , "~" are "or", "and", "not"
P(m | c) = P(m c) / P(c)
= P(m (c xor m)) / P(k xor m)
= P(m (~k m + ~m k)) / P(k xor m)
= P(~k m) / P(k xor m)
= P(~k) P(m) / [P(k) + P(m) - 2 P(k) P(m)]
= (1/2) P(m) / [(1/2) + P(m) - 2 (1/2) P(m)]
= P(m)
---
Alexis
------------------------------
From: [EMAIL PROTECTED] (MrDbol)
Date: 24 Apr 2001 01:27:50 GMT
Subject: Micro Video Camera Suitable for Documents?
Hi,
I need a micro video camera that can clearly capture text (every single letter)
on a document from reading distance (1-2ft). For example, you sit down and you
sign a contract and you have the camera on your chest, I want the camera to be
able to capture every single letter, and the whole page legibly so that it can
clearly be read and understood when it is played back on the VCR. Which
micro-video camera do you recommend? Which micro-video camera do I need?
Thank you for your time, I appreciate it. Please email all responses in
addition to the post.
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Micro Video Camera Suitable for Documents?
Date: Tue, 24 Apr 2001 01:34:36 GMT
"MrDbol" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Hi,
>
> I need a micro video camera that can clearly capture text (every single
letter)
> on a document from reading distance (1-2ft). For example, you sit down and
you
> sign a contract and you have the camera on your chest, I want the camera
to be
> able to capture every single letter, and the whole page legibly so that it
can
> clearly be read and understood when it is played back on the VCR. Which
> micro-video camera do you recommend? Which micro-video camera do I need?
>
> Thank you for your time, I appreciate it. Please email all responses in
> addition to the post.
Why did you post this request here?
Why not use a disposible camera? hehehe
------------------------------
From: Brett <[EMAIL PROTECTED]>
Subject: Re: Gurus: Please show weaknesses in this
Date: Mon, 23 Apr 2001 21:39:17 -0400
Reply-To: [EMAIL PROTECTED]
Scott Fluhrer wrote:
> This is vulnerable to standard "crib-dragging" techniques.
Thankyou. A very fine description of how it is weak. I
see how this seemingly strong route is much less than perfect.
Brett
------------------------------
From: Samuel Paik <[EMAIL PROTECTED]>
Subject: Re: Micro Video Camera Suitable for Documents?
Date: Tue, 24 Apr 2001 01:50:41 GMT
> I need a micro video camera that can clearly capture text (every single letter)
> on a document from reading distance (1-2ft).
Do you mean at the same time? As in, one image captures the entire document?
If so, you probably need at around
200 dpi * (8.5 in x 11 in) => 1700 pixels x 2200 pixels capture format.
This is not a format you can display on a VCR.
Otherwise, if you scan, you don't actually need very high resolution,
you need something with a lens intended for that distance with a
sufficient magnification (which depends on the format of your imaging
device).
--
Samuel S. Paik | [EMAIL PROTECTED]
3D and digital media, architecture and implementation
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Current best complexity for factoring?
Date: Tue, 24 Apr 2001 01:55:04 GMT
Terry Boon wrote:
>
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> On Wed, 18 Apr 2001 17:03:02 -0700, Joseph Ashwood <[EMAIL PROTECTED]>
> wrote:
>
> >"Terry Boon" <[EMAIL PROTECTED]> wrote in message
> >news:[EMAIL PROTECTED]...
>
> >> On Wed, 11 Apr 2001 06:37:36 GMT, Samuel Paik <[EMAIL PROTECTED]> wrote:
>
> [discussing method of generating random n-bit prime - snip]
>
> >> >Generally, pick random odd n-bit number (this means the high order
> >> >bit and low order bit are set to 1 and the rest of the bits are
> >> >chosen randomly). Test for probabilistic primality. If not
> >> >prime, increment by 2 and go to test, otherwise, accept as prime.
>
> [snip]
>
> >> Does this not bias the "random" selection of a prime towards primes
> >> which come after a long run of composites?
>
> [snip]
>
> >Well if that doesn't work for you try:
> >pick a random number
> >repeat until prime
> >It'll work, but it'll be a slower process.
>
> [snip - more algorithms]
>
> I agree that these will produce an unbiased distribution, at the cost
> of more processing time and more random bits than the add-two method.
>
> I wonder if there is an efficient algorithm (say, polynomial in the
> number of bits) which minimises the (expected) number of of random
> bits needed.
x = random n bit number
do {
x = (((x & ~(1<<n)) ^ randbit()) << 1) | (1<<n) | 1;
} while( !primetest( x ) );
This is much less biased than the add two method, since it continuously
intruduces entropy with each trial x.
[snip]
> But for all the trouble that some people seem willing to go to to
> generate random bits, it seemed a little strange to bias the
> subsequent prime generation...
Well, suppose that you're going through an enormous amount of trouble to
get some random bits, and your method is very slow. You want to use as
few bits as possible.
--
Sometimes the journey *is* its own reward--but not when you're trying to
get to the bathroom in time.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Current best complexity for factoring?
Date: 24 Apr 2001 01:59:57 GMT
Benjamin Goldberg wrote:
>Terry Boon wrote:
>> But for all the trouble that some people seem willing to go to to
>> generate random bits, it seemed a little strange to bias the
>> subsequent prime generation...
>
>Well, suppose that you're going through an enormous amount of trouble to
>get some random bits, and your method is very slow. You want to use as
>few bits as possible.
I don't know. We've got algorithms (e.g., AES-CTR) that take a
short, truly random seed and stretch it into a pseudorandom n-bit
string with about 2n clock cycles. What's the cost of a primality
test on a n-bit prime? I don't know, but I bet it is much greater
than 2n clock cycles. This back-of-the-envelope analysis suggests
that the randomness is unlikely to be the bottleneck.
------------------------------
From: [EMAIL PROTECTED] (Gregory G Rose)
Subject: Re: compare PRNG
Date: 23 Apr 2001 19:07:55 -0700
In article <q9%E6.36099$[EMAIL PROTECTED]>,
Tom St Denis <[EMAIL PROTECTED]> wrote:
>All diehard can tell you is "given my battery of tests this output seems to
>be [not] very well distributed". It's not a secure/unsecure test.
It's a good "insecurity" test... if it says the
output is not well distributed, the cipher is
definitely not secure. However, a positive output
says almost nothing positive about the security.
I'm sure that's what you meant.
Other packages are Crypt-X from the Queensland
University of Technology, and the tools developed
for NESSIE which I think are at
http://www.cryptonessie.org .
Greg.
--
Greg Rose INTERNET: [EMAIL PROTECTED]
Qualcomm Australia VOICE: +61-2-9817 4188 FAX: +61-2-9817 5199
Level 3, 230 Victoria Road, http://people.qualcomm.com/ggr/
Gladesville NSW 2111 232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: compare PRNG
Date: Tue, 24 Apr 2001 02:10:46 GMT
"Gregory G Rose" <[EMAIL PROTECTED]> wrote in message
news:9c2n5r$[EMAIL PROTECTED]...
> In article <q9%E6.36099$[EMAIL PROTECTED]>,
> Tom St Denis <[EMAIL PROTECTED]> wrote:
> >All diehard can tell you is "given my battery of tests this output seems
to
> >be [not] very well distributed". It's not a secure/unsecure test.
>
> It's a good "insecurity" test... if it says the
> output is not well distributed, the cipher is
> definitely not secure. However, a positive output
> says almost nothing positive about the security.
>
> I'm sure that's what you meant.
Sorta. A good PRNG can fail the diehard tests though... Remember that at
some time a truly random bit generator must output a string of millions of
bits of '1'. That would be random.
Tom
------------------------------
From: Steve Portly <[EMAIL PROTECTED]>
Subject: Re: OTP breaking strategy
Date: Mon, 23 Apr 2001 22:13:02 -0400
Tom St Denis wrote:
> "newbie" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > What is a random process?
> > What it appears today to be truly random will be very predictable
> > tomorrow.
> > Randomness is nothing more than some mechanisms above our actual
> > computational power.
>
> And simply because you believe this, I say READ A BLOODY BOOK YOU DARN
> FOOL!!!!!
>
> BTW two random bits xor'd together gives me 0, what are the two bits (one
> guess only please).
>
> Tom
Ya but not everybody can produce random salt of the quality you can Tom.
Think about all the people that are using watered down PRNG's with only small
quantities of unreproduceable entropy. I bet some of the newer super
computers working off of an advanced chaos theory could beat the house in
Vegas.
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: OTP breaking strategy
Date: Mon, 23 Apr 2001 19:07:36 -0700
"newbie" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> What is a random process?
Well for example it is believed that the decay of radioactive substances is
random in timing. It is difficult to find a perfect random source, in fact
it is difficult enough that not a single one is known.
> What it appears today to be truly random will be very predictable
> tomorrow.
That statement is true, but read it carefully, you have the word *appears*
that is different from randomness. the appearance of randomness can be
dictated by either lack of knowledge or by true randomness. Those instances
where it is dictated by lack of knowledge may soon no longer appear random.
Those that are based on true randomness will forever be random.
> Randomness is nothing more than some mechanisms above our actual
> computational power.
Wrong. Randomness is a measure of the unknowability of a problem. To take
something that has been mathematically proven to be wholly entropic (which
is equivalent to being perfectly random) and move it from the class of
perfect randomness would require proving that the foundations of the
mathematics involved in the initial proof were wrong.
The vast majority of your statements are either plainly wrong, and could be
corrected with even the most trivial of readings, or are right but are not
the statement you intended to make (see the "appears" statement above). I
encourage you to think properly through your posts, do a significant amount
of reading on the subject and actually learn. You have clearly stated
through your name that you are a newbie, it is only your deception to
yourself through which you have declared yourself of infinite knowledge on
the subject of randomness. Unlike you many of us have dedicated a
significant number of years to the pursuit of actual knowledge on the
subject of cryptography, this has included knowledge in random numbers and
entropy. Would you so argue with an English professor on the use of the word
'the' by claiming that it belonged at the end of every sentence?
Joe
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Wolf's Secure Channel Theorem
Date: Mon, 23 Apr 2001 19:19:47 -0700
It does not imply multiple channels any more than having one molecule of
water in a river implies more than one river. I think maybe it would be best
to explain it that way.
Your question is roughly the same as "How much water can a river have
running through it each second assuming the river is 1 meter long?" the
answer is roughly the same, you can build a river of arbitrary width, it is
still one river.
As to how I got the maximum number of toggles a switch can go through for
during a finite time. I was treating light as a non-particle, nothing more
than a mathematic curve, given this we can reduce the distance on the curve
that is revealed until there is the last finite amount of it revealed, going
to infinite values causes a point which is not a curve.
So picture this, a sin wave. Now assuming the other end knows it's a
particular sin wave, and that the other end knows when you could be flipping
the switch, what is the least amount of the curve necessary to seperate it
from a point or a line? Well you must have more than two points (two points
determine a line). Considering that the 3+ points can be infinitely close
together but not simultaneous, we only need to avoid the degenerate
situation where they become the same point. Since the degenerate case only
happens when the sampling hits infinite values (otherwise simply sampling
faster gives you non-simultaneous points). So you can toggle at any value
below infinite Hertz. Does that make a bit more sense?
Of course treating light as a particle will give you different results, and
certainly they won't act at infinity like the wave method.
Joe
"Mark G Wolf" <[EMAIL PROTECTED]> wrote in message
news:9c2j7i$27p4$[EMAIL PROTECTED]...
> Nope, I don't quite follow on the second part, and parallel implies more
> than one channel.
>
>
>
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: OTP breaking strategy
Date: Tue, 24 Apr 2001 02:28:08 GMT
"Steve Portly" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
>
> Tom St Denis wrote:
>
> > "newbie" <[EMAIL PROTECTED]> wrote in message
> > news:[EMAIL PROTECTED]...
> > > What is a random process?
> > > What it appears today to be truly random will be very predictable
> > > tomorrow.
> > > Randomness is nothing more than some mechanisms above our actual
> > > computational power.
> >
> > And simply because you believe this, I say READ A BLOODY BOOK YOU DARN
> > FOOL!!!!!
> >
> > BTW two random bits xor'd together gives me 0, what are the two bits
(one
> > guess only please).
> >
> > Tom
>
> Ya but not everybody can produce random salt of the quality you can Tom.
> Think about all the people that are using watered down PRNG's with only
small
> quantities of unreproduceable entropy. I bet some of the newer super
> computers working off of an advanced chaos theory could beat the house in
> Vegas.
Ahh, but random is just subjective. If *you* can't tell the bits with a
prob greater than 1/2 then they are random from your POV. Obviously me with
the key can know.
The OTP however requires the key to be the same size of the message, so if
you use some RNG (non-keyed) where the bits are not more probable from an
attackers POV you win.
Tom
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: OTP breaking strategy
Date: Mon, 23 Apr 2001 19:45:04 -0700
"Steve Portly" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> I bet some of the newer super
> computers working off of an advanced chaos theory could beat the house in
> Vegas.
Since when are super computers needed for that?
You simply have to know your game, know the odds, and count. Of course if
you don't want to count get a book on Blackjack from your local library
it'll tell you what you should hit/stay/split/double down on, and you'll
walk away with more money. Or you can play craps, but it takes a bit more
effort to beat the house. If you really feel like winning, find an indian
casino, the dealers are generally very bad. Half of them drag the card edges
bowing them, the other half push too hard in the middle again bowing them,
so you can read the cards. Of course I also saw a dislexic roulette wheel
where he very often switched numbers (e.g. 13 to 31). All you have to do is
know your enemy. But please remember that Cryptanalysts have a gentleman's
agreement with the casinos, we don't beat them up too badly, they don't beat
us up too badly.
Joe
------------------------------
From: "Mark G Wolf" <[EMAIL PROTECTED]>
Subject: Re: Wolf's Secure Channel Theorem
Date: Mon, 23 Apr 2001 22:05:27 -0500
> Of course treating light as a particle will give you different results,
and
> certainly they won't act at infinity like the wave method.
Um, when we "make" light (EM waves) we do it with particles.
Crazy ain't it!
------------------------------
** 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
******************************
