Cryptography-Digest Digest #51, Volume #12 Sat, 17 Jun 00 19:13:00 EDT
Contents:
Re: Evidence Eliminator Dis-Information Center (lordcow77)
Re: Evidence Eliminator Dis-Information Center (tomstd)
Re: Weight of Digital Signatures (Tom McCune)
Re: Cipher design a fading field? ("John A. Malley")
Re: Evidence Eliminator Dis-Information Center (lordcow77)
Re: Weight of Digital Signatures (Matthew Montchalin)
Re: Comments please: A protocol for Digital voting (Roadkill)
Re: small subgroups in Blum Blum Shub (Terry Ritter)
Re: Mixing Xor and Addition (John M. Gamble)
Re: Cipher design a fading field? ("Trevor L. Jackson, III")
Re: Cipher design a fading field? ("Trevor L. Jackson, III")
Re: Flattening of frequency distributions (zzapzing)
Re: Weight of Digital Signatures ("Michael Brown")
Re: Evidence Eliminator Dis-Information Center (tomstd)
Re: Cryptographic voting (zzapzing)
Re: XOR versur MOD (Mok-Kong Shen)
Re: Mixing Xor and Addition ("Scott Fluhrer")
----------------------------------------------------------------------------
Subject: Re: Evidence Eliminator Dis-Information Center
From: lordcow77 <[EMAIL PROTECTED]>
Crossposted-To:
alt.privacy,alt.privacy.anon-server,alt.security.pgp,comp.security.firewalls
Date: Sat, 17 Jun 2000 13:24:29 -0700
tomstd <[EMAIL PROTECTED]> wrote:
>>Format doesn't wipe anything. Go crawl under your rock again.
>
>Format writes a binary constant to every byte of every sector of
>the HD. That's a pretty effective wipe if you ask me.
>
>Unlike floppy drives hard disks are designed to have a very high
>density. So there is little room for "magnetic" remininents of
>the original data.
>
I feel guilty just replying to this blatantly off-topic spew,
but format certainly does not "write a binary constant to every
byte of every sector" of a fixed disk.
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
Subject: Re: Evidence Eliminator Dis-Information Center
From: tomstd <[EMAIL PROTECTED]>
Crossposted-To:
alt.privacy,alt.privacy.anon-server,alt.security.pgp,comp.security.firewalls
Date: Sat, 17 Jun 2000 13:29:19 -0700
lordcow77 <[EMAIL PROTECTED]> wrote:
>tomstd <[EMAIL PROTECTED]> wrote:
>>>Format doesn't wipe anything. Go crawl under your rock again.
>>
>>Format writes a binary constant to every byte of every sector
of
>>the HD. That's a pretty effective wipe if you ask me.
>>
>>Unlike floppy drives hard disks are designed to have a very
high
>>density. So there is little room for "magnetic" remininents of
>>the original data.
>>
>
>I feel guilty just replying to this blatantly off-topic spew,
>but format certainly does not "write a binary constant to every
>byte of every sector" of a fixed disk.
Then why do formats write ascii 'v' to each sector of the disk?
(when I formated a floppy).
I can hardly believe quick formats of a 13gb hd could take 10
mins...
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
From: Tom McCune <[EMAIL PROTECTED]>
Subject: Re: Weight of Digital Signatures
Date: Sat, 17 Jun 2000 20:39:49 GMT
=====BEGIN PGP SIGNED MESSAGE=====
Hash: RIPEMD160
In article <[EMAIL PROTECTED]>, tomstd
<[EMAIL PROTECTED]> wrote:
>Using what protocol? I think ECC is secure, but no RSA is
>secure... how about DSA? What hash? I like TIGER but I think
>SHA-1 is secure or perhaps RIPEMD or HAVAL...What PRNG shall we
>use...and so on...
>
>This is hardly a settled issue.
>
>Tom
Tom, please explain what you mean about RSA not being secure. I can't
think of a more secure signature than a 2048 bit RSA key using either
RIPEMD-160 or SHA1 for the hash.
=====BEGIN PGP SIGNATURE=====
Version: PGP 6.5.2 -- QDPGP 2.61a
Comment: My PGP Page & FAQ: http://www.McCune.cc/PGP.htm
iQEUAwUBOUviFDYk/PXew/BzAQONUAfyA4H4a9D9PwHWPL0WsXNdFj/7u3mWv4UF
autoLQKIbtLKJD1McfpoPAGy0NJJ+1T6ps357hzboUZNH4BelraCWf5zx/ekdYKK
1J9OQY/M6CMh5KqpFsjRPYXnmfP3GyKENjP8hJoEyM2DfURzqiVvWCZ9QPes3HEh
aCi7UsYInwFzb6+pioKGZRI3/i8FnrBWOQwacIp095BeJkFH5LZ3yKlVHix5Hqdq
ZZBKumgrVm984vT6SsBPa6t8ovxxJm0sZEjths5ChWznCqr1tdES0ZGdq9LY021s
DF6tzpnBgCMrs3YGs15QLQ87klM3CMchPbCXUwwKrwCUotbDWkgp
=S/aO
=====END PGP SIGNATURE=====
------------------------------
From: "John A. Malley" <[EMAIL PROTECTED]>
Subject: Re: Cipher design a fading field?
Date: Sat, 17 Jun 2000 13:52:28 -0700
Here's a follow-up on the example ciphertext-only cryptanalysis "thought
experiment" post.
That post addressed the question "Is the ciphertext-only cryptanalysis
of a uniliteral cipher decidable?"
We know the plaintext is an English language string, we get only the
ciphertext, and we decrypt the ciphertext with all possible uniliteral
substitutions to create a finite set of candidate plaintext strings. One
of those plaintext candidates is the original plaintext.
This cryptanalysis is undecidable iff deciding a (finite) string is a
member of the language E (English) is undecidable. So without an
algorithm that decides a string belongs to the English language, there
is no algorithm to automate cryptanalysis of uniliteral substitution.
Now consider a known plaintext cryptanalysis. We decrypt the ciphertext
with all possible uniliteral substitutions to create a finite set of
candidate plaintext strings. Is there an algorithm that can compare each
candidate plaintext string to the known plaintext and decide on
equivalence, and thus determine the key ( which corresponds to the
uniliteral substitution that correctly decrypted the ciphertext)?
Yes, iff the plaintext comes from a Turing-recognizable language.
So given a finite string of plaintext and its corresponding ciphertext,
the known plaintext cryptanalysis of a uniliteral cipher is decidable (
assuming English is Turing-recognizable.)
And this brings out the eerie truth that when the plaintext comes from a
non-Turing-recognizable language, even when one gets the plaintext and
its ciphertext there is NO algorithm able to decide which instance of
the decryption (and thus the key) produced the correct decryption
(candidate plaintext equal to the original plaintext.)
John A. Malley
[EMAIL PROTECTED]
------------------------------
Subject: Re: Evidence Eliminator Dis-Information Center
From: lordcow77 <[EMAIL PROTECTED]>
Crossposted-To:
alt.privacy,alt.privacy.anon-server,alt.security.pgp,comp.security.firewalls
Date: Sat, 17 Jun 2000 13:59:47 -0700
tomstd <[EMAIL PROTECTED]> wrote:
>Then why do formats write ascii 'v' to each sector of the disk?
>(when I formated a floppy).
>
>I can hardly believe quick formats of a 13gb hd could take 10
>mins...
What you may or may not believe has no relationship to what is
true. Format will not wipe a fixed disk.
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
From: Matthew Montchalin <[EMAIL PROTECTED]>
Subject: Re: Weight of Digital Signatures
Date: Sat, 17 Jun 2000 13:52:37 -0700
On Sat, 17 Jun 2000, tomstd wrote:
|Using what protocol?
The bill didn't specify the protocol.
|I think ECC is secure, but no RSA is secure... how about DSA? What
|hash? I like TIGER but I think SHA-1 is secure or perhaps RIPEMD or
|HAVAL...What PRNG shall we use...and so on...
|
|This is hardly a settled issue.
You could check out the limericks relating to John Doe and John Hancock
over at alt.arts.limericks FWIW.
------------------------------
Date: 17 Jun 2000 21:31:20 -0000
From: Roadkill <[EMAIL PROTECTED]>
Subject: Re: Comments please: A protocol for Digital voting
=====BEGIN PGP SIGNED MESSAGE=====
Sundial Services wrote:
>
> My feeling on digital-voting is that this is one place where a highly
> efficient, technology-based scheme that does not involve lots of humans
> is NOT a good idea. The reason is that way too many humans have a
> vested interest in distorting the outcome of a vote, OR in altering the
> records of a vote after it is taken, and way too much ingenuity is
> expended on accomplishing that.
>
> A paper-vote always goes back to a massive amount of real paper. And if
> you want to re-count them, feel free. If you want to falsify the voting
> outcome, you've got to get inside that warehouse, unlock those sealed
> boxes, stuff more paper in, and ...
>
> Electronic voting sounds great, but you know, I think that the people
> who will vote will vote, and computers won't make voters out of couch
> potatoes.
You raised some good points, maybe digital voting should not be on the
agenda's of political leaders. If it would, however, privacy should be
their number one concern. And anonymous remailing techniques could help
here.
Roadkill
- --
"If you're so special, why aren't you dead" - Kim Deal
~~~
This PGP signature only certifies the sender and date of the message.
It implies no approval from the administrators of redneck.gacracker.org.
Date: Sat Jun 17 21:31:16 2000 GMT
From: [EMAIL PROTECTED]
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3a
Charset: noconv
iQCVAwUBOUvuJ5Lupyyiz83tAQE/RQP/SrjRpEBjTsH3Z9vO+ob2JLcGmbLH8nzB
shbjSigXcZsWfe0qpkfcDuySuuArMnaUhUfmLgyvyXBAo6AA4x1jE4ddqrVDSTJh
lmV9NKeZcvT1XFB5upBsQn17/hEE8cPf7vzDZcGKwm5mMcLH9fq2O1vHmGXsdJiy
ok1LGxDdw4c=
=v/Tn
=====END PGP SIGNATURE=====
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: small subgroups in Blum Blum Shub
Date: Sat, 17 Jun 2000 22:10:35 GMT
On 16 Jun 2000 23:00:30 -0000, in
<[EMAIL PROTECTED]>, in sci.crypt lcs Mixmaster
Remailer <[EMAIL PROTECTED]> wrote:
>> Please define "breaking". :) To me, being able to guess the upcoming
>> bits with probability 1 because you already saw them earlier in the
>> cycle, *that* spells "broke". I don't know how I would go backwards from
>> knowing the sequence to knowing the factorization, but I do know I could
>> guess upcoming bits quite easily. :)
>
>Take a look at:
>http://x61.deja.com/[ST_rn=ps]/getdoc.xp?AN=572282072
I saw that when it came out, and a short summary is:
"it follows from the RSA assumption that finding short cycles is
impossible, for moduli large enough that factorization is
intractable."
and
"The advice to choose moduli with guaranteed long cycles, and to
choose seeds that way, is completely useless."
Oddly for useless advice, the last 2/3 of the BB&S published article
concerns just this issue. The response involves forming a special
construction for N which is guaranteed to have long cycles of a
computable length, and then finding an algorithm to traverse those
cycles of known length, to show that a long cycle has been selected.
Now, did Blum, Blum and Shub simply get carried away with their own
math abilities? Shall we assume that they were they so unaware of
their first results that they simply did not understand that 2/3 of
their work was "useless"?
The world gasps at such arrogance.
>It shows a way to factor RSA moduli if you can find short BBS cycles
>(or any cycles for that matter).
The cycles in an arbitrary primes construction will have various
lengths, but as far as I know, there are always some cycles of length
1 (which I call "degenerate"). I doubt they will be much help in
factoring N. But they undoubtedly *are* the weakest possible
"sequence" (which would be, in practice, a "constant").
It may be that some of those on the other side have not really
understood the weakness of a short cycle. BB&S type systems probably
would be used as the generator of the confusion sequence for stream
ciphers. The stream cipher requires its sequence to be random-like,
and *ALSO* to not repeat. But if the BB&S happens to be on a short
cycle, it *will* repeat, and *that* is a weakness. Sufficiently short
cycles *are* weak, and there simply is nothing to debate about it.
>It would be a miracle if we could get agreement on this issue though.
>Every time it comes up, the falsehoods fly.
Then I suggest that you follow the discussion and point out those
falsehoods in detail. That will be tricky for you, though, because
you are on the wrong side.
As I see it, the principle falsehood here is the suggestion that the
discussion pertains to practical security. It does not. In practice,
selecting a short cycle would indeed be very, very unlikely. But
"unlikely" is *not* the same as "impossible."
Instead, the discussion here is about the concept of "proof" itself:
I claim that if it is *POSSIBLE* to select a short cycle, it should be
self-evident that any *proof* of security must be false. The
alternative is a clear logic error -- an actual reasoning fault.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED] (John M. Gamble)
Subject: Re: Mixing Xor and Addition
Date: 17 Jun 2000 22:21:24 GMT
In article <8ig6s7$r8s$[EMAIL PROTECTED]>,
Paul Schlyter <[EMAIL PROTECTED]> wrote:
>In article <[EMAIL PROTECTED]>,
>tomstd <[EMAIL PROTECTED]> wrote:
>
>> It's thought by some that mixing addition and xor operations is
>> a good idea (and it is) because they are different group
>> operations.
>
>They're not that different -- as a matter of fact, XOR is nothing
>but modulo-2 addition:
>
> A B A+B mod 2 A xor B
>
> 0 0 0 0
> 1 0 1 1
> 0 1 1 1
> 1 0 0 0
>
Slightly on-topic, but a while ago John Savard pointed out that
since xor was, as you point out, bitwise modulo 2 addition then
you could also write an xor-like function to do paired-bitwise
modulo 4 addition.
And if you are of a fanatical nature, you could even go beyond that.
Ahem. Of course if i were truly fanatical, i would post the whole
damn thing. Here are just a couple of the functions, which merely
demonstrate the technique. This stuff assumes 32 bit integers -
i was performing an experiment, not writing code for general use.
The pattern should be easy to see in the 'grp5' function, and it
is easy to extend.
But i suspect that after you get past groups of 4 bits it becomes
more efficient to loop-shift-and-add anyway.
/*
* Routines to add groups of bits in an integer to corresponding
* groups of bits in another integer, modulo the group size.
*
* This may be thought of as an extension of an xor operation,
* which "adds" bits in groups of one, modulo 2.
*
* Written as an experiment after reading an off-hand comment
* by John Savard in sci.crypt, so this is his fault.
* 9 Aug 1999 John Gamble
*/
/* some code snipped */
/*
* unsigned add_bits_grp2(unsigned x, unsigned y)
*
* Return an integer where each pair of bits in x are added to
* the corresponding pair of bits in y, modulo 4.
*/
unsigned add_bits_grp2(unsigned x, unsigned y)
{
const unsigned m = 0x55555555; /* To separate the bits in each pair */
unsigned c1 = (x & y & m) << 1;
unsigned z = x ^ y;
return (z & m) | (z ^ c1);
}
/* some more code snipped */
/*
* unsigned add_bits_grp5(unsigned x, unsigned y)
*
* Return an integer where each quintet of bits in x are added to
* the corresponding quintet of bits in y, modulo 32.
*/
unsigned add_bits_grp5(unsigned x, unsigned y)
{
const unsigned m = 0x42108421; /* To separate the bits in each quintet */
unsigned c1 = (x & y & m) << 1;
unsigned c2 = ((x & y & (m << 1)) | ((x | y) & c1)) << 1;
unsigned c3 = ((x & y & (m << 2)) | ((x | y) & c2)) << 1;
unsigned c4 = ((x & y & (m << 3)) | ((x | y) & c3)) << 1;
unsigned z = x ^ y;
return (z & m) | (z ^ c1 ^ c2 ^ c3 ^ c4);
}
-john
February 28 1997: Last day libraries could order catalogue cards
from the Library of Congress.
--
Pursuant to US Code, Title 47, Chapter 5, Subchapter II, '227,
any and all unsolicited commercial E-mail sent to this address
is subject to a download and archival fee in the amount of $500
US. E-mailing denotes acceptance of these terms.
------------------------------
Date: Sat, 17 Jun 2000 18:34:48 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Cipher design a fading field?
Usually we don't need to prove that the plaintext comes from a natural
language, but are willing to accept a probability estimate which is
considerably easier to construct that a proof, even for a machine-recognizable
language.
"John A. Malley" wrote:
> Here's a follow-up on the example ciphertext-only cryptanalysis "thought
> experiment" post.
>
> That post addressed the question "Is the ciphertext-only cryptanalysis
> of a uniliteral cipher decidable?"
> We know the plaintext is an English language string, we get only the
> ciphertext, and we decrypt the ciphertext with all possible uniliteral
> substitutions to create a finite set of candidate plaintext strings. One
> of those plaintext candidates is the original plaintext.
>
> This cryptanalysis is undecidable iff deciding a (finite) string is a
> member of the language E (English) is undecidable. So without an
> algorithm that decides a string belongs to the English language, there
> is no algorithm to automate cryptanalysis of uniliteral substitution.
>
> Now consider a known plaintext cryptanalysis. We decrypt the ciphertext
> with all possible uniliteral substitutions to create a finite set of
> candidate plaintext strings. Is there an algorithm that can compare each
> candidate plaintext string to the known plaintext and decide on
> equivalence, and thus determine the key ( which corresponds to the
> uniliteral substitution that correctly decrypted the ciphertext)?
>
> Yes, iff the plaintext comes from a Turing-recognizable language.
>
> So given a finite string of plaintext and its corresponding ciphertext,
> the known plaintext cryptanalysis of a uniliteral cipher is decidable (
> assuming English is Turing-recognizable.)
>
> And this brings out the eerie truth that when the plaintext comes from a
> non-Turing-recognizable language, even when one gets the plaintext and
> its ciphertext there is NO algorithm able to decide which instance of
> the decryption (and thus the key) produced the correct decryption
> (candidate plaintext equal to the original plaintext.)
>
> John A. Malley
> [EMAIL PROTECTED]
------------------------------
Date: Sat, 17 Jun 2000 18:39:34 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Cipher design a fading field?
Paul Schlyter wrote:
> In article <[EMAIL PROTECTED]>,
> Trevor L. Jackson, III <[EMAIL PROTECTED]> wrote:
>
> > English and other human languages aren't formally defined, so categorizing
> > them precisely is not possible.
> >
> > Consider that excluding a particular class of strings from formal English
> > would almost guarantee that poets, punsters, and comics would work the
> > excluded area and find ways to incorporate the forbidden fruit into their
> > material. If the writers managed to use the forbidden area to communicate
> > with an audience it would be very difficult to defend the idea that the
> > excluded area was not part of the language.
> >
> > We'd need to timestamp the language definition the way programming languages
> > are time stamped by the date of their standards and fiat currency is time
> > stamped by the date of its issuance (1970 USD versus 1999 USD and F66 versus
> > F77).
>
> Time-stamping is insufficient -- we would also need "space-stamping",
> since English has a lot of geographical variation as well (e.g. US
> English vs British English vs Canadian English vs Australian English
> vs New Zealandian English vs Pidgin English...)
True. By reductio each person has a personal definition. This would lead to
labeling each channel with the proper subset of of the languages used by the
sender and the receivers. Ick.
Futher extrapolation gets ugly because the personal languages will vary with mood,
time of day (blood sugar level), etc. This is beyond slippery.
------------------------------
Subject: Re: Flattening of frequency distributions
From: zzapzing <[EMAIL PROTECTED]>
Date: Sat, 17 Jun 2000 15:37:22 -0700
[EMAIL PROTECTED] (Mack) wrote:
> [EMAIL PROTECTED] (Bill Unruh) wrote:
snip
>frequency analysis of 8 byte blocks may have some use
>especialy if messages are similar and sent repeatedly
>with the same key.
And of course we all know that Manager Murphy L Dufus
would do exactly that. And if we try to do data
compression he (MMLD) will probably decide that a
bunch of random numbers need to be encrypted and sent,
which will of course result in the encryption routine
having to send several standardized headers that say
"this is just random data I couldn't compress it".
>It isn't simply a matter of adding pieces at random
>Layering two block ciphers wouldn't prevent the attack.
>If the first 8 or 16 bytes of any message is a key to a PRNG
>then it effectively eliminates any patterns in the output that
>are residuals of the english language for the block cipher.
>Or residuals of file headers or anything else for that matter.
>The best use of this would indeed be for hiding file headers.
>The added cost would be about 8 bytes plus decryption time.
I absolutely agree but someone will probably
start screaming "Bandwidth, Bandwidth".
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
From: "Michael Brown" <[EMAIL PROTECTED]>
Subject: Re: Weight of Digital Signatures
Date: Sat, 17 Jun 2000 22:42:58 GMT
Tom McCune <[EMAIL PROTECTED]> wrote in article
<pmR25.10526$[EMAIL PROTECTED]>...
> Tom, please explain what you mean about RSA not being secure. I can't
> think of a more secure signature than a 2048 bit RSA key using either
> RIPEMD-160 or SHA1 for the hash.
I'm not Tom, but I may be able to help.
See my postings on "Logical attack on RSA". It's not proven, but its
looking that way.
Regards
Michael Brown
_____________________________
/ [EMAIL PROTECTED] \
| (Remove .nospam) |
\_____________________________/
------------------------------
Subject: Re: Evidence Eliminator Dis-Information Center
From: tomstd <[EMAIL PROTECTED]>
Crossposted-To:
alt.privacy,alt.privacy.anon-server,alt.security.pgp,comp.security.firewalls
Date: Sat, 17 Jun 2000 15:41:48 -0700
lordcow77 <[EMAIL PROTECTED]> wrote:
>tomstd <[EMAIL PROTECTED]> wrote:
>>Then why do formats write ascii 'v' to each sector of the disk?
>>(when I formated a floppy).
>>
>>I can hardly believe quick formats of a 13gb hd could take 10
>>mins...
>
>What you may or may not believe has no relationship to what is
>true. Format will not wipe a fixed disk.
For what *i* need format is perfectly fine.
Oh well.
Tom
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
Subject: Re: Cryptographic voting
From: zzapzing <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Date: Sat, 17 Jun 2000 15:52:34 -0700
Greg <[EMAIL PROTECTED]> wrote:
>
>> For goodness sakes, people could use laundry
>> tickets for money if they wanted to. Actually
>> that gives me an interesting idea about
>> cryptographic money .... I'll have to work on
>> it after I get the *cryptographic* *voting*
>> thing figured out (hint).
>
>After carefull consideration of what would be required for a
voting
>system to resist fraud and tampering, I have come to the
conclusion
>that given the requirements below, one cannot be made:
>
>1. It must be secret ballot
>2. Voters cannot be identified (by law)
>3. Voters cannot be deduced from the votes
>4. Votes must be verifiable (not altered) by anyone
>5. Voters cannot vote more than once
>6. The system requires no trust of anyone
>
I agree but I would relax requirement #2.
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: XOR versur MOD
Date: Sun, 18 Jun 2000 01:10:22 +0200
tomstd wrote:
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> >tomstd wrote:
> >> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> >> >Jacques Th�riault wrote:
> >> >> Is there any advantages of using XOR instead of Modulo N
> when
> >> we mix a
> >> >> random stream with plaintext.
> >> >
> >> >Mod 2^n addition, with n equal to the number of bits in
> >> >a computer word, is simply done with the addition operation
> >> >for unsigned integers. Because of the carry-overs, the bits
> >> >of a word from the PRNG and the bits of a word from the
> >> >plaintext are not always combined (one to one) in fixed
> >> >pairs as is the case with xor. This complicates analysis
> >> >at the bit level somewhat and is to be preferred in my
> >> >humble opinion.
> >>
> >> Not really since note that the LSB is still an 'xor'.
> >
> >There is a simple, apparently less popularly known, method
> >of catering for that issue in my humble view, if one really
> >desires a better combination of two operands using naturally
> >available computer instructions: Rotate one operand by some
> >random amount and then perform addition mod 2^n.
>
> You mean turn (a + b) into ((a <<< r) + b)?
>
> Unless 'r' changed with each usage that would still be xor-
> linear.
>
You appeared to have missed my word 'random' above.
M. K. Shen
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Mixing Xor and Addition
Date: Sat, 17 Jun 2000 15:48:02 -0700
tomstd <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> It's thought by some that mixing addition and xor operations is
> a good idea (and it is) because they are different group
> operations. This however is not essentially true. It's been
> pointed out time and time again that the lsb is xor-linear.
> Well I wrote a program to calc the equalities (a+b) == (a xor b)
> for a, b { Z(256).
Well, from a cryptographic standpoint, mixing addition and xor is not ideal.
They are pretty close to each other. In particular:
- In terms of linear cryptanalysis, addition shows some pretty high biases.
Apart from the obvious linear relationship in the least significant bits,
there are also p=0.75 equations between other bits. xor, of course, has p=1
biases in all bits
- In terms of differential cryptanalysis, addition/xor shows some pretty
strong characteristics. For both, an input differential in the high order
bit gives an output differential in the high order bit with probability 1.
For any other bit, it is probability 1 with xor, probability 0.5 for add.
- In terms of avalanche, they are too similar. With a chain of add/xor
operations, changes in bits tend to effect the corresponding output bits,
and the next couple higher order bits. It is necessary to build in some
other mechanism to do avalanche.
That said, the great advantage of add/xor is that they are fast (at least in
software). And so, the cryptographer can afford to design in lots of
add/xor operations and still have a reasonably fast cipher.
--
poncho
------------------------------
** 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
******************************
