Cryptography-Digest Digest #213, Volume #13 Thu, 23 Nov 00 14:13:01 EST
Contents:
Re: New Dynamic Algo + Contest + Doc (Sylvain Martinez)
Man arrested in stolen Enigma case (Francois Grieu)
Set projection.. (Jorgen Hedlund)
Re: vote buying... ("Frog2000")
Re: Man arrested in stolen Enigma case (Richard Heathfield)
Re: PLEASE DON'T HELP Re: How to find celebrity (Richard Heathfield)
Random function ("Piotr P. Karwasz")
Generating certificate private key ("Dima Mukalov")
Re: PLEASE DON'T HELP Re: How to find celebrity (David A Molnar)
Re: Random function (Jorgen Hedlund)
Re: weten we die PIN? (Mok-Kong Shen)
Re: weten we die PIN? (DS-Net)
Re: Random function ("Frog2000")
NERDS attack (no pun intended) ("Jakob Jonsson")
Re: RSA Signature ! (Mehdi-Laurent Akkar)
Re: PLEASE DON'T HELP Re: How to find celebrity (Paul Crowley)
Re: DES question: Has this ever been proven before? (Francois Grieu)
----------------------------------------------------------------------------
From: Sylvain Martinez <[EMAIL PROTECTED]>
Subject: Re: New Dynamic Algo + Contest + Doc
Date: Thu, 23 Nov 2000 11:58:18 GMT
In article <8vhhja$8lh$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (David Wagner) wrote:
> Sylvain Martinez wrote:
> >You are right, what I tried to say is that I think (hope !) BUGS
could
> >be just a bit more difficult to understand than Vignere or Caesar is.
> >And could therefore be still interesting to look at for a newbie.
>
> I hope you recognize that "look at" is very different from suggesting
> that others can use it and expect it to be reasonably secure.
>
> If the point is just to have fun, sure, post your algorithm; but if
> you recommend that others use it, you might be doing them a major
> disservice.
>
> If the point is to use it operationally, don't invent a new cipher;
> use a trusted cipher, like 3DES or Rijndael.
The point was not to use it operationally. I've just been carried
away...
As I said in my previous post at one point I faced the problem where I
had to know how to have this algorithm tested.
When I first posted an announce about this algorithm few years ago on
sci.crypt, when it was just a student project, I've been flamed "big
way" and nothing constructive came out of it ! the thread I've started
just became a place where people where speaking about anything but
crypto.
(It's also true that looking back in time the algorithm was really crap,
I guess in 2 years I may think the same way again ;O)
Therefore I decided to try something else, aka getting a lot of people
using it. Since then I received a lot of interesting comments, probabely
not as precious as comments from "good cryptographers" but better than
nothing.
> That's my advice, anyway.
Thanks,
Sylvain.
--
---
Unix security administrator
BUGS crypto project: http://www.bcrypt.com
http://www.encryptsolutions.com
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Francois Grieu <[EMAIL PROTECTED]>
Subject: Man arrested in stolen Enigma case
Date: Thu, 23 Nov 2000 13:47:13 +0100
A 57 year old man was arrested on the afternoon of the 17th of November
in a Derbyshire village. As yet the missing rotors are yet to be recovered.
source: <http://www.bletchleypark.org.uk/press.htm>
Francois Grieu
------------------------------
From: Jorgen Hedlund <[EMAIL PROTECTED]>
Subject: Set projection..
Date: Thu, 23 Nov 2000 14:55:22 +0100
Reply-To: [EMAIL PROTECTED]
I'm out on thin ice here, so bear with me. =)
As I've understood it, using public/private key
ciphering you start up with the unciphered data
and use the public key with some function to
project into another set. I.e. projection from
set A to set B using the public key, where set
A is unciphered data, and set B is the ciphered
data.
Now to my problem, is there any easy way to find
the reverse function (i.e. from set B to set A
using the private key) once you have the first
function? (I think I've read it once in my course
"Discrete mathematics" and set theory, but I
can't remember).
BR/jorgen
------------------------------
From: "Frog2000" <[EMAIL PROTECTED]>
Subject: Re: vote buying...
Date: Thu, 23 Nov 2000 09:06:17 -0500
> The Electorial College is the method being used. Florida has no "undue
weight"
This time it does, as we are all waiting. Who wins FLA wins the "nation."
> but simply the weight intended for the contest. We're just seeing the
process
> at one extreme of the possible outcomes. To me, the whole "Popular vote"
> thing is a non-sequiter. The process says the states elect the the Pres,
why
> talk about other conglomerations of votes other than state wise? Doesn't
> the EC represent the "Popular vote" of each state?
No, do your homework. :) That is the point. Look at history, 1876, 1888,
1960, 1968...There is no mandate that the EC must follow the popular vote in
each state.
>
> Look at it this way, If Bob looses by ten votes in Ohio and wins by 15 in
> Idaho and is therefore delared the winner of both contests,
> Idaho votes are being counted in Ohio. Beyond a doubt.
Again, if you do the math, you will see that EC is not exactly equal to the
population. By it's definition, the smaller states are given more weight so
the big ones don't "swollow them." Small and big" refer to population, or
more accurately, # of congressmen, 2 senators...Wasington DC gets 3 EC
votes.
>
> There is no fairness issue here, IMHO:
Well, we disagree. Who did you vote for? :)
>
> Florida has no more weight than normal this time. It is a an artifact of
> perception. It is the one state that has enough votes to swing on it's
own,
> where the outcome was close enough to be diddled with effectively.
But don't you contradict yourself. Florida has 25 EC votes, so who cares how
close it is. Look at the curren EC #s for Bush and Gore. try
http://www.cnn.com/election/2000 and tell me how close it looks. Look at the
EC #s. Must get to 270. Who ever gets FL wins.
> To me, it's like trying to say that the last runner in a relay race "Won"
> as opposed to the rest of that team since he is the one who
> crosses the finish line.
Bad analogy, unless Gore wins. It's all going to be decided, at latest in
Mid-December by the EC. So you're right. Florida means nothing in the end.
>
> Paul
>
> >
> > >
> > > Shawn.
> > >
> >
> >
>
>
>
>
> -----= 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! =-----
------------------------------
Date: Thu, 23 Nov 2000 14:25:13 +0000
From: Richard Heathfield <[EMAIL PROTECTED]>
Subject: Re: Man arrested in stolen Enigma case
Francois Grieu wrote:
>
> A 57 year old man was arrested on the afternoon of the 17th of November
> in a Derbyshire village. As yet the missing rotors are yet to be recovered.
>
> source: <http://www.bletchleypark.org.uk/press.htm>
>
> Francois Grieu
Old news. Did you not see the article I posted on Saturday afternoon,
under the heading "Enigma Development"?
--
Richard Heathfield
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R answers, C books, etc: http://users.powernet.co.uk/eton
------------------------------
Date: Thu, 23 Nov 2000 14:33:07 +0000
From: Richard Heathfield <[EMAIL PROTECTED]>
Subject: Re: PLEASE DON'T HELP Re: How to find celebrity
Paul Crowley wrote:
>
<snip>
> I wouldn't mind so much if the slightest effort had gone into attacking
> the problems before asking for help, but it's clear that the homework
> question has been read off the assignment and typed into the browser
> without ever passing through the brain.
I find this very hard to believe. Surely it's more credible to postulate
that the assignment has been copied and pasted rather than read and
typed. Typing requires at least partial mastery of a keyboard; copy and
paste needs only mouse control.
--
Richard Heathfield
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R answers, C books, etc: http://users.powernet.co.uk/eton
------------------------------
From: "Piotr P. Karwasz" <[EMAIL PROTECTED]>
Subject: Random function
Date: Thu, 23 Nov 2000 15:56:15 +0100
I found a function that is sufficently random.
If you take y=tan(x) and apply this function many times the result seems
unpredictable. Is it true?
Thanx for answering
------------------------------
From: "Dima Mukalov" <[EMAIL PROTECTED]>
Subject: Generating certificate private key
Date: Thu, 23 Nov 2000 17:29:24 +0200
Hi All !
I have a new X509_ASN_ENCODING certificate in a file store.
How can I generate a private key for this certificate
using CryptoAPI functions if I have CERT_PUBLIC_KEY_INFO data?
When I used CryptGenKey the new public key did
not corespond to certificate public key.
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: PLEASE DON'T HELP Re: How to find celebrity
Date: 23 Nov 2000 15:25:03 GMT
Paul Crowley <[EMAIL PROTECTED]> wrote:
> I wouldn't mind so much if the slightest effort had gone into attacking
> the problems before asking for help, but it's clear that the homework
> question has been read off the assignment and typed into the browser
> without ever passing through the brain.
I was about to make some silly comment to the effect that at least posting
problems has a "traitor tracing" property, when I realized it doesn't.
Here the "tracer" is a member of the course staff, and the "traitor" is
the student sharing his problem with everyone else. From a posted problem,
it's possible to figure out which course it came from if you know the
problem sets assigned in that course...but it doesn't follow that you know
which student posted the problem.
In addition, even if you could tell by inspection which student had
posted the problem, you still need to monitor sci.crypt, comp.theory, and
who knows where else to see the problem (though Deja helps with this). The
readers of these groups might or might not be willing to report to the
tracer, but as it stands they likely have no idea where the problem comes
from.
Is there a way to build problem set problems such that they have some kind
of "tracing" properties? It seems that there will always be an attack
from semantics - if a student understands the problem, he or she can write
out and post an equivalent problem. Maybe we don't care about that,
though, on the grounds that at least it's better than cut and paste?
-David
------------------------------
From: Jorgen Hedlund <[EMAIL PROTECTED]>
Subject: Re: Random function
Date: Thu, 23 Nov 2000 16:54:58 +0100
Reply-To: [EMAIL PROTECTED]
"Piotr P. Karwasz" wrote:
>
> I found a function that is sufficently random.
> If you take y=tan(x) and apply this function many times the result seems
> unpredictable. Is it true?
> Thanx for answering
Have you tried to run it let's say 10 times and recorded the result,
and tried this procedure more than once? If the recorded result is
different every time, it might be some kind of "randomness", but I
hardly believe that a mathematical function like that could be
random..
BR/j
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Crossposted-To:
alt.cracks.nl,alt.nl.telebankieren,nl.comp.crypt,nl.financieel.bankieren,nl.juridisch
Subject: Re: weten we die PIN?
Date: Thu, 23 Nov 2000 11:49:32 +0100
Paul Wessels wrote:
>
> We weten, dacht ik wel dat de PIN code van je bankpas van uit de
Please note that the language of sci.crypt is English.
M. K. Shen
------------------------------
From: DS-Net <[EMAIL PROTECTED]>
Crossposted-To:
alt.cracks.nl,alt.nl.telebankieren,nl.comp.crypt,nl.financieel.bankieren,nl.juridisch
Subject: Re: weten we die PIN?
Date: Thu, 23 Nov 2000 17:04:51 +0100
On Thu, 23 Nov 2000 11:49:32 +0100, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>
>
>Paul Wessels wrote:
>>
>> We weten, dacht ik wel dat de PIN code van je bankpas van uit de
>
>Please note that the language of sci.crypt is English.
>
>M. K. Shen
ja maar van de rest nederlands.
Kijk maar goed allemaal .nl
Kan hij toch niet lezen maar moet hij het maar laten vertalen ofzo.
--
http://stripe.cjb.net
------------------------------
From: "Frog2000" <[EMAIL PROTECTED]>
Subject: Re: Random function
Date: Thu, 23 Nov 2000 11:28:10 -0500
No, that isn't sufficient.
--
http://welcome.to/speechsystemsfortheblind
"Piotr P. Karwasz" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> I found a function that is sufficently random.
> If you take y=tan(x) and apply this function many times the result seems
> unpredictable. Is it true?
> Thanx for answering
>
>
>
------------------------------
From: "Jakob Jonsson" <[EMAIL PROTECTED]>
Subject: NERDS attack (no pun intended)
Date: Thu, 23 Nov 2000 17:44:05 +0100
Hi all,
I have made an observation on the public-key cryptosystem NERDS; the
specification is found here:
http://www.core-sdi.com/papers/nerds.pdf
(see also sci.crypt.research). It is a known-plaintext attack, which reduces
the problem of finding the decryption of a ciphertext to a linear
programming problem over the integers. Please have my apologies if my
observation is incorrect or downright nonsense.
Let notation be as in the paper. Suppose that an adversary knows
plaintext-ciphertext pairs (m_1, c_1), ..., (m_k, c_k). c_i being an
encryption of m_i means that
S(m_i) + T(r_i) = c_i
for certain public Z-linear operators S, T and a random element r_i.
Let c be another ciphertext. If there are integers a_1, ..., a_k such that
c = a_1 c_1 + ... + a_k c_k
and such that
m := a_1 m_1 + ... + a_k m_k
is a valid plaintext, then the decryption of c will be m. Namely, we have
that
\sum a_i c_i = \sum a_i (S(m_i) + T(r_i))
= \sum (S(a_i m_i) + T(a_i r_i) )
= S(\sum a_i m_i) + T(\sum a_i r_i)
= S(m) + T(r),
where r = \sum a_i r_i. Hence, c is an encryption of m.
So the problem we have to solve is the following system of linear equations
and inequalities:
c = x_1 c_1 + ... + x_k c_k
0 <= x_1 m_1 + ... + x_k m_k < d_1
The second equation means that each coefficient of the middle expression is
in the interval [0, d_1-1]. Of course, we are looking for integer solutions.
If this system can be solved efficiently, then the scheme is broken. I
believe k does not have to be much larger than twice the degree of the
underlying polynomial p in order to make this system solvable.
Please let me know what you think.
Happy thanksgiving,
Jakob Jonsson
------------------------------
From: Mehdi-Laurent Akkar <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: RSA Signature !
Date: Thu, 23 Nov 2000 17:09:22 GMT
>
> signed them ? is it an encryption ?
Signing <=> Decryption / Verifying <=> Encryption
Or anybody would be able to sign with the publick key !!
MLA
------------------------------
From: Paul Crowley <[EMAIL PROTECTED]>
Subject: Re: PLEASE DON'T HELP Re: How to find celebrity
Date: Thu, 23 Nov 2000 17:07:52 GMT
David A Molnar wrote:
> Is there a way to build problem set problems such that they have some kind
> of "tracing" properties? It seems that there will always be an attack
> from semantics - if a student understands the problem, he or she can write
> out and post an equivalent problem. Maybe we don't care about that,
> though, on the grounds that at least it's better than cut and paste?
We don't care about that, on the pragmatic grounds that the students
bright enough to do that won't be the ones cheating with their homework.
I remember explaining to a University teacher how I would defeat his
scheme to catch people who copy programming assignments, and got the
response that if I was bright enough to do that, I'd probably find it
easier just to do the assignment! These schemes catch lots of people in
practice; if I recall correctly over 100 students were expelled from
Edinburgh University as a result.
--
__
\/ o\ [EMAIL PROTECTED]
/\__/ http://www.cluefactory.org.uk/paul/
------------------------------
From: Francois Grieu <[EMAIL PROTECTED]>
Subject: Re: DES question: Has this ever been proven before?
Date: Thu, 23 Nov 2000 19:10:05 +0100
Raphael Phan <[EMAIL PROTECTED]> asked a question that can be
restated as: find key K and distinct plaintext X Y such that
X ^ Y = DES_K(X) ^ DES_K(Y)
As stated, this is trivial ! For example
K = 1F1F1F1F0E0E0E0E
X = 3333333333333333
Y = 72010BEFAC1ED6E4
[ROT-13 Spoiler in next 3 lines]
Vg jbexf orpnhfr vs L = QRF_X(K) gura K = QRF_X(L)
sbe nal inyhr bs K, jura X vf n jrnx xrl va QRF.
Ohg guvf pna'g or trarenyvmrq sbe neovgenel X.
[EMAIL PROTECTED] (David Wagner) wrote:
> you could find one (solution) with 2^29 encryptions using
> birthday paradox techniques.
> Fix an arbitrary K; re-write the equation as
> X XOR DES_K(X) = Y XOR DES_K(Y);
> generate 2^28 random values of X, and sort them by X XOR DES_K(X);
> generate 2^28 random values of Y, sorted by Y XOR DES_K(Y);
> finally, merge the two sorted lists and look for duplicates.
The idea of using the birthday "paradox" technique is right,
but the 2^29 figure is wrong and the method not optimum.
There are 2^64 possible values for X XOR DES_K(X); assuming
it behaves as a random function, about 2^32 trials are
necessary to find a match with probability 1/2.
It is not necessary to use two sorted lists, simply use one
and find duplicates while or after sorting. Or better, use a
simple probabilistic hashing technique:
a) choose key K, set X to 0
b) zero an array A[] of 2^36 entries of 36 bits each
c) increment X; if X reaches 2^36, the algorithm has failed
d) compute D = X XOR DES_K(X), set Y = A[D mod 2^36]
e) if Y==0, set A[D mod 2^36] = X mod 2^36 and proceed to step c
f) if D != Y XOR DES_K(Y) proceed to step c
g) the algorithm found solution X, Y for key K.
Because step f is reached rarely (with probability a little
less than 2^-4 when X has reached 2^32), the proportion of X
that are not entered in the table is small, and there is only
slightly more than one DES per X tested. The algorithm behaves
nearly as well as comparing D with all values of D previously
computed. It has a fair probability (not quite 1/2) to succeed
with X<2^32, and good probability to succeed with X<2^36.
A simple modification of the algorithm lets it continue should
no solution be found, at the cost of some extra DES computations.
It can be modified to work (though less efficiently) with say
2^32 entries of 2^32 bits. I think it can be modified so that
only a fraction of this 16GByte memory is RAM (my idea is to keep
in RAM a list of D,X pairs in a smaller table kept sorted using
a similar hash-coding tehcnique, then when it fills up to some
thresold sequentialy scan array A[] on disk, in sync with this
RAM table to perform the compare and updates). And the algorithm
can be modified to efficiently use a bitsliced DES implementation.
So all in all this seems a feasible task for a single high-end PC.
Who will give us a solution for K = 0123456789ABCDEF ?
Francois Grieu
------------------------------
** 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
******************************
