Cryptography-Digest Digest #61, Volume #12 Mon, 19 Jun 00 09:13:01 EDT
Contents:
Re: Q: Equally like bit-flips in a Gray code? (Tim Tyler)
Re: Extending LFSR...... (Tim Tyler)
Re: Extending LFSR...... (Tim Tyler)
Re: Comments please: A protocol for Digital voting (Roadkill)
Re: XOR versur MOD (Zulfikar Ramzan)
Re: AWFUL PUN (was: Why the golden ratio?) (anonymous)
Re: XOR versur MOD (Runu Knips)
Re: XOR versur MOD (tomstd)
Re: Online Text Encryption ("Dan Coyle")
Re: Mixing Xor and Addition ("Al Grant")
Re: Random sboxes... real info (Roger Carbol)
Re: Logical attack on RSA (DJohn37050)
----------------------------------------------------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Q: Equally like bit-flips in a Gray code?
Reply-To: [EMAIL PROTECTED]
Date: Mon, 19 Jun 2000 11:24:13 GMT
Guy Macon <[EMAIL PROTECTED]> wrote:
: M Joonas Pihlaja wrote:
:>I'm trying to find a Gray code in which each bit is 'equally
:>likely' to change between adjacent code words. Well, more likely
:>than in the the usual (ix+1)^(ix>>1) code at least. [...]
: Here is how to get as close as you can get for a 0 to 9 code.
: [1] Some random bit sequence = 0
: [2] Flip a random bit.
: Result = 1
: [3] Flip a random bit.
: Discard and repeat if result is already in use.
: Result = 2
: (Repeat until you reach 9)
Surely there's no reason to think that this will produce an equal
frequency (or as near to this as is possible) of bit-flips.
I suspect this only works at all because it 0-9 doesn't completely fill up
a 4-bit space.
For longer sequences - or where there's less wasted space - there doesn't
appear to be a guarantee that this process will terminate.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Breast is best.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Extending LFSR......
Reply-To: [EMAIL PROTECTED]
Date: Mon, 19 Jun 2000 11:29:39 GMT
Simon Johnson <[EMAIL PROTECTED]> wrote:
: Since i am no longer working in GF(2) but in some GF(p). I could
: use primes as the exponents, provided they are smaller than the
: new modulo. For example:
: x^31 + x^17 + x^13 + x^7 + x^3 + x^2 mod 257
: Would be primitive, and once converted to a LFSR would result in
: a period which is the maximum allowed?
: Instinct tell me this period is 257^31?
This won't be the period. LFSRs never completely span the possible state
space - since they always omit the all-zero state.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Goodbye cool world.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Extending LFSR......
Reply-To: [EMAIL PROTECTED]
Date: Mon, 19 Jun 2000 11:35:05 GMT
Brian McKeever <[EMAIL PROTECTED]> wrote:
[Re: Any thoughts about the period?]
: All the theorems still apply - primitive polynomial implies a period of
: p^n -1 (and the zero fixed point).
Indeed. From "Shift Register Sequences", p.36:
``Anywhere in this chapter where "mod 2" has been used, a similar
discussion applies to the more general "mod m" case. [...]
Such a shift register will have a period of m^r - 1 or less.''
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ I'm pink :. I'm spam
------------------------------
Date: 19 Jun 2000 12:18:55 -0000
From: Roadkill <[EMAIL PROTECTED]>
Subject: Re: Comments please: A protocol for Digital voting
=====BEGIN PGP SIGNED MESSAGE=====
Mok-Kong Shen wrote:
>
> Roadkill wrote:
>
> > First, secure random numbers are generated and (securely) distributed
> > among voters. These numbers are your ticket into the voting booth and
> > they must be large enough to ensure that they can't be guessed by
> > cheaters (like 256 bits, that's a snowflakes chance in hell to guess
> > correctly, even if there are more than 6.000.000.000 or about 2^32
> > voters). Software ensures that noone is given the same number as
> > somebody else. (Not quite unlike the 'token' in www.Freedom.net)
>
> I have a bunch of questions:
> How do you actually distribute the numbers to the people? Via normal
> post or other means? Are you sure that the way from you to the voter
> is absolutely secure? What happens, if the voter stores the number at
> a not absolutely secure place and someone gets a copy? Do you
> check that the person getting a number is a legitimate voter? How?
> How do you ensure that nobody gets two numbers and every legitimate
> voter gets one?
First I want to apologize for the late reply. I'm relatively new to nym
servers and something went wrong with my original reply. I format these
messages by hand and I lost the original message. Yesterday I had a
family happening (very nice), so here is my second try ;-)
What I think must happen is some kind of hybrid system as a transition.
Where people can vote on paper, or by e-mail or https if they have a
secure digital ID. The voter should choose to vote digitally in advance
of the elections (e.g. by visiting a web site by use of their digital
ID).
To be honest, the identification number for the validator computer was
inspired by the way www.Freedom.net exchanges its tokens for cash. They
use a 'random' number too.
I think the ID numbers can be distributed by PGP or some other crypto
system securely, at the time that people carry their digital ID on a
smart card or a digital passport.
Best would be if people could also vote at a computer in the place where
people normally vote (they should beware of wiretaps), or at a friends
or neighbours house, or at a cyber cafe. But I see the problems here in
identifying people. Maybe they could pick up their 'random ID number' at
the local town hall on showing their passport, if they lose it or if (a
copy) gets stolen they lose their vote :-( Also people could be
threathened and forced to turn over their random numbers. This should be
reported to the police I guess (unless they are the ones threathening
you). A strong point of this scheme is that you can vote at any place
with a computer installed, so the intimidator doesn't know precisely
where to show up.
You made me think, and I see lots of problems with digital voting.
Perhaps it is even impossible without people getting a digital passport
or digital ID first.
> > Secondly, a secure random number is generated by each voter. These
> > numbers are your ticket into the tallier (=vote counting machine) and
> > must be large enough to ensure that each legimit vote is unique (like
> > also 256 bits). If two legimit voters accidently choose the same number
> > (birthday attack), only the first person to administer his or her vote
> > gets counted, so it is in everybodies best interest to generate
> > cryptographicly strong random numbers. I haven't got the calculus ready
> > in my mind to produce the right size of number but I guess 256 bits
> > would suffice.
>
> Since collision can't be absolutely ensured not to occur, would you
> complain, if you happen to be the second person and your vote
> becomes nullified?
This is just a chance you take. Even in PGP where the Key ID is 64 bits
(internally), I haven't heard of any collitions taking place. With 256
bits chances would be even smaller. You might just as well get hit by a
crashing airoplane on your way to the voting booth. At least now you can
vote at home, so there chances improve.
If of course a bug like recently discovered in PGP 5.0x for Unix gets
found, re-elections should be in order. So there is your complaint.
Regards,
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: Mon Jun 19 12:18:52 2000 GMT
From: [EMAIL PROTECTED]
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3a
Charset: noconv
iQCVAwUBOU4PrZLupyyiz83tAQH49wP+MLadsYSvZtnXyaHEepwOfLEkGUNFlHCv
OwDHNiCF6uVXRAH5sclAm/PNKHA2ayfz2monLDskJHGI0EZh4UkFzaWAkjdg3vsW
5Ea1UMf1/CCY1myVxbu0Yhnur8MK9SLqvib8fpYIvy6qD/ZKaYjeTpEBRD2JWuj1
Qwm4pwR2kN8=
=N64S
=====END PGP SIGNATURE=====
------------------------------
Date: Mon, 19 Jun 2000 08:24:41 -0400
From: Zulfikar Ramzan <[EMAIL PROTECTED]>
Subject: Re: XOR versur MOD
> addition modulo greater than two may have different
> security than XOR (addition modulo 2). Just
> depends on the cipher. DES with addition modulo 32
> is weaker than with XOR (someone wrote a paper
> back in the 80s). RC5 is probably stronger with addition
To add to this, when we look at idealized DES-like ciphers (for example
Luby-Rackoff) there are cases when using an addition mod 2^n in a Feistel
permutation gives us a provably secure construction, whereas using XOR (addition
in GF(2^n)) yields a cipher that is trivially breakable.
I have paper on this topic on my web page.
One thing is that since XOR is its own inverse, if one is not careful in using it
in cipher design, then the resulting cipher may have involutory-like properties.
(an involution is a function f such that f(f(x)) = x) and thus may be easily
distinguishable from random.
There have been cases when these types of properties have been exploited.
PS If you have a reference for the above mentioned paper on DES with operations
other than XOR, I'd definitely be interested in seeing it!
--
--Zully
=======
Zulfikar Ramzan (AKA Zully)
Laboratory for Computer Science, MIT
NE43-311, (617) 253-2345
http://theory.lcs.mit.edu/~zulfikar/homepage.html
------------------------------
Subject: Re: AWFUL PUN (was: Why the golden ratio?)
From: anonymous <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Date: Mon, 19 Jun 2000 05:24:23 -0700
[EMAIL PROTECTED] (John Savard) wrote:
>(As the mathematician in
question
>is deceased, I suppose he can't do anything but rest on his
laurels.)
>
I read someplace that the person who rests on his laurels is
wearing them in the wrong place. Perhaps the mathematician in
question would agree, were he able to do so.
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
Date: Mon, 19 Jun 2000 14:25:06 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: XOR versur MOD
Jacques Th�riault wrote:
> Is there any advantages of using XOR instead of Modulo N when we mix a
> random stream with plaintext.
Hmm the main difference is AFAIK that XOR can be implemented in O(1) in
hardware, while implementing Addition in hardware is principially a
matter of O(log(n)), with n number of bits of the values. However, there
are many tricks to upspeed addition, but they require additional
transistors, where the most primitive implementation of addition already
requires much more transistors as the XOR implementation.
All this doesn't matter in software because additions as well as XOR
require exactly the same time on a general purpose processor.
------------------------------
Subject: Re: XOR versur MOD
From: tomstd <[EMAIL PROTECTED]>
Date: Mon, 19 Jun 2000 05:30:40 -0700
[EMAIL PROTECTED] (Mack) wrote:
>What I was trying to say is that addition appears to
>help distribute the bits in RC5. Whether this is actually
>true or whether it leaves RC5 open to some future
>attack that XOR might prevent is an open question.
>Unless someone has an attack they would like to share.
No, again it's because the addition and xor does not commute
through the rotation (see mod n analysis).
Anyways, mixing add and xor is not a bad idea...
Tom
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
From: "Dan Coyle" <[EMAIL PROTECTED]>
Subject: Re: Online Text Encryption
Date: Mon, 19 Jun 2000 07:33:59 -0500
"Let's begin the snake oil attack.."
Let's get one thing straight. "snake oil peddling" implies that I am somehow
selling something. Well if you find a page on the website that even mentions
money, or payment, please let me know, because as last I checked it didn't.
I am not selling anything, just offering my own observations and opinions to
the public. Also flames are not usually the kind of feedback one expects
from the level of professionalism that is usually shone on this newsgroup,
but since the perception was so misguided, I feel I must apologize for the
level of detail that I went into on the "What is" page on the website, and
so I must explain in better detail so that it may be fully understood.
"Which is essentially meaningless. Adding 'time' into symmetric
cryptography has been done before this is nothing new. Also
it's called a 'salt' not 'another dimension'. And another thing
is that not all symmetric key algorithms are "linear in nature"
that is just plain false. And how does adding a salt determine
the level of security?"
Actually it's not a salt at all.
Salt -
"An unnecessarily cute and sadly non-descriptive name for an arbitrary
value, unique to a particular computer or installation, prepended to a
password before hash authentication. The "salt" acts to complicate attacks
on the password user-identification process by giving the same password
different hash results on different systems. Ideally, this would be a sort
of keying for a secure hash. " (source Ritters Dictionary of Technical
Cryptography - http://www.io.com/~ritter/GLOSSARY.HTM#Salt)
This definition states that a salt is a, machine specific, algorithm for
modifying password hashes stored in a message. It does not discuss using a
given amount of time to encrypt the message, so if there is another
definition that you would like to show me, please give me an URL or
something so that I may see your sources.
"This is garbage aswell. If I assume a rate of 'x' keys per
second in a brute force attack, I can be fairly confident that a
n bit key will offer 2^n/x seconds of resistance. You can
estimate advances as well (doubling every 18 months, etc...).
Also your method (I don't even need to look at it to tell) will
not allow specific time constraints. You can't be sure of
computer advances so how can you say exactly how long it will
take to solve?"
Again I apologize because, had I given proper descriptions of the methods,
you would have seen that this is the true strength of the algorithm. You
see, you are assuming that you can generate 'x' keys per second and test
them in a brute force attack, which isn't true, you see in trying an
incorrect key you would not know when to stop decrypting, because it doesn't
build the amount of time into the encrypted message, it just keeps
encrypting, creating different keys as it goes, until a certain time period
has elapsed. Then records where it stopped, and XOR's that result with the
original iteration key. Now in order to decrypt it, it has to perform
exactly the same amount of decrypt iterations and start with the correct
key, by keying in the correct original iteration key, it extracts the final
iteration key and starts decrypting from the end. When it finally gets back
to the original iteration key, it stops decryption and knows that its job is
done. But if the wrong key is used, by entering in an incorrect original
iteration key, it comes up with an incorrect ending key and begins
decrypting. Well since it starts in the wrong place it will almost never
know when to stop, IE chances are 1 in 2^128 that it will ever run across
the correct Starting iteration key, in which case it will have decrypted it
incorrectly anyway, but it will have taken an average of 2^64 iterations of
decrypting for an attacker to find out if only one key truly doesn't work.
"This is pure garbage too. If your times are symmetric then a 50
year secret will take 50 years to make. This is obviously not
well thought through.
No deterministic process can prevent brute force, only delay it.
You obvioulsy are some type of snake oil peddler and I hope
nobody buys into your garbage.
"
Yes, if you choose to encrypt a message for 50 years, it will take 50 years,
with the correct key, to decrypt. But you usually don't have to do that, I
find that 3 seconds, for a <1k message, usually gets encrypted over 10000
times, which should be hard enough decrypt on anything used today.
I think the most misunderstood point I was trying to make was that if you
use this method the message encrypted with it would be safe forever. And of
course that's absurd. No message, no matter how secure, is 100% protected,
simply because a person could guess the correct password, and the message
would be properly decrypted. What I was saying, though, was that If you are
using a 500Mhz machine today, and encrypt a message for N seconds, it will
be (relatively) secure for a certain amount of time, but if, in the future,
you are using a 10GHz machine, and you encrypt another message, that message
will again be (relatively) secure for the same number of years. Not because
you've used an algorithm with more bit's in its key, but because the 10Ghz
machine encrypted the text for the same N Seconds, and encrypted for more
iterations, causing an attacker to have to decrypt it for the additional
amount of iterations.
The method I am proposing isn't the answer to everything, but It's my answer
to Brute force attacks, if I can use a parallel algorithm to solve RSA-128
and try 100,000 keys per second, or even a million, or a billion. Moore's
law takes hold, and you will need to update the amount of key bit's used in
future editions of the program. But with a time based Algorithm, you don't
need to do that.
This method is not without it's flaws either. If a person wanted to use this
algorith many times in a short time span, the efficiency of the algorithm
goes down, so it wouldn't be usefull for real time communicatioon. I
understand this, because I designed the algorithm to be as hard to brute
force as possible nothing else.
I do appreciate any "Constructive" critisism, and I thank you for your time,
and I do agree with you that a certain amount of "Fluff" was inserted into
the "What is" page, and I will try to rectify that. We were just having too
much fun the day we wrote that, that it didn't seem, at the time, like it
came from a Microsoft Marketer. J
Dan Coyle
"tomstd" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Let's begin the snake oil attack..
>
> "PSIFRE - pronounced ('si-fur) - is a cryptographic algorithm
> that uses, not only key size, but time as an enhancement to the
> normal security of the data it encodes. Simply put all current
> symmetric key algorithms are linear in nature. With the
> addition of time, as an added dimension to the algorithm, for
> the first time you have the option of determining the level of
> security you wish to use to encrypt your data."
>
> Which is essentially meaningless. Adding 'time' into symmetric
> cryprography has been done before this is nothing new. Also
> it's called a 'salt' not 'another dimension'. And another thing
> is that not all symmetric key algorithms are "linear in nature"
> that is just plain false. And how does adding a salt determine
> the level of security?
>
> "Current symmetric Algorithms use key size as the determining
> factor in how secure the data has been encrypted, but PSIFRE
> not only uses a 128 bit key, but it allows you to choose how
> long you want your data to be encrypted. "
>
> ---
> This is garbage aswell. If I assume a rate of 'x' keys per
> second in a brute force attack, I can be fairly confident that a
> n bit key will offer 2^n/x seconds of resistance. You can
> estimate advances as well (doubling every 18 months, etc...).
>
> Also your method (I don't even need to look at it to tell) will
> not allow specific time constraints. You can't be sure of
> computer advances so how can you say exactly how long it will
> take to solve?
>
> "All symmetric cipher's start with a key, that ranges in size
> from 40 to 2048 bits. PSIFRE starts by hashing the users' key
> into a 128 bit iteration key. It then prompts the user for a
> period of time to encrypt the data. When the user enters the
> data and then issues the command to encrypt it, PSIFRE begins a
> looping pattern, reencrypting the data over and over again,
> changing the iteration key after each iteration, until the time
> period specified has elapsed. When this happens, PSIFRE merges
> the first and last 128 bit iteration keys into one final key
> that is appended to the data.
>
> When a user wants to decrypt the data, he/she enters the data,
> with the final key within it, and the same key with which data
> was encrypted. The key the user enters, is used to extract the
> Last iteration key used while encrypting the data. It then
> works its way back to the original text by re-decrypting the
> data over and over again until the iteration key is equivalent
> to the key that the user entered to decrypt the message, at
> which point PSIFRE stops decrypting the ciphertext and displays
> the result."
>
> ---
> This is pure garbage too. If your times are symmetric then a 50
> year secret will take 50 years to make. This is obviously not
> well thought through.
>
> But it gets better
> "What if someone attempts to decrypt the message, and fails to
> enter the correct starting key? They will not only fail to
> know how long the data has been decrypted, but they will have
> started decrypting the data with the wrong key. Thus message
> will not be decrypted properly. Not only that, but if the user
> doesn't decrypt the message for a long enough period of time,
> they could stumble over the correct key, and still not decrypt
> the message properly. This is what we feel prevents the brute-
> force decryption of a PSIFRE encrypted message."
>
> No deterministic process can prevent brute force, only delay it.
>
> You obvioulsy are some type of snake oil peddler and I hope
> nobody buys into your garbage.
>
> Tom
>
> Got questions? Get answers over the phone at Keen.com.
> Up to 100 minutes free!
> http://www.keen.com
>
------------------------------
From: "Al Grant" <[EMAIL PROTECTED]>
Subject: Re: Mixing Xor and Addition
Date: Mon, 19 Jun 2000 13:39:28 +0100
"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).
>
> Out of the 32640 possible equations like the above 4373 of them
> lead to equalities
Given that
(a + b) - (a xor b) = 2(a and b)
you are looking for pairs a, b such that
2(a and b) = 0 mod 2^n
Any of the lower n-1 bits can be in a, b or neither
(3 choices), and the top bits can be chosen freely
(4 choices). This gives 4(3^(n-1)) choices for a
and b. Since you're looking for distinct pairs,
take away (0,0) and (2^(n-1),2^(n-1)) and divide
by 2 because you chose the other pairs twice.
This gives you 2(3^(n-1))-1 distinct pairs.
2(3^(8-1))-1 = 4373
2(3^(10-1))-1 = 39365
A cypher or hash cannot be built entirely around add
and xor as it would then be possible to run it modulo
2^k for k smaller than wordsize n. Some other kind
of avalanche operation is needed (e.g. rotate or s-box).
I may be stating the obvious. I hope so. One very
widely-used (albeit proprietary and unfashionable)
cryptosystem has a serious weakness in this respect.
I would be interested if anyone can supply a reference
to the problems of mixing add and xor, or to modulo-k
attacks, being discussed in the literature.
--
Al Grant
------------------------------
From: [EMAIL PROTECTED] (Roger Carbol)
Subject: Re: Random sboxes... real info
Date: Fri, 16 Jun 2000 18:48:20 GMT
[EMAIL PROTECTED] (David A. Wagner) wrote:
>Nonsense. That's on par with the following popular fallacy:
> Myth: "the all-zeros key is a weak key for the one-time pad
> (because it acts as the identity transformation), and
> so the one-time pad can be strengthened if you exclude
> the all-zeros key."
>Such reasoning is pure balderdash. The myth is, of course, false.
What is the meaning of "key" with reference to a one-time pad,
anyways? The two concepts seem mutually exclusive, at least
by my limited understanding.
.. Roger Carbol .. [EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: Logical attack on RSA
Date: 19 Jun 2000 12:53:02 GMT
Michael, I think many people have thought of this before, but it is
interesting to see how far you can get.
Don Johnson
------------------------------
** 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
******************************
