Cryptography-Digest Digest #56, Volume #12 Sun, 18 Jun 00 14:13:01 EDT
Contents:
LSFR (Simon Johnson)
Re: LSFR (tomstd)
Re: Extending LFSR...... (Simon Johnson)
Re: Cipher design a fading field? (wtshaw)
Re: XOR versur MOD (Simon Johnson)
Re: Extending LFSR...... (tomstd)
Re: LSFR (Simon Johnson)
Re: AWFUL PUN (was: Why the golden ratio?) (wtshaw)
Re: MD5 Expansion ([EMAIL PROTECTED])
Re: XOR versur MOD (Mack)
Re: MD5 Expansion (tomstd)
Re: LSFR ("Scott Fluhrer")
Q: Equally like bit-flips in a Gray code? (M Joonas Pihlaja)
Re: Small compression/encryption problem (Rickman)
Re: Cipher design a fading field? ("John A. Malley")
Re: Evidence Eliminator Dis-Information Center ([EMAIL PROTECTED])
----------------------------------------------------------------------------
Subject: LSFR
From: Simon Johnson <[EMAIL PROTECTED]>
Date: Sun, 18 Jun 2000 08:26:54 -0700
Looking at a basic LSFR, they don't look all too secure. The
reason i say this is the whole key is spat out for the first n
clocks, where n is the size in bits of the Register?
Why is this secure?
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
Subject: Re: LSFR
From: tomstd <[EMAIL PROTECTED]>
Date: Sun, 18 Jun 2000 08:39:34 -0700
Simon Johnson <[EMAIL PROTECTED]> wrote:
>Looking at a basic LSFR, they don't look all too secure. The
>reason i say this is the whole key is spat out for the first n
>clocks, where n is the size in bits of the Register?
>
>Why is this secure?
First off they are called LFSR's not LSFR, which stands for
Linear Feedback Shift Register.
Second they are not secure, but do appear statistically random
(somewhat). It's the filters on the output of the LFSR's that
make it secure, not the LFSR itself.
Tom
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
Subject: Re: Extending LFSR......
From: Simon Johnson <[EMAIL PROTECTED]>
Date: Sun, 18 Jun 2000 08:43:39 -0700
well, this has all gone too mathematical for me :)
But would it work to simple use primes as the powers above mod 2?
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Cipher design a fading field?
Date: Sun, 18 Jun 2000 09:11:22 -0600
In article <[EMAIL PROTECTED]>, Benjamin Goldberg
<[EMAIL PROTECTED]> wrote:
> How much does the problem change, if we consider English as a
> ciphertext, and 'knowledge' or 'understanding' as it's corresponding
> plaintext?
>
> You string of letters is an encoding of English text which is in turn
> an encoding of knowledge; To determine if we have a correct decryption
> of ciphertext-string into english we can test to see if there is a
> valid decryption of the possible-english-string into knowledge.
>
Consider equations or source compared with and English version of the same
idea. We might as well ask whether such, as expressions in a language,
can be identified. To verify them as true would require knowing if they
are. So, can a Turing machine identify its own source code as accurate?
--
Some Turkeys can fly, for short distances. If you are to depend on
birds for communication, if it's with turkeys, consider the
discussions that might occur while feasting on one.
------------------------------
Subject: Re: XOR versur MOD
From: Simon Johnson <[EMAIL PROTECTED]>
Date: Sun, 18 Jun 2000 08:49:31 -0700
Security wise there is no difference.
It has been pointed out that XOR is the addition of bits at the
same level of significance mod 2 anyway, it must therefore be of
equal security to addition mod n. However XOR is self inverse,
so is simpler to use.
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
Subject: Re: Extending LFSR......
From: tomstd <[EMAIL PROTECTED]>
Date: Sun, 18 Jun 2000 08:52:27 -0700
Simon Johnson <[EMAIL PROTECTED]> wrote:
>well, this has all gone too mathematical for me :)
>But would it work to simple use primes as the powers above mod
2?
>
Well I don't see why you couldn't do it, but the construction
would work and look a bit differently. Mathematically it's the
same thing.
However 2 was chosen as the prime for many reasons including
speed and simplicity ..
Tom
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
Subject: Re: LSFR
From: Simon Johnson <[EMAIL PROTECTED]>
Date: Sun, 18 Jun 2000 09:08:23 -0700
Sorry i wasn't thinking..........
The above name is actually the name of a brand of clothing over
here, that's my excuse for getting confused :p.
I thought *LFSR's* would be suspetible to known plain-text
attack, but i thought i was wrong. Thanxs
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Crossposted-To: sci.math
Subject: Re: AWFUL PUN (was: Why the golden ratio?)
Date: Sun, 18 Jun 2000 09:20:06 -0600
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (John Savard) wrote:
> Nobody commented on this awful pun? (As the mathematician in question
> is deceased, I suppose he can't do anything but rest on his laurels.)
>
Are we to curry f(l)ave(/o)r with such an observation?
--
Some Turkeys can fly, for short distances. If you are to depend on
birds for communication, if it's with turkeys, consider the
discussions that might occur while feasting on one.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: MD5 Expansion
Date: Sun, 18 Jun 2000 16:14:39 GMT
In article <[EMAIL PROTECTED]>,
tomstd <[EMAIL PROTECTED]> wrote:
> >Sorry, my news server sucks, so I'm using Deja.
> >Anyway, Your logic evades me. Just because we can
> >find 2 messages that have the same MD5 hash
> >doesn't mean those two messages, run through the
> >linear function, will have the same 2nd hash!
> >That is where I see the security of using 2
> >hashes: Even when a collision is found in MD5, it
> >will rarely have a collision in the 2nd hash
> >because one bit change in the message will
> >(supposed to) change on average half the bits of
> >the hash. The attacker is back to searching...
> >
>
> No you missed it. You said you wanted to calculate one hash,
> then perform some permutation of the (presumably) hash and make
> another hash of it. This looks like
>
> A = H(m)
> B = H(L(A))
>
> If for two messages the A values are equal the B value must be
> equal as well. Even if you did
>
> A = H(m)
> B = H(L(A) || m)
>
> I can break it faster then bruteforce and the bday paradox.
>
> It's not a good idea.
>
> Tom
>
> Got questions? Get answers over the phone at Keen.com.
> Up to 100 minutes free!
> http://www.keen.com
>
>
I little bit of miscommunication here. I meant a linear transform of
the message, not the hash, so it looks something like this:
A = H(m)
B = H(L(m))
Final hash = AB
Are you saying this is not secure as well? I'm interested, if it isn't
secure, how one might break it. Just from the outside (amateur) view,
it seems as though L(m) could be something as simple as flipping the
first bit of the message and this would still be effective because the
avalanche effect of the hash would amplify that difference tremendously.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Mack)
Subject: Re: XOR versur MOD
Date: 18 Jun 2000 16:20:43 GMT
Simon Johnson wrote:
>Security wise there is no difference.
>
>It has been pointed out that XOR is the addition of bits at the
>same level of significance mod 2 anyway, it must therefore be of
>equal security to addition mod n. However XOR is self inverse,
>so is simpler to use.
>
>Got questions? Get answers over the phone at Keen.com.
>Up to 100 minutes free!
>http://www.keen.com
>
>
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
modulo word size than with XOR (haven't seen an
analysis just a gut feeling). The main difference
between the two is at the hardware level.
XOR is easier to implement.
Mack
Remove njunk123 from name to reply by e-mail
------------------------------
Subject: Re: MD5 Expansion
From: tomstd <[EMAIL PROTECTED]>
Date: Sun, 18 Jun 2000 09:29:14 -0700
[EMAIL PROTECTED] wrote:
>In article <[EMAIL PROTECTED]>,
> tomstd <[EMAIL PROTECTED]> wrote:
>> >Sorry, my news server sucks, so I'm using Deja.
>> >Anyway, Your logic evades me. Just because we can
>> >find 2 messages that have the same MD5 hash
>> >doesn't mean those two messages, run through the
>> >linear function, will have the same 2nd hash!
>> >That is where I see the security of using 2
>> >hashes: Even when a collision is found in MD5, it
>> >will rarely have a collision in the 2nd hash
>> >because one bit change in the message will
>> >(supposed to) change on average half the bits of
>> >the hash. The attacker is back to searching...
>> >
>>
>> No you missed it. You said you wanted to calculate one hash,
>> then perform some permutation of the (presumably) hash and
make
>> another hash of it. This looks like
>>
>> A = H(m)
>> B = H(L(A))
>>
>> If for two messages the A values are equal the B value must be
>> equal as well. Even if you did
>>
>> A = H(m)
>> B = H(L(A) || m)
>>
>> I can break it faster then bruteforce and the bday paradox.
>>
>> It's not a good idea.
>>
>> Tom
>>
>> Got questions? Get answers over the phone at Keen.com.
>> Up to 100 minutes free!
>> http://www.keen.com
>>
>>
>
>I little bit of miscommunication here. I meant a linear
transform of
>the message, not the hash, so it looks something like this:
>
>A = H(m)
>B = H(L(m))
>
>Final hash = AB
>
>Are you saying this is not secure as well? I'm interested, if
it isn't
>secure, how one might break it. Just from the outside (amateur)
view,
>it seems as though L(m) could be something as simple as
flipping the
>first bit of the message and this would still be effective
because the
>avalanche effect of the hash would amplify that difference
tremendously.
Well we can find collisions in A such that
A = H(m) = H(m') for m != m'
Then we just need to find collision in B such that
B = H(L(A) || m) == H(L(A) || M')
The first has a probability of 2^-64 of happening before the
bday threshold, the second has an equal prob... together it is
2^-65... that's if I get this right, ... err.. I am tired...
Tom
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: LSFR
Date: Sun, 18 Jun 2000 09:22:24 -0700
Simon Johnson <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Looking at a basic LSFR, they don't look all too secure. The
> reason i say this is the whole key is spat out for the first n
> clocks, where n is the size in bits of the Register?
>
> Why is this secure?
They aren't, by themselves. Beyond the obvious weakness you found, given n
arbitrary outputs, you have a good chance at being able to reconstruct the
output (depending on exactly which bits you see -- a few spares will make
that an almost certainty). In fact, if you known n linearly independent
linear equations on the outputs, you have a good chance at being able to
reconstruct the output.
The reasons they tend to be favored:
- They're fast and easy in hardare - O(n) transistors and O(1) time per
output.
- They have a long period (2**n-1 if you chose a primitive polynomial), and
LFSRs of different lengths have relatively prime periods, so the periods
multiply if the LFSRs are clocked at the same rate
- They have great short term randomness properties -- for any m <= n, all
possible m-bit outputs are pretty close to equiprobable. The n consecutive
0's is the only counterexample to that
Of course, they need additional post-processing logic to prevent the
attacker from seeing LFSR output bits in the clear (or, if they do see them
in the clear, they don't know the stepping relationship between outputs).
--
poncho
------------------------------
From: M Joonas Pihlaja <[EMAIL PROTECTED]>
Subject: Q: Equally like bit-flips in a Gray code?
Date: Sun, 18 Jun 2000 19:48:55 +0300
I hope this is the appropriate forum for this type of question.
Hi,
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. That changes
the lower k bits before it gets to bit k.
I need to uniformly sample the key space of a cipher and was
going to use a Sobolev sequence, but noticed that a Gray code
would allow for some optimisations.
Regards,
Joonas Pihlaja
------------------------------
From: Rickman <[EMAIL PROTECTED]>
Crossposted-To: comp.compression
Subject: Re: Small compression/encryption problem
Date: Sun, 18 Jun 2000 13:28:35 -0400
What you suggest could do the job well. But I can give you what should
be a simpler approach. Take your input data (uncompressed text string of
any form) and compress it by any of the conventional and redily
available means. PKZIP will do nicely. Generate a bit pattern using a
LFSR or other simple pseudo random number generator. XOR the compressed
data with the bit pattern. This is your compressed, encrypted data. You
may need to group it into 6 bit characters which are mapped to 64
printable ascii characters. I would bet that with a little searching on
the web for the random bit stream generator, you could reduce your
programming effort to almost nothing.
This may not provide NSA level security, but it will be more than useful
enough for your application and you don't need to do a lot of coding.
Richard John Cavell wrote:
>
> Hi all,
>
> The task is this:
>
> A set of data needs to be encoded and transferred in a nonsecure manner to
> an operator, who will type the encrypted data into a computer program
> manually. The operator (who has no particular skill in programming) must
> be unable to easily decipher what the data is. Errors in
> typing/transferring the data must be made impossible or very unlikely.
>
> The data (which is actually a multiple choice exam):
>
> A twenty-character alphanumeric string, which may contain punctuation.
> Alpha characters are far more likely.
>
> Either twenty or forty values of 1, 2, 3, 4. The value 4 is significantly
> less likely to appear than any of the first 3.
>
> My solution:
>
> Encode the string by mapping all the available alphanumeric characters
> against random others, then exchanging, rotating the key by one for each
> successive character.
>
> Encode each answer as a 2-bit value. Squash them together and break the
> resulting code up into base-32 values. Encode the values as alphanumeric
> (36 possible characters, so leave 0/O and 1/I out of the possbilities).
>
> Lastly, a simple checksum of all the data encoded as 2
> hexadecimal characters.
>
> Does anyone have a better idea?
>
> --------------
> Richard Cavell
> Melbourne University Medical Student
> Debater, Chess Player, etc.
> - [EMAIL PROTECTED]
>
> Newsgroups - Please copy your replies to me via email. (Server problems).
--
Rick Collins
[EMAIL PROTECTED]
Ignore the reply address. To email me use the above address with the XY
removed.
Arius - A Signal Processing Solutions Company
Specializing in DSP and FPGA design
Arius
4 King Ave
Frederick, MD 21701-3110
301-682-7772 Voice
301-682-7666 FAX
Internet URL http://www.arius.com
------------------------------
From: "John A. Malley" <[EMAIL PROTECTED]>
Subject: Re: Cipher design a fading field?
Date: Sun, 18 Jun 2000 10:30:08 -0700
wtshaw wrote:
> Consider equations or source compared with and English version of the same
> idea. We might as well ask whether such, as expressions in a language,
> can be identified. To verify them as true would require knowing if they
> are. So, can a Turing machine identify its own source code as accurate?
> --
Rice's Theorem in computability theory tell us that testing any property
of the languages recognized by Turing Machines is an undecidable problem
- there is no algorithm that can decide if the language does/does not
posses the property.
No Turing Machine can decide if a given description of a TM (its source
code) does or does not satisfy some property that should be there if it
is accurate (however we define accurate, like "bug free" so it correctly
implements the behavior desired - Automated verification. Can the
verifier verify itself? No, this problem reduces to the halting
problem.)
John A. Malley
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED]
Crossposted-To:
alt.privacy,alt.privacy.anon-server,alt.security.pgp,comp.security.firewalls
Subject: Re: Evidence Eliminator Dis-Information Center
Reply-To: [EMAIL PROTECTED]
Date: Sun, 18 Jun 2000 17:49:34 GMT
On Fri, 16 Jun 2000 16:40:23 -0700, tomstd <[EMAIL PROTECTED]>
wrote:
>[EMAIL PROTECTED] wrote:
>> First excuse me for posting on top.
>>
>> Let me just say that once in a while a program comes
>along that can
>>under the "right" circumstances make you HUMBLE like a newbie ,
>and after
>>reading this thread I downloaded it and ran it, while setting
>it up I changed
>>the DEFAULT of Netscape to my D drive and along the way I F**d
>up BIG time I
>>left a entry pointing to the root of d:\netscape and needless
>to say I had
>>NOT backed up in a BIG while ALL MY FAULT of course BUT I
>almost cried I
>>lost my Bookmarks and mail that was saved with passwords for
>programs I've
>>bought for the last 1 1/2 year I'm a humble man
>again........now to email
>>companies to get those passwords again!..... I just backed up
>my documents
>>recently and forgot once again to back up Netscape! ALL THE
>BACKUPS I DO AT
>>WORK EVERY DAY .........................it's a bitch getting
>old!!!!!
>>
>> It's the BEST program I've used in a while it really
>wipes good.
>>
>>be careful and as the old adage goes back up before using.......
>>
>
>Pardon me for saying this, but you are seriously in need of help.
>
>I can't phantom a reason why any compotent person would go about
>saying "I feel like wiping my hard disk today". Maybe you are
>just playing too much with your computer. I mean I could goto
>dos and type "FORMAT C:\" just to find out what it does... Or I
>Could not.
>
>Seek help my friend.
>
>And to the other paranoids who think EE will save their day...
>NOBODY CARES. I personally don't care what some faceless drone
>has on their HD much more then I care to see fly mate.
>
>If you have naughty files be smart and keep them on a floppy or
>don't run FTP/HTTP daemons...
>
>Tom
>
I *do* play with my machines a lot. it's always been a hobbies as for
naughty, no, I don't get the movie mp3 over the net, when I can buy a dvd and
enjoy it so much more.
------------------------------
** 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
******************************
