Cryptography-Digest Digest #614, Volume #11 Mon, 24 Apr 00 12:13:01 EDT
Contents:
Re: quantum computation FAQ? (Martin Veasey)
Simple XOR breaking - What is the logic? (Eero)
Re: Checksum algorithm which is ASCII (Terry Neckar)
Re: (MERCY) Overcomming the slack used by IV's (Tim Tyler)
Re: Simple XOR breaking - What is the logic? (Bill Unruh)
Re: Checksum algorithm which is ASCII (Tom St Denis)
Re: GSM A5/1 Encryption (David A. Wagner)
Re: (MERCY) Overcomming the slack used by IV's (Tom St Denis)
Re: GOST related key attack (David A. Wagner)
Re: factor large composite (DJohn37050)
Re: factor large composite (Andrew Carol)
Re: factor large composite (Tom St Denis)
Re: factor large composite ("Trevor L. Jackson, III")
----------------------------------------------------------------------------
From: Martin Veasey <[EMAIL PROTECTED]>
Subject: Re: quantum computation FAQ?
Date: Sun, 23 Apr 2000 16:12:49 +0100
"What is quantum computing" ... ?
On 23 Apr 2000 04:13:02 GMT, David A Molnar <[EMAIL PROTECTED]>
wrote:
>I've drafted an outline of a possible FAQ which follows this message.
>Comments appreciated. Everything from "we don't need no steenkin' FAQ"
>to "it's been done before and done better" to "you're not qualified to
>write it" to specific comments on formatting, addition or deletion of
>questions, and so on.
------------------------------
From: Eero <[EMAIL PROTECTED]>
Subject: Simple XOR breaking - What is the logic?
Date: Sun, 23 Apr 2000 19:35:17 +0300
The sci.crypt FAQ says (with the same exact words as in
the Applied Cryptography.. :) that when you know the lenght
of the key, it is very easy to reconstruct plaintext from
cipher. Can somebody tell where my logic has gone wrong.
"Shift the text by that length and XOR it with itself."
So let us try this with a simple example:
Let's say that key is "101", so when you encrypt the
message, the cipher is generated like this:
plaintext: 110101101000100100111011011000000101111
key: 101101101101101101101101101101101101101
cipher: 011000000101001001010110110101101000010
Because I know that the key is 3 chars long, I shift it 3 chars:
Shifted cipher: 000011000000101001001010110110101101000010
When it says that you should "XOR it with itself",
i understand that it doesn't mean that we XOR
the shifted cipher with the shifted cipher, because
the outcome would a bunch of zeroes, right?
cipher: 000011000000101001001010110110101101000010
"Key": 000011000000101001001010110110101101000010
outcome:000000000000000000000000000000000000000000
If I XOR the original ciphertext with the shifted
ciphertext or vice versa, the outcome will be plain rubbish.
cipher: 000011000000101001001010110110101101000010
"Key": 011000000101001001010110110101101000010
outcome:011011000101100000011100000011000101010
So can anyone explain me what does the hell does the
writer mean when he tells you to "shift" the ciphertext
and "XOR it with itself"? Or is just a big hoax to scare
people away from Microsoft and its encryption standards
which are "faster and almost as secure as DES" :)
-Eero
------------------------------
From: Terry Neckar <[EMAIL PROTECTED]>
Subject: Re: Checksum algorithm which is ASCII
Date: Sun, 23 Apr 2000 16:35:24 GMT
I have an actual file at http://www.microcoders.com/keyfile.dat that has the
checksum of "$PLQDC". I'm trying to figure out how that was accomplished.
Thanks,
Terry
Tom St Denis wrote:
> Terry Neckar wrote:
> >
> > The SHA-1 algorighm is not the right one. It puts out 5 words, 4 bytes
> > each. I need one that puts out one six ASCII character string, such as
> > "AXBQE3". Any other ideas?
>
> Why not just truncate the output of SHA-1? Doesn't seem you are
> thinking about this.
>
> Tom
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: (MERCY) Overcomming the slack used by IV's
Reply-To: [EMAIL PROTECTED]
Date: Sun, 23 Apr 2000 16:32:08 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
: The motivation behind MERCY apparently is that normal block ciphers need
: IV's to become secure over a large range of blocks. However why can't
: you just expand the sector number to the size of the block?
: For example on a FAT32 system each sector is designated by a 32 bit
: number, well why can't you just do something like
: s = sector #
: IV = s || s || s || s
: (for a 128 bit block)
: Or use the 's' as a seed for a word sized LFSR and make the Iv that way?
: Basically you don't need to implicitly store the IV to use one. just
: derive it from the sector number.
: I.e MERCY is moot.
Mercy is already doing something similar to this. According to:
http://www.cluefactory.org.uk/paul/mercy/mercy-paper/node3.html
"Mercy accepts a sector number as a randomiser". It calls this "spice".
It is 128 bits and gets fed into the "F-function" - which you can see at:
http://www.cluefactory.org.uk/paul/mercy/mercy-paper/node4.html
The spice is not intended to be concealed from the attacker.
*Apparently* the term "spice" (in this context) was coined by Rich
Schroeppel in his "Hasty Pudding Cipher specification".
Mercy is designed to be fast (esp. fast to decrypt), small, secure and
simple. It is also a little unusual in that it uses a 4096-bit block
size.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Be good, do good.
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: Simple XOR breaking - What is the logic?
Date: 23 Apr 2000 16:47:01 GMT
In <[EMAIL PROTECTED]> Eero <[EMAIL PROTECTED]> writes:
>If I XOR the original ciphertext with the shifted
>ciphertext or vice versa, the outcome will be plain rubbish.
No, it will not be plain rubbish. It will be the original plain text
XORed with itself shifted three spaces to the right. Ie, it will be
English Xored with a shifted version of English . As such it has a huge
amount of redundancy in it which will allow decryption using standard
"frequency analysis, etc". It is not that you can simply read out the
results after you have done that, it is that you can use standard
techniques now to descramble the resultant "rubbish"
>writer mean when he tells you to "shift" the ciphertext
>and "XOR it with itself"? Or is just a big hoax to scare
>people away from Microsoft and its encryption standards
>which are "faster and almost as secure as DES" :)
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Checksum algorithm which is ASCII
Date: Sun, 23 Apr 2000 16:47:36 GMT
Terry Neckar wrote:
>
> I have an actual file at http://www.microcoders.com/keyfile.dat that has the
> checksum of "$PLQDC". I'm trying to figure out how that was accomplished.
>
> Thanks,
> Terry
What is the base of "$PLQDC" is it base 64, base 20? What program gave
you that?
Tom
>
> Tom St Denis wrote:
>
> > Terry Neckar wrote:
> > >
> > > The SHA-1 algorighm is not the right one. It puts out 5 words, 4 bytes
> > > each. I need one that puts out one six ASCII character string, such as
> > > "AXBQE3". Any other ideas?
> >
> > Why not just truncate the output of SHA-1? Doesn't seem you are
> > thinking about this.
> >
> > Tom
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: GSM A5/1 Encryption
Date: 23 Apr 2000 09:12:30 -0700
Look, you are just speculating about whether this proposed
change to GSM can be made to work without too much cost.
I am skeptical, and I've tried to explain why, but it doesn't
seem to have helped. At this point, it seems pretty unlikely
that explaining in any further detail would be productive.
Why don't you go read the GSM specifications, study whether
your proposal can be cheaply implemented, and post the results
of your detailed analysis? Then maybe we can have an informed
discussion.
As it stands, I don't think this is a topic that can be
profitably discussed in the abstract without knowing anything
about GSM internals. (Except possibly for the point that, due
to the fixed frame length in GSM, your proposal would naively
appear to introduce a large bandwidth overhead, ~ 15% or so.)
If you'd like to discuss something other than GSM, that's fine.
I've written before, and I'll be happy to write again, that it
seems plausible to me that this technique could have a low
enough bandwidth overhead in some systems. Whether it's worth
the cost or not in general is a question I'll leave to someone
else. Anyway, I don't see any conflict on our positions in
the general case; where I disagree is in the case of GSM.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: (MERCY) Overcomming the slack used by IV's
Date: Sun, 23 Apr 2000 16:59:09 GMT
Tim Tyler wrote:
>
> Tom St Denis <[EMAIL PROTECTED]> wrote:
>
> : The motivation behind MERCY apparently is that normal block ciphers need
> : IV's to become secure over a large range of blocks. However why can't
> : you just expand the sector number to the size of the block?
>
> : For example on a FAT32 system each sector is designated by a 32 bit
> : number, well why can't you just do something like
>
> : s = sector #
> : IV = s || s || s || s
>
> : (for a 128 bit block)
>
> : Or use the 's' as a seed for a word sized LFSR and make the Iv that way?
>
> : Basically you don't need to implicitly store the IV to use one. just
> : derive it from the sector number.
>
> : I.e MERCY is moot.
>
> Mercy is already doing something similar to this. According to:
>
> http://www.cluefactory.org.uk/paul/mercy/mercy-paper/node3.html
>
> "Mercy accepts a sector number as a randomiser". It calls this "spice".
>
> It is 128 bits and gets fed into the "F-function" - which you can see at:
>
> http://www.cluefactory.org.uk/paul/mercy/mercy-paper/node4.html
>
> The spice is not intended to be concealed from the attacker.
>
> *Apparently* the term "spice" (in this context) was coined by Rich
> Schroeppel in his "Hasty Pudding Cipher specification".
>
> Mercy is designed to be fast (esp. fast to decrypt), small, secure and
> simple. It is also a little unusual in that it uses a 4096-bit block
> size.
While the design is certainly interesting, the main reason for using a
large block is so that an IV is not required (?). But you don't need to
actually store the IV to use it.
Since there are other ciphers such as Blowfish that have been around for
much longer and are actually faster then MERCY. My idea is just to use
that instead.
Tom
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: GOST related key attack
Date: 23 Apr 2000 09:37:10 -0700
Good point.
But it may be worth pointing out that these keys are also weak
in another sense: encryption is the same as decryption (up to
possibly a swap of the halves of the block). This weakness may
be more of a practical concern than related-key attacks.
Actually, I think any of the 2^128 keys of the form ABCDDCBA has
this "encryption = decryption" property, and this is an even more
general class of weak keys.
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: factor large composite
Date: 23 Apr 2000 18:04:35 GMT
I think it goes without saying that this question of factoring depends
tremendously on how much "other" info is available. Is the 2048 number used in
RW or RSA? If so, what is the public exponent? What was the seed? In
practise, MOST 2048 bit numbers can be factored, or at least split.
Don Johnson
------------------------------
From: Andrew Carol <[EMAIL PROTECTED]>
Subject: Re: factor large composite
Date: Sun, 23 Apr 2000 11:47:34 -0700
In article <[EMAIL PROTECTED]>, DJohn37050
<[EMAIL PROTECTED]> wrote:
> I think it goes without saying that this question of factoring depends
> tremendously on how much "other" info is available. Is the 2048 number used
> in
> RW or RSA? If so, what is the public exponent? What was the seed? In
> practise, MOST 2048 bit numbers can be factored, or at least split.
> Don Johnson
Most can be factored only because most have many, many small factors.
Sadly the ones choosen for RSA have only two factors which are quite
large. It can certainly be factored, but only in time measured in
years or decades.
Oh well.....
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: factor large composite
Date: Sun, 23 Apr 2000 18:52:19 GMT
Andrew Carol wrote:
>
> In article <[EMAIL PROTECTED]>, DJohn37050
> <[EMAIL PROTECTED]> wrote:
>
> > I think it goes without saying that this question of factoring depends
> > tremendously on how much "other" info is available. Is the 2048 number used
> > in
> > RW or RSA? If so, what is the public exponent? What was the seed? In
> > practise, MOST 2048 bit numbers can be factored, or at least split.
> > Don Johnson
>
> Most can be factored only because most have many, many small factors.
> Sadly the ones choosen for RSA have only two factors which are quite
> large. It can certainly be factored, but only in time measured in
> years or decades.
>
> Oh well.....
Calc the estimated time for a 2048 bit composite and tell me it can be
done in decades...
Also the space is a big problem...
Tom
------------------------------
Date: Sun, 23 Apr 2000 15:17:48 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: factor large composite
Tom St Denis wrote:
> Andrew Carol wrote:
> >
> > In article <[EMAIL PROTECTED]>, DJohn37050
> > <[EMAIL PROTECTED]> wrote:
> >
> > > I think it goes without saying that this question of factoring depends
> > > tremendously on how much "other" info is available. Is the 2048 number used
> > > in
> > > RW or RSA? If so, what is the public exponent? What was the seed? In
> > > practise, MOST 2048 bit numbers can be factored, or at least split.
> > > Don Johnson
> >
> > Most can be factored only because most have many, many small factors.
> > Sadly the ones choosen for RSA have only two factors which are quite
> > large. It can certainly be factored, but only in time measured in
> > years or decades.
> >
> > Oh well.....
>
> Calc the estimated time for a 2048 bit composite and tell me it can be
> done in decades...
>
Well, for an arbitrary 2048-bit number, the _average_ time to factor is probably
pretty small. 1/N will have factor N, which means on _average_ you generate factors
very quickly.
------------------------------
** 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
******************************
