Cryptography-Digest Digest #603, Volume #12 Sun, 3 Sep 00 15:13:01 EDT
Contents:
Re: New cryption method... ("Stephan Leclercq")
Re: Feistel Cipher (Mark Wooding)
Re: DES weak keys in 3DES ("Scott Fluhrer")
Re: Extending RC4 to 16 bits ("Scott Fluhrer")
Re: Transposition Problem ("Douglas A. Gwyn")
Re: New cryption method... (PROdotes)
Re: e-cash protocol concept, comments wanted ("Tor Rustad")
Re: 96-bit LFSR needed (Mack)
Re: New cryption method... (PROdotes)
Re: New Site, Purple/Enigma/Sigaba/Russia Emulators (UBCHI2)
Re: New cryption method... ("Stephan Leclercq")
Vic Cipher must have been a plant (UBCHI2)
Re: New cryption method... (PROdotes)
----------------------------------------------------------------------------
From: "Stephan Leclercq" <[EMAIL PROTECTED]>
Subject: Re: New cryption method...
Date: Sun, 03 Sep 2000 15:14:43 GMT
PROdotes <[EMAIL PROTECTED]> a écrit dans le message :
[EMAIL PROTECTED]
Step 2
> It the same as if you would take the printout of the result, scan it and
> the process it as a BW picture.
Doesn't look like an algorithm... Let me try to guess what you mean by
that...
Consider now the message as a stream of pixels, either black or white, each
pixel being one bit of the message. Arrange the pixels in rows so the
message now looks like a picture.
I don't understand why you use such a complicated view of the data. It is
totally equivalent to seing the message as an array of bits ...
Step 3
> B->W, W->B
Do you mean :
1) Generate a random number
2) Use this number as an index in the array of bits
3) Invert the given bit (0 becomes 1, 1 becomes 0)
4) Repeat steps 2-3 a fairly big number of times
?
You have to choose the number of iterations very carefully, so each bit in
the message has exactly 50% chance of being inverted (or an odd number of
times), and 50% chance of not being inverted (or inverted an even number of
times).
Otherwise, the attacker could use this bias. If a bit only has 40% chance of
being inverted in the process, then the attacker knows a "1" bit in the
ciphertext represents a "1" in the plaintext with 60% probability, and a "0"
with 40% probability.
Steps 4/5
> Well, I swap the rows and colums of the picture... so I swap the bits,
> not the bytes anymore...
Yes, but why not swap individual bits instead of whole rows/columns ? Same
in step 1, why not swap individual bits instead of full bytes ?
Some conclusions so far :
There are two (for me) obvious attacks on this encryption :
a) key ranges from 0 to 999.999, that is at most "20 bits strong". Brute
force will almost certainly break this in a few minutes. Oops, I meant
seconds.
b) A bit in the ciphertext depends on one and only one bit in the cleartext.
So, by changing a single bit in the cleartext message, exactly one bit will
change in the encrypted message. The attacker might use this to gain
knowledge of the internal state of the PRNG. While I'm totally unable to do
this myself, others are smart enough; Dr. Shamir, do you read this thread
:-) ?
--
Stephan Leclercq - sauron <at> minasmorgul <dot> com
www <dot> minasmorgul <dot> com
S'il n'y a pas de solution, c'est qu'il n'y a pas de problème -- proverbe
Shadok
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Feistel Cipher
Date: 3 Sep 2000 15:25:28 GMT
Mark Wooding <[EMAIL PROTECTED]> wrote:
> Secondly, there's a differential attack which requires about 2^{-25}
Duh. 2^{25}.
> chosen plaintext pairs (about 50 million chosen plaintexts). That's
> a lot.
Duh. 67 million. It's still not a lot.
-- [mdw]
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: DES weak keys in 3DES
Date: Sun, 3 Sep 2000 08:30:47 -0700
Mark Wooding <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Gisle Sælensminde <[EMAIL PROTECTED]> wrote:
>
> > DES have a number of weak and semi-weak keys, but in 3DES
> > (DES-EDE3) tree independent keys is used. How is the securiy if
> > one (or two) of these keys are weak. Shoud the key be avoided if
> > any of the DES-keys are weak, or must as least two of them be
> > weak before it becomes a problem.
>
> I believe that rejecting a single weak key is not beneficial. To notice
> the weak key being used, you'd have to successfully guess the other two
> keys, which is harder than attacking the full triple encryption (using,
> e.g., meet-in-the-middle or Lucks' probabilistic attack).
>
> I'd reject two weak keys out of three, though, if I were the sort of
> person who rejects weak keys.
Actually, if you were worried about 3DES "weak keys", it'd worry first about
keys where either the first and second DES keys were the same, or the second
and third keys where the same. This has approximately as much likelihood of
happening by random chance as picking one of the three keys to be a DES weak
key, however, it reduces the cipher to DES, which would appear to be a more
severe weakness than using even two weak keys in 3DES...
--
poncho
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Extending RC4 to 16 bits
Date: Sun, 3 Sep 2000 08:45:03 -0700
Guy Macon <[EMAIL PROTECTED]> wrote in message
news:8os40u$[EMAIL PROTECTED]...
> Scott Fluhrer wrote:
>
> >- Ignoring that, the idea of generalizing RC4 to include other bit sizes
has
> >already appeared in the literature. It may be a bit too late to try to
try
> >to place it under the quite restrictive Gnu copyright...
>
> Did said literature conclude anything about the effect on cryptographic
> strength?
Well, just about any attack in the literature that considers different RC4
sizes gets much harder as the size increases. This includes:
- Mister and Tavares' Cycle Analysis (SAC 98)
- Mister and Tavares' Tracking Analysis (SAC 98)
- Jenkin's Gap Length observation (quoted in SAC 98)
- Jovan Golic's linear distinguisher (Eurocrypt 97)
- My digraph distinguisher (FSE 2000)
Now, as for how much stronger RC4 gets as you get beyond sizes of 8 bits,
well, no one seems to studied that all that closely. After all, 8 bit RC4
itself is quite a handfull, and until we have a fruitful attack against
that, it doesn't make much sense to start attacking something that appears
to be considerably harder. However, every attack that we know about that
fails against RC4 would fail even more miserably against 16 bit RC4.
--
poncho
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Transposition Problem
Date: Sun, 03 Sep 2000 12:15:53 -0400
Future Beacon wrote:
> If two bits are used to select a number between 1 and 4 and
> then one bit is used to select 0 or 2 and these two numbers
> are added, the selections will be between 1 and 6, but the
> possible selections are not equally likely.
Of course, just as the sum of two dice is not uniformly
distributed.
> Also I am suspicious of a bias in the event that three bits
> are used to select 1 of 8 and two outcomes are simply ignored.
No, that method is obviously unbiased.
------------------------------
From: PROdotes <[EMAIL PROTECTED]>
Subject: Re: New cryption method...
Date: Sun, 3 Sep 2000 18:37:21 -0700
***Step 2
> > It the same as if you would take the printout of the result, scan it and
> > the process it as a BW picture.
> Doesn't look like an algorithm... Let me try to guess what you mean by that...
> Consider now the message as a stream of pixels, either black or white, each
> pixel being one bit of the message. Arrange the pixels in rows so the
> message now looks like a picture.
> I don't understand why you use such a complicated view of the data. It is
> totally equivalent to seing the message as an array of bits ...
If you convert the text in bits a -> 01000001 and use this as the data to
be crypted then some mathematical algorithms could "very easy" break the
code. When converting the byet into a 16 X 8 picture then you can't
"calculate" it out and have a greater variety of combinations to crypt.
***Step 3
> Do you mean :
> 1) Generate a random number
> 2) Use this number as an index in the array of bits
> 3) Invert the given bit (0 becomes 1, 1 becomes 0)
> 4) Repeat steps 2-3 a fairly big number of times
> ?
Yep...
> You have to choose the number of iterations very carefully, so each bit in
> the message has exactly 50% chance of being inverted (or an odd number of
> times), and 50% chance of not being inverted (or inverted an even number of
> times).
If the principles of the chaos theory are correct... the chance of an
random chosen number form 0 to 0.999 step .001 has an 50-50 chance to be
< .5
> Otherwise, the attacker could use this bias. If a bit only has 40% chance of
> being inverted in the process, then the attacker knows a "1" bit in the
> ciphertext represents a "1" in the plaintext with 60% probability, and a "0"
> with 40% probability.
As said... it depends on the PRNG...
***Steps 4/5
> Well, I swap the rows and colums of the picture... so I swap the bits,
> not the bytes anymore...
> Yes, but why not swap individual bits instead of whole rows/columns ? Same
> in step 1, why not swap individual bits instead of full bytes ?
Hey... I neaded to shorten it for personal use... it's better to use 2
arrays of "n" then an "n*n" array...
> Some conclusions so far :
> There are two (for me) obvious attacks on this encryption :
> a) key ranges from 0 to 999.999, that is at most "20 bits strong". Brute
> force will almost certainly break this in a few minutes. Oops, I meant
> seconds.
OK... but as said many times before... so far the algorithm is for
personal use... it isn't an big problem to make the key bigger... It just
makes the algorithm "a bit" slower.
> b) A bit in the ciphertext depends on one and only one bit in the cleartext.
> So, by changing a single bit in the cleartext message, exactly one bit will
> change in the encrypted message. The attacker might use this to gain
> knowledge of the internal state of the PRNG. While I'm totally unable to do
> this myself, others are smart enough; Dr. Shamir, do you read this thread
> :-) ?
Well... I wrote in this post before... 1 byte depends on 128 bits...
However, I'll make an program later on today to test this theory...
THNX
------------------------------
From: "Tor Rustad" <[EMAIL PROTECTED]>
Crossposted-To: alt.cypherpunks,alt.cypherpunks.technical
Subject: Re: e-cash protocol concept, comments wanted
Date: Sun, 3 Sep 2000 18:47:35 +0200
"Julian Morrison" <[EMAIL PROTECTED]> wrote in message
> If you are knowledgeable about ecash, please check out my idea for a
> signature-based ecash protocol at
> http://fling.sourceforge.net/concepts.html
>
> Are there any major design bugs?
> Are there major improvements you could suggest?
> How does this compare to other ecash proposals you know of?
>
> Thanks in advance for any comments.
I have the same comment that signed coins is not useful or practical, your purse
has a electronic value in a currency (or multiple currencies), the bank only
need to sign this value.
1,2) Loading the purse with electronic value.
Your description is not detailed on this, it does not look to me that the
security issues of this critical point, is _not_ addressed at all. Sorry.
3) Coin storage.
No security!
No trace!
Totally unacceptable for most banks.
4) Spending e-cash.
Totally flawed...
Which bank will give 'transaction reciept' (whatever that is) on the basis of
hashes?
5) Settlement.
Where is the security?
Designing a new electronic payment protocol is very complicated, first of all
its not a one-man job. Flawed protocols on this, sooner or later gets broken,
and when that happends there is a great risk of major losses for the banks. The
national banks also want to have a word about the security on e-cash, in the
future a national economy may collapse if a big e-cash system is broken!
There exists today real life systems on e-cash (i.e. Proton), which are well
designed from a bank and security point of view. There is also on-gong
standardization efforts to produce international e-cash protocol, with multiple
contributing experts. This work is backed by major players in finance community.
Sorry for my negative response.
--
Tor
------------------------------
From: [EMAIL PROTECTED] (Mack)
Subject: Re: 96-bit LFSR needed
Date: 03 Sep 2000 17:03:40 GMT
>"Mack" <[EMAIL PROTECTED]> wrote:
>> TT wrote:
>
>> >I looked at Scott's program. [...]
>> >
>> >It seemed to me that the time taken to factor the
>> >modulus was the primary factor limiting performance.
>>
>> Not really it takes a shortcut. It has a table of
>> factors. Since it only handles numbers up to
>> 2^1024 he only has to include the factorization of
>> 1020 numbers.
>
>"He"? The version currently on Scott's site reads:
The version I have does not have an attribution of
authorship. I thought it came from Scott Nelsons
site. I may be wrong.
This is the comments about the factorization part
Factoring large numbers isn't really an easy problem, but
fortunately the special case of 2**n-1 is easier. Numbers
of this form are called Mersene numbers, and have recieved an
intense amount of interest lately.
I have thus been able to find or calculate (using the free factor
program that comes with the MIRACL package) the complete factorization
of the first 512 mersene numbers. These factorizations are in the file
mnumbers.h
>
>/*
> *
> * Find all the factors of 2^order-1 by brute force division.
> * This divides by all the odd numbers less than the square root,
> * [...]
> * Not the fastest way, but one of the smallest. :)
> *
> */
>
>Of course, a table of factors would certainly make good sense.
>
>I only meant that factorising was the bottleneck in Scott's
>implementation - not that it was necessarily always going
>to be the slow spot.
It could have been. Sounds like the original version
used a seive. The version I have has a table up to M512
and then uses the fact certain mersene numbers are prime.
It does not attempt to factor numbers above M512.
Although in the special case of where we have a mersene
number that has an exponent is not prime, factoring should
be fairly easy.
>--
>__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
> |im |yler The Mandala Centre http://mandala.co.uk/ Namaste.
>
Mack
Remove njunk123 from name to reply by e-mail
------------------------------
From: PROdotes <[EMAIL PROTECTED]>
Subject: Re: New cryption method...
Date: Sun, 3 Sep 2000 19:35:23 -0700
Hm... I worked a bit on the algorithm and tested it... in the case
mentioned an divide and conquer attack could be very much of use...
------------------------------
From: [EMAIL PROTECTED] (UBCHI2)
Subject: Re: New Site, Purple/Enigma/Sigaba/Russia Emulators
Date: 03 Sep 2000 17:50:53 GMT
If you specifically used the Sigaba emulator (Strongest One) to encrypt a
message, then with a bit of known plaintext it would be possible to get through
in time. The cracker would have to sub in letters a-z, offsets 1-10 and rotors
I-X and wait until the decryption of the known word came out.
By mixing the algorithms in a way unknown to the cracker and with protocols to
avoid leaving cribs, it would not be feasible to crack a message.
Best bet would be to also alter the wiring of the rotors, reflectors so those
became unknown as well. The canned emulators don't allow rewiring. They only
allow changes in initial settings. That is a great vulnerability.
------------------------------
From: "Stephan Leclercq" <[EMAIL PROTECTED]>
Subject: Re: New cryption method...
Date: Sun, 03 Sep 2000 17:57:26 GMT
PROdotes <[EMAIL PROTECTED]> a écrit dans le message :
[EMAIL PROTECTED]
>
> ***Step 2
>
>
> If you convert the text in bits a -> 01000001 and use this as the data to
> be crypted then some mathematical algorithms could "very easy" break the
> code. When converting the byet into a 16 X 8 picture then you can't
> "calculate" it out and have a greater variety of combinations to crypt.
01000001 is A, not a...
Homophonic encryption is OK as long as each cleartext symbol can be
converted to several different ciphertexts. If every A in your text is
replaced by
00011000
00100100
01000010
10000001
11111111
10000001
10000001
10000001
then you give the attacker many more information than simply keeping the
original 01000001, because of the 2^(16*8) patterns you generate, only 128
or 256 are valid, and s/he can easily use that information.
>
> ***Step 3
>
> > Do you mean :
>
> > 1) Generate a random number
> > 2) Use this number as an index in the array of bits
> > 3) Invert the given bit (0 becomes 1, 1 becomes 0)
> > 4) Repeat steps 2-3 a fairly big number of times
> > ?
>
> Yep...
>
> > You have to choose the number of iterations very carefully, so each bit
in
> > the message has exactly 50% chance of being inverted (or an odd number
of
> > times), and 50% chance of not being inverted (or inverted an even number
of
> > times).
>
> If the principles of the chaos theory are correct... the chance of an
> random chosen number form 0 to 0.999 step .001 has an 50-50 chance to be
> < .5
No.
1) The theory of chaos *is* correct AFAIK
2) The theory of chaos simply says that the future history of a system
governed even by simple rules can be dramatically affected by arbitrarily
small changes in the initial conditions. It has nothing to do with
probability.
3) The probability you give is only valid for certain classes of random
number generators. Most generators used for simulation do not obey this
rule.
4) Either you said YEP to my algorithm while you use another, or I didn't
understand your point.
--
Stephan Leclercq - sauron <at> minasmorgul <dot> com
www <dot> minasmorgul <dot> com
S'il n'y a pas de solution, c'est qu'il n'y a pas de problème -- proverbe
Shadok
------------------------------
From: [EMAIL PROTECTED] (UBCHI2)
Subject: Vic Cipher must have been a plant
Date: 03 Sep 2000 18:01:11 GMT
The Vic Cipher sounds like a plot by the Soviets to waste US code breaking
time. Why would you require an agent to memorize a code of such complexity
that errors are extremely likely. The issuance of one time pads would have
greatly simplified the creation and accuracy of messages.
Some might say that the Vic Cipher avoids the possibility of the capture of the
one time pad digits by hostile authorities. That explanation does not work
however. If the Soviets were willing to risk the deposit of documents in dead
drops, then surely they were comfortable with the idea of leaving coded papers
in secure locations.
Why would you deliberately hide code material in a piece of money (a hollow
nickel) That is something that any passerby would want to pick up and take. A
useless thing like a candy wrapper would have been used.
The question is whether the Vic Cipher was ever found on another Soviet agent
when one time pads had been the standard issue to others that are in the
literature.
------------------------------
From: PROdotes <[EMAIL PROTECTED]>
Subject: Re: New cryption method...
Date: Sun, 3 Sep 2000 20:36:49 -0700
> 3) The probability you give is only valid for certain classes of random
> number generators. Most generators used for simulation do not obey this
> rule.
So the problem is the PRNG...
The answer to this problem should be an "selfcoding" and flexible PRNG...
the easyer way would be to use the cleartext for keygeneration... but in
that case the key could not be regenerated without hurting the security
of the algorithm...
Lets say the "l" looks like this
0110
0010
0010
1111
It could be easily cripted into
0010
1001
1100
0110
But if the attacker changes the "l" into an "I"
0111
0010
0010
1111
The output could be:
0010
1101
1100
0110
Now the attacker would know where the lines with the changes have
traveled...
The problem is always the same ... for the same startig conditions the
ending conditions are the same...
------------------------------
** 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
******************************
