Cryptography-Digest Digest #323, Volume #10 Tue, 28 Sep 99 10:13:05 EDT
Contents:
Re: Perfect Shuffle Algorithm? (Johnny Bravo)
Re: Perfect Shuffle Algorithm? (Dr D F Holt)
Re: RSA 640 bits keys factored, French banking smart card system craked! (Serge
Paccalin)
Re: Perfect Shuffle Algorithm? ("Oliver Roese")
Re: SNAKE Web Page (Paul Onions)
Re: Electronic envelopes (Johnny Bravo)
Re: msg for Dave Scott (Tom St Denis)
Re: msg for Dave Scott (Tom St Denis)
Re: msg for Dave Scott (Tom St Denis)
Help me! Please give me CAVE algorithm. ("bee16")
Hardest ever ECDL solved by INRIA researcher and 195 volunteers (Robert Harley)
Re: Perfect Shuffle Algorithm? ("Clive Tooth")
Re: Hardest ever ECDL solved by INRIA researcher and 195 volunteers (DJohn37050)
Re: Electronic envelopes (Helger Lipmaa)
Re: Perfect Shuffle Algorithm? ("Clive Tooth")
Re: Perfect Shuffle Algorithm? ("Clive Tooth")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Johnny Bravo)
Crossposted-To: sci.stat.math,sci.math
Subject: Re: Perfect Shuffle Algorithm?
Date: Tue, 28 Sep 1999 05:47:10 GMT
On Tue, 28 Sep 1999 00:50:40 GMT, [EMAIL PROTECTED] wrote:
>They way I did it, is I created an array of 1002 cards (ints) in
>computer memory, set the card value to it's original array index, then
>created a 2nd array, shuffled the 1st into the 2nd, compared to see if
>the 2nd array was in the original order, if not, copied the 2nd array
>back into the deck, and repeated until the came up in th4e right order.
>
>Does anybody have any ideas, how to do this simpler, faster?
I'm a hack programmer (I coded CipherSabre from scratch in about 3 hours) and
I managed to get a speed of 2.2 million shuffles per minute on a plain P200.
That's 2.5x faster than you got, and I'm sure it could be optimized much further
both in code and algorithm. Since you didn't bother to tell us codewise how you
did anything I can't tell you what you can improve upon.
>I do know in a perfect shuffle, the top card gets lowered into the deck
>2 positions every shuffle. Also, every shuffle I am only shuffling 204
>cards (102 off the top + 102 off the bottom) and putting the remaining
>797 cards on the top of the deck.
>
>I could use this job.
And if you need this kind of knowledge are you going to come here and ask us
for help all the time if you do get the job? Oh yeah, what does this have to
do with crypto. <plonk - killfiled>
Post follow ups to dev/null.
Johnny Bravo
------------------------------
From: [EMAIL PROTECTED] (Dr D F Holt)
Crossposted-To: sci.stat.math,sci.math
Subject: Re: Perfect Shuffle Algorithm?
Date: 28 Sep 1999 10:25:09 GMT
In article <7sp3cs$6k0$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] writes:
>I was given a problem for a job interview for a computer programming
>job. I was to write a routine that cuts a computer simulated deck and
>performs a perfect shuffle. A perfect shuffle, you cut the deck x cards
>from the top. Then the bottom card from the top stack deck goes down
>first, then the bottom card from the bottom of the deck on top of it,
>one at a time, until one of the stacks runs out, then the remaining
>cards go on top of the deck.
etc.
Well, this does seem a difficult problem to be confronted with in a job
interview. If you have seen something like it before then it is easy, but
otherwise it is definitely not! All but one of the suggestions you have had
so far have not been very inspired either. But maybe you were expected to
try and get help with it, which is what you are doing!
The easiest approach, which would certainly solve the problem fast, is
to program the case of finding the order of an arbitrary permutation of the
set {1,2,3,...,n} (in your case n=1001). Just write the permutation in
cycles, and then the order is the least common multiple of the cycle
lengths. For example, if n=10, and we had the permutation
1 2 3 4 5 6 7 8 9 10
get mapped to: 9 7 5 4 3 2 8 1 10 6
This permutation decomposes into cycles
(1,9,10,6,2,7,8)(3,5)(4)
which means 1 maps to 9, 9 maps tp 10, ..., 8 maps to 1, etc.
Cycle lengths are 7, 2, 1, so order = 14.
This means that you would have to repeat this permutation 14 times to
get beack to the initial position.
Derek Holt.
------------------------------
From: [EMAIL PROTECTED] (Serge Paccalin)
Crossposted-To: alt.security.pgp
Subject: Re: RSA 640 bits keys factored, French banking smart card system craked!
Date: Tue, 28 Sep 1999 12:36:11 +0200
On/Le 23 Sep 1999 02:39:45 GMT, [EMAIL PROTECTED] wrote/a �crit...
> Laurent PELE <[EMAIL PROTECTED]> wrote:
> >> could factor by mathematical means. I wonder if the factors were
> >> embedded in the smart card, and Humpich got them out with a hardware
> >> or protocol attack.
> >
> >No because, Humpich can make different false smartcards and change them as
> >he like.
>
> Well, if the smartcards had the secret key inside and he got it out,
> then he could re-use it in other cards.
>
> >He didn't find any leak in the protocol, he didn't have any other choice to
> >factor the key, it is said in the 2 pages interview in PirateMag September
> >magazine in French.
>
> Is that interview online? I can read enough French to get the sense
> of what he said.
The interview (in French) is now online at the following URL:
http://www.acbm.com/pirates/num_05/interview.html
Several digitized articles (mainstream press) can be viewed at
http://altern.org/humpich/
--
___________
_/ _ \_`_`_`_) Serge PACCALIN
\ \_L_) [EMAIL PROTECTED]
-'(__) L'hypoth�se la plus �labor�e ne saurait remplacer
_/___(_) la r�alit� la plus bancale. -- San Antonio
------------------------------
From: "Oliver Roese" <[EMAIL PROTECTED]>
Crossposted-To: sci.stat.math,sci.math
Subject: Re: Perfect Shuffle Algorithm?
Date: Tue, 28 Sep 1999 12:49:19 +0200
<[EMAIL PROTECTED]> schrieb in im Newsbeitrag:
7sp3cs$6k0$[EMAIL PROTECTED]
(...)
(Given a permutation pi, your problem is to find the least integer n
with pi^n=id.)
You can solve this easily, if you have the cycle-representation of your
permutation.
Example:
pi = (1,4,2,3,6,5) = ((1)(2,4,3)(5,6))
That means: 1->1, 2->4->3->2, 5->6->5
pi is composed of three independent working special permutations
(rotations.)
The first rotation does nothing.
The second comes back if n is divisible by 3.
The third comes back if n is divisible by 2.
All three come back if n is divisible by {1,2,3}. The least positive
number with this property is defined to be lcm(1,2,3) (The least common
multiplier.)
>
> I could use this job.
>
Good Luck
Best Regards
Oliver
------------------------------
From: Paul Onions <[EMAIL PROTECTED]>
Subject: Re: SNAKE Web Page
Date: Tue, 28 Sep 1999 04:13:37 -0700
In article <[EMAIL PROTECTED]>, Peter Gunn
<[EMAIL PROTECTED]> wrote:
> Paul Onions wrote:
> > Peter Gunn wrote:
> > >
> > > Im wondering if this can be fixed by simply not
allowing { 0,1,g }
> > > for g^Y1 mod f(1,P,R) ??
> >
> > Looks like it to me. But disallow those values for
both A and B.
> >
> > > Perhaps not allow any values J such that g^J < Z ??
> > > (Z being the minimum f(1,P,R))
> >
> > I'd just go for something simple like:-
> >
> > 1 < w < p, w != g
> I think I'll stick to...
> J < w < p
> since J is easily calculated (or estimated for g==3 or
g==4) and should
> hopefully make it more difficult to find other special
values for w.
> I will have to explicitly state that w !=g though for
people who want to
> use large modulous values (which might be bigger than J).
> I also forgot to put code in RATTLER to check the values
it receives for
> w... I'll patch that up at the weekend :-)
I think maybe you're misunderstanding things a bit here.
Legitimate parties send values w of the form w = g^x mod p
for some x and p,
but adversaries need not do so. The problem you will have
is that, on
receiving a value w, how do you compute x in order to
ensure that x > J ?
The only efficient way I can see to do this is to compute
all j <= J and check
that w != g^j for all j. This either involves successive
computations or
table lookups.
But having said this, you are on the right track because
I've just found another
attack that would defeat my suggestion all the time and
yours potentially some
of the time! (depending on the prime moduli used)
The attack details are below, but the main weakness that is
exploited is the
ability for an adversary to generate x values such that w =
g^x < p. In order
to stop this attack we must make it impossible for an
attacker to generate
such x's for *any* of the prime moduli.
Using your approach this would mean disallowing all such J
such that g^J < Z
where Z is the *maximum* f(1,P,R).
Another approach would be to choose a generator such that g
> sqrt(Z) where
again Z is the *maximum* f(1,P,R). This has the advantage
of only needing
to check w != g, not powers of g.
Attack details
==============
The adversary impersonates B.
In step (2) she returns S, g^n, g^n, g^n, ... where n is a
low exponent so
that g^n has a chance of being less than all of the moduli
used in this pass.
Now the adversary captures E[K](S) and aborts.
Offline, the adversary can mount a search attack on the
weak shared secret P
as follows.
Guessing P gives the moduli used in the exponentiations.
So the adversary
can now compute (g^X1)^Y1 mod f(1,P,R) = (g^X1)^n mod
f(1,P,R), etc.
Since the key is given by (from your modified web-page):-
K=H(U,S,R,P,g^X1 mod f(1,P,R),
g^X2 mod f(2,P,R),
g^X3 mod f(3,P,R), ...,
g^Y1 mod f(1,P,R),
g^Y2 mod f(2,P,R),
g^Y3 mod f(3,P,R), ...,
(g^X1)^Y1 mod f(1,P,R),
(g^X2)^Y2 mod f(2,P,R),
(g^X3)^Y3 mod f(2,P,R),...)
the adversary can compute this based on her guess at P and
then test this
out on E[K](S).
Thus eventually finding P.
Regards,
Paul(o)
* 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: [EMAIL PROTECTED] (Johnny Bravo)
Subject: Re: Electronic envelopes
Date: Tue, 28 Sep 1999 07:13:01 GMT
On Tue, 28 Sep 1999 08:42:38 +0200, Mok-Kong Shen <[EMAIL PROTECTED]>
wrote:
>> >In other words, one deposits an envelope containing
>> >secrets at a notary who opens it at a certain time point and
>> >announces the contents. The envelope is to be opened exactly at
>> >that time point and not before. No trust on the notary is assumed.
>>
>> Then you can't even be sure your envelope will even be opened.
>
>In the case of normal envelopes I suppose that there are ways of
>sealing that are traditionally considered to be adequate against
>frauds and there are specialists who can examine that. I don't know
>what the actual probability of frauds is, but it seems that people
>accept (believe) that degree of security (compare signatures on
>cheques).
I was just responding to your comment about not trusting the notary.
Given this, you can't even trust they will open the envelope or even
bother reading the message. :)
>
>> >The act of opening should hence prove that it is indeed done at the
>> >prescribed time point. With such a mechanism one could deposit
>> >copies at several notaries at different geographical locations and
>> >the secrets will then be disclosed simultaenously at these places
>> >(within the error tolerance of the radio clock signal transmission,
>> >of course).
>>
>> Not at all possible, even if you give them the keys yourself can
>> you assume that they will all open them within the same second.
>> And what radio clock signal transmission are you talking about?
>
>The signals that synchronize, for example, your alarm clock.
The only signal that synchronizes my alarm clock is the current flowing
through my brain. I have to set my own alarm clocks manually, and set them
again
every time the power goes out. :)
>As far as I know, each country has a station sending the time signals
>based on an atom clock which is synchronized with Greenwich.
>
>M. K. Shen
But now you aren't talking about an electronic envelope but a physical one.
This violates the first requirement you listed at the beginning of your request.
Johnny Bravo
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: msg for Dave Scott
Date: Tue, 28 Sep 1999 11:14:05 GMT
In article <7snrlm$bur$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Keith A Monahan) wrote:
> Can someone help me out here? I've seen and read about the fact that most
> encryption algorithms use padding in the last block to make sure their
> last block is the same size as the rest of the blocks.
>
> What happens when the transmitted file size (or transaction, or ...) is
> the same everytime. I mean, what happens when it is a predictable length?
> This gives the attacker some plaintext, which can't possibly be good.
>
> And I think the worst case scenerio is when there is only a small amount
> of original (unknown) plaintext coupled with a large amount of known
> plaintext(the padding) within the same ciphertext block.
Well I can say that yes only encrypting a small portion of the block is a
hazard (dictionary attacks), HOWEVER, in peekboo (which this thread is semi
about) each message has a session key so they are not encrypted with the same
key. This means dictionary attacks will not work (or not work well at all).
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: msg for Dave Scott
Date: Tue, 28 Sep 1999 11:17:16 GMT
In article <[EMAIL PROTECTED]>,
Anton Stiglic <[EMAIL PROTECTED]> wrote:
> Keith A Monahan wrote:
>
> > Can someone help me out here? I've seen and read about the fact that most
> > encryption algorithms use padding in the last block to make sure their
> > last block is the same size as the rest of the blocks.
> >
> > What happens when the transmitted file size (or transaction, or ...) is
> > the same everytime. I mean, what happens when it is a predictable length?
> > This gives the attacker some plaintext, which can't possibly be good.
> >
>
> Actually, knowing the lenght of the message gives you much more info!
> Imagine seeing an ecryption of a 'yes' or 'no' answer, if you saw something
> like '$R' and '%0#', which one would you think is yes?
>
> The thing is that you must not see the padding, it should be encrypted, so as
> to not give any info on the lenght. If all encrypted blocks have the same lenght,
> the only info you get is a size limit to the plaintext.
Actually most 'yes' or 'no' messages are of little value..
Anton here is my message for you 'no'.
What does that mean? The question before it is more important.
BTW if you are paranoid about that you can always use a block cipher (peekboo
has blowfish/cast/rc5/rc6/twofish to pick from) which will mask the size of
the message (in increments of the block size).
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: msg for Dave Scott
Date: Tue, 28 Sep 1999 11:21:17 GMT
In article <7so137$222u$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (SCOTT19U.ZIP_GUY) wrote:
> Thare are modes that don't require. Padding. You can look in
> various FIPS or the FAQ for this forum. But the 3-letter standard modes
> are weak in my humble opiniun. IF you want to use a files that can
> end on any boundary I wouild sugguset "Wrapped-PCBC" see scott16u.zip
> of scott19u.zip These methods acan handle files that end on any number of
> bytes of files on long length.
What I think you were getting to was OFB/CFB right? What makes the other
modes (CBC, PCBC) weak?
> One other quick and dirty way to so add a psuedo random padding to the front
> of file in such a way that file always ends on a nice mulitply for the method
> of your chosse. But if you get into encryption methods that directly adding
> the padding themsleves you have to worry about the encyrption method hiding
> info for the attacker.
Well in my case (in peekboo) if you have a 9 byte message and you are using
blowfish for example... you will get 2 FULL ciphertext blocks. There is no
'padding' pursue it's just 1 byte and 7 nulls...And you cannot build
dictionaries of the 'last byte' because each message uses a different key.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "bee16" <[EMAIL PROTECTED]>
Subject: Help me! Please give me CAVE algorithm.
Date: Tue, 28 Sep 1999 15:36:24 +0900
Hi, I am studying AUTHENTICATION.
I need articles about CAVE algo.
Please, give me articles.
Thanks.
[EMAIL PROTECTED]
------------------------------
From: Robert Harley <[EMAIL PROTECTED]>
Subject: Hardest ever ECDL solved by INRIA researcher and 195 volunteers
Date: 28 Sep 1999 13:56:52 +0200
The INRIA researcher is yours truly... =:-)
Detailed press releases in English and French from INRIA and 4K
Associates are now available at:
http://pauillac.inria.fr/~harley/ecdl/
Get the info from the horse's mouth!
Rob.
------------------------------
From: "Clive Tooth" <[EMAIL PROTECTED]>
Crossposted-To: sci.stat.math,sci.math
Subject: Re: Perfect Shuffle Algorithm?
Date: Tue, 28 Sep 1999 13:05:25 +0100
[EMAIL PROTECTED] wrote in message <7sp3cs$6k0$[EMAIL PROTECTED]>...
>I was given a problem for a job interview for a computer programming
>job...
Hmmm... seems like 97,020 to me. Oh well...
--
Clive Tooth
http://www.pisquaredoversix.force9.co.uk/
End of document
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: Hardest ever ECDL solved by INRIA researcher and 195 volunteers
Date: 28 Sep 1999 12:56:16 GMT
Also check out www.certicom.com.
Don Johnson
------------------------------
From: Helger Lipmaa <[EMAIL PROTECTED]>
Subject: Re: Electronic envelopes
Date: Tue, 28 Sep 1999 15:50:36 +0300
Mok-Kong Shen wrote:
> Anton Stiglic wrote:
> >
> > Assuming Alice deposits the enveloppe to Bob. The scheme
> > you described is possible if Bob can communicate with Alice
> > at the moment Bob is to open the enveloppe. When the content
> > in the enveloppe is a bit, this is called a bit commitement scheme.
>
> I wrote in my post that after deposition the sender is assumed to
> be no longer available.
>
> M. K. Shen
The next publication should give a state-of-the-art (AFAIK) overview
of the subject:
"Conditional Oblivious Transfer and Timed-Release Encryption", Giovanni
Di Crescenzo (University of California San Diego), Rafail Ostrovsky, and
Sivaramakrishnan Rajagopalan (Bellcore) , Eurocrypt 1998
------------------------------
From: "Clive Tooth" <[EMAIL PROTECTED]>
Crossposted-To: sci.stat.math,sci.math
Subject: Re: Perfect Shuffle Algorithm?
Date: Tue, 28 Sep 1999 13:52:09 +0100
Alex wrote...
>I would work in the permutation group S_{1001}. you have this
>permutation
>
>120 -> 1001
>1001 -> 1000
>119 -> 999
>etc.
Or rather...
102 -> 1001
1001 -> 1000
101 -> 999
etc.
--
Clive Tooth
http://www.pisquaredoversix.force9.co.uk/
End of document
------------------------------
From: "Clive Tooth" <[EMAIL PROTECTED]>
Crossposted-To: sci.stat.math,sci.math
Subject: Re: Perfect Shuffle Algorithm?
Date: Tue, 28 Sep 1999 14:14:51 +0100
[EMAIL PROTECTED] wrote in message <7sp3cs$6k0$[EMAIL PROTECTED]>...
>I was given a problem for a job interview for a computer programming
>job. I was to write a routine that cuts a computer simulated deck and
>performs a perfect shuffle. A perfect shuffle, you cut the deck x cards
>from the top. Then the bottom card from the top stack deck goes down
>first, then the bottom card from the bottom of the deck on top of it,
>one at a time, until one of the stacks runs out, then the remaining
>cards go on top of the deck.
[snip]
>I do know in a perfect shuffle, the top card gets lowered into the deck
>2 positions every shuffle.
No. Your definition of a perfect shuffle does not imply this.
--
Clive Tooth
http://www.pisquaredoversix.force9.co.uk/
End of document
------------------------------
** 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
******************************
