Cryptography-Digest Digest #59, Volume #13 Tue, 31 Oct 00 17:13:00 EST
Contents:
Re: RSA Multiprime (Bob Silverman)
Re: BENNY AND THE MTB? (SCOTT19U.ZIP_GUY)
Re: ciphertext smaller than blocksize ([EMAIL PROTECTED])
Re: how i decode this? ([EMAIL PROTECTED])
Re: How do I detect invalid passwords? ([EMAIL PROTECTED])
Give it up? (Tom St Denis)
Re: Is RSA provably secure under some conditions? (Shai Halevi)
Re: Graphics and Encription (wtshaw)
Re: BENNY AND THE MTB? ([EMAIL PROTECTED])
Re: Is RSA provably secure under some conditions? (Roger Schlafly)
Re: Searching for a good PRNG (David Schwartz)
Re: XOR based key exchange protocol - flawed? (David Schwartz)
----------------------------------------------------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: RSA Multiprime
Date: Tue, 31 Oct 2000 20:00:51 GMT
In article <[EMAIL PROTECTED]>,
Francois Grieu <[EMAIL PROTECTED]> wrote:
> > Finding a 192-bit prime with ECM will be a little easier than
> > factoring a 576-bit number with GNFS.
>
> Maybe, but this must be close. According to
> <http://www.loria.fr/~zimmerma/records/ecmnet.html>
> the largest prime factor found with ECM for a moreless
> general number is 177 bits, for an effort that probably was
> below last years sucess for 512 bit using GNFS. This tells the
> thresold (between ECM and GNFS for product of 3 random primes of n
> bits) is over n = 177 bits, but how do we get to 192 bits ?
Getting from 177 to 192 bits is about a factor of 3 in effort.
A naiive use of the complexity functions for ECM vs. GNFS, assuming
that o(1) = 0 yields an effort of about 6 x 10^12 * M(512) to find a
192 bit prime via ECM
vs an effort of 2 x 10^19 to factor a general 512 bit number with GNFS.
M(N) is the number of operations (adds, mults, divs, etc.) to add
two points on an elliptic curve modulo an N bit number. This is
"about" 10^5 for N = 512; note that multiplications take more than 1
cycle whereas almost all of the GNFS operations take only 1 cycle.
--
Bob Silverman
"You can lead a horse's ass to knowledge, but you can't make him think"
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Crossposted-To: talk.politics.crypto
Subject: Re: BENNY AND THE MTB?
Date: 31 Oct 2000 20:02:45 GMT
[EMAIL PROTECTED] (SCOTT19U.ZIP_GUY) wrote in
<[EMAIL PROTECTED]>:
> What follows is a story that may or may not be true
>Supose there is a group that is sending messages and they
>have a code book of 256 symbols most of which are words.
> The MTB ( a fictitous group) has been monitoring them
>and wants to know what the leader Benny lewis ( also fictistous)
>is sending to them. The group started by sending messages by
>hand but the MTB got a copy of the code book. After a period
>of time Benny and his boys decide to get modern so they stated
>using QHQ in the non public key mode. The mode where the public
>is using compression and encryption. But the boys back at the MTB
>laugh since even when they have been out drinking they brag they
>can decrypt any QHQ program with there methods. The boys know
>that there billion dollar quantam computer can find the solution
>of almost all meassages since usually there is only one possible
>solution to the decryption compression process and there tool
>swiftly locks in on it. But Benny is no fool so he still keeps
>the code book for first layer and then decides to use Matt's
>bicom program to do the compression and encryption. The resultant
>file is then zipped and sent to the internet.
> THe boys still laugh since they have heard that Riandoll is the
>encryption method that Matt used. And they already have a patch
>to handle the expected inclusion of the cipher to QHQ. So they
>spend a week to modify it to use Matt's bijective compression.
>
> They are still laughing when they get the first message to
>decyrpt. Since it is only a byte long. Some of the boys don't
>even want to try to turn the quantum computer on. One byte they
>say. How many possible messages could that decrypt to. But for
>grins they test it out. It spits out a 20 byte answer that they
>run though the code book. The message does not quite make sense so
>they do it again. They get a 16 byte message this time.
> They think something is wrong with the machine. Then a tech
>with a high school degree reminds them that it spits out at
>random a possilbe valid anwser. So maybe there is more than
>one possible answer. Something that has not happend with all
>the QHQ messages they worked with before. So they decide to
>really take a long time they run the thing all nite. Spitting out
>thousands of possilbe messages that could have been encrypted
>into that one byte. By this time they are worried they realize
>there billion dollar quantum computer is worthless and that there
>are at least 2**100 different possible messages that could have
>been sent. They are at a loss. THey do the only thing they can
>they try to convince the public that bijective compression
>with bijective encryption is bad. They make sure QHQ never makes
>use of this scheme. But Benny does not stop using it. He later
>add other bijective compression encryption schemes in series. He's
>no fool he stays one step ahead.
> What follows is the one byte file that came from the zip file:
>
>xdump r.bia
>0000 78 . . . . . . . . . . . . . . . *x*
> number of bytes is 1
>
> What follows is Bennies message in the secret code format
>note it is 17 bytes ( code words) long.
I meant 19 sorry
>bicom -d -p no_shit_password r.bia r.raw
>0000 29 B5 1D 02 B5 1D 52 68 79 76 85 29 B5 68 30 6D *).....Rhyv.).h0m*
>0010 D5 79 AF . . . . . . . . . . . . . *.y.*
> number of bytes is 19
>
For some reason when I look in Deja the spacing is all messed
up for file dumps. I can't seem to get cut and paste to work
the same ech time. But it looks ok in my news reader.
>Also note that any password you try to decrypt compress with get
>a totally different file. I bet you can't even find two passwords
>that decrypt decompress to the same file.
>
> THe boys at MTB are scared they thought by allowing Riamdoll
>any implementation in a QHQ type of format would be easy to break
>by there quatum computer.
>
>**the above story false but the fact concerning matts bicom and
>and the file and password using facts are not. They are true.
>
>Cherrios
>
>
> Try this with any other compression encryption program you can't
>
>
>David A. Scott
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
Scott famous encryption website **now all allowed**
http://members.xoom.com/ecil/index.htm
Scott LATEST UPDATED source for scott*u.zip
http://radiusnet.net/crypto/ then look for
sub directory scott after pressing CRYPTO
Scott famous Compression Page
http://members.xoom.com/ecil/compress.htm
**NOTE EMAIL address is for SPAMERS***
I leave you with this final thought from President Bill Clinton:
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: ciphertext smaller than blocksize
Date: Tue, 31 Oct 2000 20:08:53 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (SCOTT19U.ZIP_GUY) wrote:
> [EMAIL PROTECTED] wrote in <8tl1c9$fkv$[EMAIL PROTECTED]>:
>
> >[snip my statement that the entropy of the key is diffused into the
> >plaintext in the creation of the ciphertext]
>
> Actually the word entropy not in your previous message so your
> lying plain and simple.
It didn't need to be, entropy is a measure of the actual information in
data. Since my statement was to the effect that the data from the key
is diffused into the data encrypted, entropy was an unnecessary word.
>
> Entropy is more a funtion of the possible message density.
> If its one per bit then you have maximum entropy in the shanon
> sense. I am not sure where your trying to take this.
> But if I have a one bit key. where I multipy by 1 or -1. I still
> would not say I physically added information to the file.
If no information was added then the result MUST be the same regardless
of key, so by your own argument, in that altered data there is now the
information that one and only one of the (key, data) pair was negative.
I would certainly call that added data, even though it is a very small
amount of data.
Joe
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: how i decode this?
Date: Tue, 31 Oct 2000 20:14:57 GMT
> If I was an ametuer
I think we have vastly different definitions of professional, my
definition includes actually having some knowledge of the subject. You
obviously have at most minimal knowledge (and probably less), therefore
you are an amateur.
> I would use more than one method
> in series for protection.
If my choice was anything beginning with Scott and ending in .zip I'd
use another method too.
> I would use only methods that
> are fully bijective so that indvivdual stages don't add
> information a layer at a time making it far easier to
> break.
And here's where you begin to show your lack of knowledge even more, it
is trivially provable that any encryption method that can be decrypted
(given the key of course) must be, by your definition as I understand
it, bijective. I've taken the liberty of deleting the rest of your
knowledgeless statements.
Joe
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: How do I detect invalid passwords?
Date: Tue, 31 Oct 2000 20:34:21 GMT
"David Hopwood" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
[snip entire message]
After reading your message, I think we are having distinct
communication problems. We were both trying for the same basic target.
Namely the following:
(Use strong authentication to establish shared secret K)
(s->c : salt)
c->s : {hash of password}K
Whether there is a salt involved in the hash or not, is a trivial
matter, and not necessary for the strength of the hash transfer. I
apologize for my part in the misunderstanding.
Joe
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Give it up?
Date: Tue, 31 Oct 2000 20:35:39 GMT
Here is all you need to know about communication topology.
Secrecy -> Cipher
Efficiency -> Codec
Codec != Cipher.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Shai Halevi <[EMAIL PROTECTED]>
Subject: Re: Is RSA provably secure under some conditions?
Date: Tue, 31 Oct 2000 16:15:12 -0500
John Feth wrote:
>
> I'm sure that Canetti, Goldreich, and Halevi (Random Oracle Methodology,
> Revisited authors) are serious in their efforts and I'm glad to have the
> paper to review. But I must admit, the proofs they offer for their
> theorems, and even the definitions they give for use in their theorems are
> opaque. I think the opacity is due to the notation they use and the lack
> of an appendix that makes clear how the notation works.
>
> It seems to me that including in the paper an actual example of a
> cryptographic system that passed the random oracle test but failed to be
> secure in implementation would go a long way to providing insight into the
> perils of implementation. Otherwise, I'm left feeling that I'm reading an
> abstraction about an abstraction.
>
> Sure, my ignorance is profound, but a little clarity of notation will help
> lift the veil. Is their some Notation Oracle hiding out there?
>
> John Feth
>
Well, that paper assumes a fair amount of background in cryptography and
complexity theory. In a way, it does include an "actual example" of a
cryptographic system that passed the random oracle test but failed to be
secure in implementation, but this description is on quite a high level.
This is unavoidable, as some of the tools we use are quite horrendous to
describe in any level of details.
Ignoring all these tools, what we show is a signature scheme with the
following properties:
* It is secure when you use a truly random function as your hash
function.
* If you implement it using any fully-specified hash function, then
essentially submitting the code of that hash function as a document for
signature, will cause the signer to output its secret key.
Admittedly, this is a contrived example. But it demonstrates that a
proof of security in the random oracle model is not an ironclad
argument.
-- Shai
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Graphics and Encription
Date: Tue, 31 Oct 2000 14:36:42 -0600
In article <[EMAIL PROTECTED]>, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>... It is in my view at least as normal for a
> person to send to a partner numerical data as pictures.
> That is, for serving as cover materials before the
> scrutinating eyes of a controller, numerical data are just
> as good. So I don't quite understand that doing stego
> with numerical data seems to have been neglected.
>
> M. K. Shen
Figure that the old method of tampering with characters to defeat possible
encriptive uses could mess up technical exchanges of raw data. Surely
most of the area of stego depends on what the computer revolution has
brought us and the need for it will be swelled by contining efforts to get
into someone elses business.
--
52) *Part of job is making whimsical, zippy, and vexing key sequences.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: BENNY AND THE MTB?
Date: Tue, 31 Oct 2000 21:17:07 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (SCOTT19U.ZIP_GUY) wrote:
Let's start with the obvious stupidities.
1) A Rijndael block of "1 byte"
Truth : Rijndael is a 128-bit block cipher, there is not way to make it
generate a single byte output that is decryptable
2) This is possible
Truth : This comes from ds, so far he has established that he knows
very little, and what he does know is usually wrong
That ought to be enough for now, but please also note that he posted it
twice, the second time adding a few bytes to make it a reply. D/s were
you by any chance attention-deprived as a child?
Joe
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Roger Schlafly <[EMAIL PROTECTED]>
Subject: Re: Is RSA provably secure under some conditions?
Date: Tue, 31 Oct 2000 13:41:57 -0800
Shai Halevi wrote:
> Ignoring all these tools, what we show is a signature scheme with the
> following properties:
> * It is secure when you use a truly random function as your hash
> function.
> * If you implement it using any fully-specified hash function, then
> essentially submitting the code of that hash function as a document for
> signature, will cause the signer to output its secret key.
>
> Admittedly, this is a contrived example. But it demonstrates that a
> proof of security in the random oracle model is not an ironclad
> argument.
Which is why these folks shouldn't be claiming that they have proofs.
They just sound like the snake-oil peddlers.
------------------------------
From: David Schwartz <[EMAIL PROTECTED]>
Subject: Re: Searching for a good PRNG
Date: Tue, 31 Oct 2000 13:58:15 -0800
Tim Tyler wrote:
> You're correct that the method is likely to produce inferior output to
> (say) a VN compensator, though - and it certainly raises the question
> of whether the author knew what they were talking about.
As long as you understand the method of generation, the method of
transmission, and its potential weaknesses, you can use it. You may have
to compensate for them, depending upon your application. Just remember
that this is useless to seed a cryptographic RNG because the random data
is sent in the clear.
DS
------------------------------
From: David Schwartz <[EMAIL PROTECTED]>
Subject: Re: XOR based key exchange protocol - flawed?
Date: Tue, 31 Oct 2000 13:55:14 -0800
Mike Connell wrote:
> > Now the MITM can intercept all the communications between A and B. A
> > knows it's talking to mb, which it thinks is B.
>
> That is the sticking point.
>
> I understand what you're sying, and thank you for saying it. However,
> I still don't see it as an attack. The question is, why does A think
> that mb is the public key of B?
Because that is the only key he has ever seen B present and he doesn't
know the MITM exists.
> In the case that A,B have exchanged keys beforehand, the attack fails,
> as A recognises Pmb!=Pb. The other scenario, is where A knows nothing
> about B, except the public key which they've previously used to
> communicate with that 'person'.
Correct. I'm talking about the other scenario.
> In that case, A is talking to "the person with public key mb" - that is
> all that they know. They get stock tips from mb, and they always get
> stock tips from mb. the MITM may be relaying those from user B (Pb), but A
> never even knows that: it only sees stocktips coming from mb.
Correct, so A thinks that mb is B. This allows the MITM to send any
message he or she wants to A and A will think it came from B, since A
only knows B as mb. This allows the MITM to impersonate any user A has
ever spoken to.
> All this reduces to the case of A and B trusting C, when C is not
> somebody they should be trusting.
No, this comes back to A assuming that messages from mb came from "the
person who gave me all those stock tips", when they don't.
> > B knows it's talking to
> > ma, which it thinks is A. The MITM can continue to do this to every
> > single communication between A, B, C, and others. All along, it can
> > decode every communication, can modify any communication, and can
> > impersonate any user to any other user.
> >
> > So you think the person who sent you all those stock tips is 'mb' (when
> > it's really B). So when you see a new stock tip from 'mb', you think
> > it's really B. It might be, or it might not be.
> >
>
> Well, it *is* mb. mb might have gotten them from B, but it was still
> mb that sent them to A.
Yes, mb sent them to A, but so did B.
> Everytime you get a message from mb, you know it came from the same
> person. That person might have gotten the information from anywhere,
> you don't know. All you know is that they're telling it to you.
>
> If A is getting anonymous stock tips from Pmb, it isn't a problem,
> even if the person using Pmb is actually getting them from B. It only
> becomes a problem when the Pmb user says "I am B". At that point A
> must say "I dont know that, I need some way to validate that you are
> in fact B". That validation clearly cannot take place over the current
> channel. B will have to host a party and let A attend. When that
> happens, A will see that the MITM is not B.
>
> To put it another way: I think I'm getting helpful comments from David
> Schwartz. However, I might be getting them from MITM. This isn't a
> problem for me. Maybe you actually don't know anything about
> crpytography, you just have a friend at the NSA [0], and you are
> relaying his information to me. All I see is that I get this
> information from you. I don't know where you get it from...
> [0] You appear to know lots, but I'm not convinced you're the *real*
> David Schwartz. ;-)
*grin* So long as you understand that you never know who you are
speaking to or whether any third parties might be intercepting what you
are saying, then you don't have a problem with MITM attacks. ;)
DS
------------------------------
** 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
******************************
