Cryptography-Digest Digest #335, Volume #14 Fri, 11 May 01 12:13:01 EDT
Contents:
Re: RC4 (jlcooke)
Re: Bleaming strock cipher (John Myre)
Re: RC4 ("Tom St Denis")
Re: SAC'01 wannabe paper (John Myre)
Re: Cryptanalysis Question: Determing The Algorithm? ("Tom St Denis")
Re: SAC'01 wannabe paper ("Tom St Denis")
Re: RSA signing with public e = 3 (jlcooke)
Re: Horst Feistel ("Douglas A. Gwyn")
Re: Security with provable strength. (John Myre)
Re: DES-CBC without Crypt::CBC (jlcooke)
Re: SAC'01 wannabe paper (jlcooke)
Re: Are low exponents a problem with RSA? (Stefek Zaba)
Re: SAC'01 wannabe paper ("Tom St Denis")
good x86 coders (help please) ("Tom St Denis")
Re: Micali-Schnorr pseudorandom bit generator (Charles Blair)
Re: Looking for a simple code wheel to print out for kids ("Robert Reynard")
NSA "Headline Puzzle" confusion ... (Mitchell Morris)
Re: Micali-Schnorr pseudorandom bit generator ("Tom St Denis")
Re: Quasi Functions, a way to design Maximum Secure Cipher (Mark Wooding)
----------------------------------------------------------------------------
From: jlcooke <[EMAIL PROTECTED]>
Subject: Re: RC4
Date: 11 May 2001 14:18:31 GMT
Isn't RC4 a trade secret of RSA Labs? RC4-compat was reverse engineered
or something. All I know is you can't use or name an algorithm RC4
unless RSA labs made it. But you can use a reverse engineered
RC4-comapt just fine.
Why oh why does RSA (labs) complicate my life so.
JLC
Tom St Denis wrote:
>
> "William" <[EMAIL PROTECTED]> wrote in message
> news:9dendq$7fs$[EMAIL PROTECTED]...
> > Hi all,
> >
> > I am doing RC4 course project but have not yet found design and analysis
> > papers or website about RC4. Please anyone suggest some websites and
> papers.
> > Thanks a lot,
>
> Look up a dude named "Scott Fluhrer".
>
> Tom
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: Bleaming strock cipher
Date: Fri, 11 May 2001 08:19:26 -0600
Paul Pires wrote:
<snip>
> ... diddle a few bits in each block according to a coin flip until the
> parity from block to block spells out, "You Loose".
<snip>
"and I'm Tight".
JM, the ocunter
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: RC4
Date: Fri, 11 May 2001 14:28:22 GMT
"jlcooke" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Isn't RC4 a trade secret of RSA Labs? RC4-compat was reverse engineered
> or something. All I know is you can't use or name an algorithm RC4
> unless RSA labs made it. But you can use a reverse engineered
> RC4-comapt just fine.
>
> Why oh why does RSA (labs) complicate my life so.
I seriously doubt RSA goes after RC4 users any more. Unless you had
something saying "our product is so secure because we use RSA RC4
technology". Since that makes RSA look bad if your product sucks (and they
at least want money in that case).
If you simply say "I use RC4" I doubt they will go after you.
If you use RC5/RC6 on the other hand... They will chase you to the end of
the earth even if you don't live in the US (which is the only place their
patent is valid).
Turns out who cares about RC5/RC6 since better ciphers exist (Rijndael,
Twofish, etc, my TC15 (hehehehe)).
Tom
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: SAC'01 wannabe paper
Date: Fri, 11 May 2001 08:24:59 -0600
Tom St Denis wrote:
>
> "Benjamin Goldberg" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
<snip>
> > Conditional assignments can be done much faster than conditional jumps,
> > and they take constant time, which is another benefit.
<snip>
> Since MDFC was designed for embedded platforms like the 8051 conditional
> assignments don't exist. One must emulate them :-)
<snip>
On the other hand, the 8051 doesn't suffer much from
branch prediction failures... :)
JM
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Cryptanalysis Question: Determing The Algorithm?
Date: Fri, 11 May 2001 14:32:49 GMT
"Bo Dömstedt" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Even though this is sci.crypt, let's try a systematic approach:
>
> Can we prevent the cryptanalyst from learning which
> cipher algorithm that we use?
Typically that's a bad way to look at crypto.
> If we do, how much can we gain?
>
> First, we need a sufficiently large algorithm space (to prevent serial
> or parallel search as discussed above). We have seen (indications on)
> that this is no problem, but I feel that most readers don't think that
> this is obvious at all. This is due to that most conventional block
> ciphers are iterated substitution/transposition ciphers, and what
> else can possibly exist??
FROG is a good example of a bad design. It uses a "polymorphic" structure
that was easily defeated simply because too many keys make weak ciphers.
> Second we must prevent the cryptanalyst from learning which algorithm
> we are using. We may use physical protection means, and zero out
> the algorithm, when a physical attack is detected on a cipher machine.
> (This function is advantageous anyway, and is required in FIPS 140-2
> level 3-4 compliant implementations).
>
<snip>
Obviously you haven't given this some thought. You're saying let's not use
a fixed known algorithm X to encrypt data. Instead let's use algorithm Y
that makes other algorithms then use those.
The problem is now algorithm Y is X.
Another problem is that typically we will have a Y that can make bad
ciphers.
Take my new TC15 (toy cipher, please dear god someone please comment about
it! I'm dying to hear comments). I picked the rotations in the LT in a
half-baked method. Turns out there are better rotation counts I could have
used. Let's suppose algorithm Y makes a family of TC15 where the rotation
is key depenedent (but fixed over all rounds). A vast amount of the ciphers
made by Y will be weak (i.e rotation counts that lead to a slow avalanche if
any at all).
The best (so far) approach is to put the security in the key and to design
the cipher as tightly as possible.
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: SAC'01 wannabe paper
Date: Fri, 11 May 2001 14:34:02 GMT
"John Myre" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Tom St Denis wrote:
> >
> > "Benjamin Goldberg" <[EMAIL PROTECTED]> wrote in message
> > news:[EMAIL PROTECTED]...
> <snip>
> > > Conditional assignments can be done much faster than conditional
jumps,
> > > and they take constant time, which is another benefit.
> <snip>
> > Since MDFC was designed for embedded platforms like the 8051 conditional
> > assignments don't exist. One must emulate them :-)
> <snip>
>
> On the other hand, the 8051 doesn't suffer much from
> branch prediction failures... :)
True. In the paper (in case you haven't read it) I suggest doing GF mults
using the shift/xor approach but to avoid simple side-channel attacks we
always load from memory even if we don't use the values.
On a pentium/etc you can just precompute the tables and have them execute in
fixed time :-)
Tom
------------------------------
From: jlcooke <[EMAIL PROTECTED]>
Subject: Re: RSA signing with public e = 3
Date: 11 May 2001 14:43:38 GMT
There are attacks if someone just blindly encrypts something with their
private key. A true signing is:
S = ( HASH(data) ) ^ d MOD K
Otherwise,
S = ( M ^ e MOD N ) ^ d MOD K
can be used to directly find d.
JLC
Peter Kooiman wrote:
>
> Hi,
>
> I have a question inspired by the recent discussion on RSA with public
> exponent 3:
>
> Suppose I receive encrypted and signed messages, my public exponent is 3
> with mod N,
> the other party has public exponent 3, private exp d (obviously not known to
> me) and mod K, so
> plaintext M would give a signed crpyted message ((M ^ 3) mod N) ^ d mod K.
>
> Question: would it be feasable for an intruder to forge a message? Let's
> suppose the message itself
> is in the first X most significant bytes of M (ie reduction mod N
> guaranteed),
> message a lot shorter than the block size and the remaining bytes can be
> filled with any convenient values.
> So in other words, could an intruder construct a message F such that after
> encrypting
> I would have an apparently valid message, that is a message with something
> meaningfull and chosen by the intruder in its MSBs?
>
> Any thoughts?
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Horst Feistel
Date: Fri, 11 May 2001 14:17:39 GMT
Jim Reeds wrote:
> Most Americans pronounce it with the stress on the second
> syllable (fai-STELL), even though in German it's correct to put
> the stress on the first syllable, as Paul indicates.
Jim, it would have never occurred to me to accent the
second syllable.
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: Security with provable strength.
Date: Fri, 11 May 2001 08:44:16 -0600
Mark Wooding wrote:
<snip>
> You end up
> with a square R matrix, which you hope is invertable,
<snip>
In standard matrix computations (floating point), there are
techniques (which I've forgotten) for solving systems of
n+k equations in n unknowns directly, getting useful results
out when the system is not overdetermined. Wouldn't there be
ways for doing the same thing in this setting?
JM
------------------------------
From: jlcooke <[EMAIL PROTECTED]>
Crossposted-To:
alt.comp.perlcgi.freelance,alt.perl,alt.perl.sockets,comp.lang.perl,comp.lang.perl.misc
Subject: Re: DES-CBC without Crypt::CBC
Date: 11 May 2001 14:50:29 GMT
Are you aware that CBC is an mode of operation for DES and not a cipher
per se?
Cipher Block Chaining. It should be part of a good DES impl'n. If not:
CBC = {0,0...};
loop:
M = {M[0]^CBC[0], M[1]^CBC[1], ...};
C = DES(M,KEY);
CBC = C;
So the nth block is dependent on all the previous blocks. My added
suggestion is to encrypt a message M' = {RAND, M[0], M[1], ...}. And
when decrypting, throw away the first block. This will prevent people
from being able to use knowledge of the first block of M as a starting
point for an attack.
JLC
Super-Simon wrote:
>
> Hi all,
>
> I have to encrypt / decrypt strings using DES-CBC. On my hostingserver is
> Crypt::DES installed, but not Crypt::CBC (the only Crypt modules installed
> are DES and Blowfish).
>
> Where can I get a .pl file doing this (without using another Crypt-module
> than Crypt::DES)??????
>
> With kind regards,
>
> Simon
------------------------------
From: jlcooke <[EMAIL PROTECTED]>
Subject: Re: SAC'01 wannabe paper
Date: 11 May 2001 14:59:45 GMT
Try this for no conditions at all:
x &= 1;
x |= x<<1;
x |= x<<2;
x |= x<<4;
x |= x<<8;
x |= x<<16;
x &= p;
y = (y << 1) ^ x;
or better still if you have a 32bit mult,
x = (x&1) * p;
y = (y << 1) ^ x;
or again,
x &= 1;
x = (~x | x) & p;
y = (y << 1) ^ x;
JLC
Benjamin Goldberg wrote:
>
> In the discussion of GF multiplies...
>
> There are such instructions as conditional assign, which could be used
> to replace/avoid conditional jumps. One would use this by replacing
> things like this:
> if( x & 1 )
> y = (y << 1) ^ p;
> else
> y = (y << 1) ^ 0;
> with something like this:
> z = ( x & 1 ) ? p : 0;
> y = ( y << 1 ) ^ z;
>
> When turning this to assembler, the assignment to z would be an
> instruction something like the following:
> condassign $test, $target, $source1, $source2
> Where, if register $test is [==, !=, <, <=, >, >=] zero, then assign
> $source1 to $target, else assign $source2 to target.
>
> Conditional assignments can be done much faster than conditional jumps,
> and they take constant time, which is another benefit.
>
> Since I don't do much asm coding, I don't know for what architectures
> this kind of instruction exists, but I'm fairly sure that there are a
> number of machines which have it.
>
> --
> Shift to the left, shift to the right, mask in, mask out, BYTE, BYTE,
> BYTE !!!
------------------------------
From: [EMAIL PROTECTED] (Stefek Zaba)
Subject: Re: Are low exponents a problem with RSA?
Date: 11 May 2001 14:48:56 GMT
In sci.crypt, DJohn37050 ([EMAIL PROTECTED]) wrote:
> Note that this is not just a theoritical possibility, apparently the Russian
> VERONA transcripts were using a OTP and somehow the OTP was caused to repeat or
> the RNG repeat or something.
Splutter. Cough. Umm, I don't think you've all of the technical details
quite right there, Don...
The technical details are available in handouts at the National Cryptologic
Museuem outside the fence at Fort Meade, in the book "Venona: Decoding
Soviet Espionage in America", John Earl Haynes and Harvey Klehr, Yale Univ.
Press 1999, ISBN 0-300-07771-8, and at a variety of websites, including
http://www.nsa.gov/docs/venona - this one has the text of the handouts
from the Cryptologic Museum referred to above.
The two principal weaknesses according to these sources are (1) a re-use of
the OTP key material, and (2) lack of randomness in the keys themselves,
allegedly because they were generated not by a mechanical or electronic
random process but by typists who were told to "hit those typewriter keys
at random". Maybe it's the second cause that Don was groping towards: humans
aren't good at simulating random processes. Leaving aside the huge earnings
of casinos as a proof point :-), people told to "generate random keystrokes"
will avoid repeats, sequences of "obvious" pattern, will tend however to
alternate between left and right hands, and the like.
The Venona book referred to above claims (at pp.29 - 35) that the Soviets
duplicated keying material around 1942. Rather than double-using whole pads,
they "duplicated individual pages, then shuffled them into different pads".
These pads-with-common-parts were used in identifiably separate cipher systems
- for their trade mission, their diplomatic traffic, the KGB, the GRU, and
the Naval GRU. The Trade system was the first one in which re-use of key
material was spotted (maybe because of a greater volume of traffic and/or
its more ready interceptability), and that gave the cryptanalysts the
confidence that it was worth persevering with the massive (absent programmable
computer support :-) tabulating and analysis effort.
Venona decodes seem to be concentrated on messages sent from 1943 to 1947.
But the plaintext did not all become available in that time; much of the
cryptanalysis occurred in the 1950s. It was complicated by the two-level
cipher system used: plaintext was first translated into number groups using
a "book code" for frequently-occurring words and phrases, and spelling out
rare words letter by letter into digit-strings. (So, a decrypt also required
access to a code book; a damaged, partial copy was acquired by extra-technical
means, covering the 1943-46 period, and this with technical analysis allowed
a pretty thorough reconstruction. A less complete reconstruction was also
achieved for the earlier codebook. But - according to the NSA materials - the
caputured codebook fragments served rather to confirm and supplement existing
analytic work on what the codebooks "must have" contatined, rather than being
the starting-point for rendition into native Russian.) Decoding continued
throughout the 50s and 60s, and with reduced effort (as the subject matter
became less operationally relevant) into the 70s, finishing on 01oct80.
Its product was not made public until 1995.
It's worth noting that the ciphertext, key, and "plaintext" (i.e. the stuff
combined with the key for encrypting and decrypting) were all numeric - no
Cyrillic-versus-Roman stuff going on here!
Cheers, Stefek
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: SAC'01 wannabe paper
Date: Fri, 11 May 2001 15:10:53 GMT
"jlcooke" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Try this for no conditions at all:
>
> x &= 1;
> x |= x<<1;
> x |= x<<2;
> x |= x<<4;
> x |= x<<8;
> x |= x<<16;
> x &= p;
> y = (y << 1) ^ x;
>
> or better still if you have a 32bit mult,
>
> x = (x&1) * p;
> y = (y << 1) ^ x;
>
> or again,
>
> x &= 1;
> x = (~x | x) & p;
> y = (y << 1) ^ x;
So what? What are these suppose to compute? also your knowledge of boolean
logic seems either very little or this is a joke post.
Your first case is not invertable since the lsb of y is lost. (same with the
second case).
Your last case ~x | x is ~0 always so it's not a function of x.
What is this post about anyways? We were discussion zero-time GF mults
(more precisely constant time GF mults).
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: good x86 coders (help please)
Date: Fri, 11 May 2001 15:19:59 GMT
One thing I learned is that there are tons of better coders here than me.
Which is why I want to ask if anyone would be interested in writting up a
short expose of TC15 in assembler optimized for the pentium (i.e basic
pairing and such). It doesn't have to be a complete package, just be able
to encrypt a block (no decryption required) with an expanded key that will
be provided.
I could code my own but the results would not reflect that of top notch
coders. (yes I feel like a hypocrite posting this).
Any takers?
--
Tom St Denis
---
http://tomstdenis.home.dhs.org
------------------------------
Subject: Re: Micali-Schnorr pseudorandom bit generator
From: [EMAIL PROTECTED] (Charles Blair)
Date: Fri, 11 May 2001 15:25:58 GMT
"Tom St Denis" <[EMAIL PROTECTED]> writes:
>"Charles Blair" <[EMAIL PROTECTED]> wrote in message
>news:pnQK6.5666$[EMAIL PROTECTED]...
>> "Tom St Denis" <[EMAIL PROTECTED]> writes:
>>
>>
>> >"Klaus Pommerening" <[EMAIL PROTECTED]> wrote in message
>> >news:9dgh4e$chl$[EMAIL PROTECTED]...
>> >> In <[EMAIL PROTECTED]> Benjamin Goldberg wrote:
>> >> > Also, since the Micali-Schnorr generator seems to be similar in some
>> >> > ways to the Blum-Blum-Schub generator, why not implement that,
>instead?
>> >> > BBS is a much more well known and analysed PRNG.
>> >> >
>> >> Because Micali-Schnorr is faster by several orders of magnitude.
>> >> BBS is notorious as the slowest PRNG of all times :-)
>>
>> >The BBS has nice properties though.
>>
>> >3. It's provably as secure as factoring.
>>
>> I'm pretty sure the original paper related security to the problem
>> of whether a number was or was not a square modulo pq, which is a
>different
>> problem from factoring pq. It is well-known that factoring allows
>> square determination, but I did not know that the converse had been
>> shown.
>Finding square roots is the same as factoring.
Yes, but the security proof in the original BBS paper was related
to determining with probability greater than 1/2 whether a number was
a square, WITHOUT exhibiting the square root.
------------------------------
From: "Robert Reynard" <[EMAIL PROTECTED]>
Subject: Re: Looking for a simple code wheel to print out for kids
Date: Thu, 10 May 2001 21:05:44 -0400
Go to Secret Code Breaker Online ==>http://codebreaker.dids.com
Go to Codes section.
There is a listing of different ciphers that can be used online and
downloaded. There is also an entry on that page that describes the Cipher
Disk Templates that can be printed.
=================================================
Cipher Disk Templates - Two pages of Cipher Disk Templates( Page 1 - Page
2 ) that can be printed out, pasted to card stock, cutout and used to create
your own Secret Code Breaker Cipher Disks that are a part of the Secret Code
Breaker - Secret Message Kit. Two pieces for a Caesar Cipher Disk and five
pieces for a Mexican Army Cipher Disk. You'll need both pages and if you use
a contrasting color (light blue, yellow) paper for one of the pages, the
disks will be easier to read when assembled.
=================================================
This will work using the Netscape 4.75 browser and Microsoft's I.E. 5.5
browser. For some reason, not yet determined, it will not work using the new
Netscape 6.01 browser. If anyone knows what change to make to the html, so
that it will work for all browsers, I would appreciate hearing from them.
Rock on,
Robert Reynard
Author, Secret Code Breaker series of crypto books for young readers (8-16
yr.)
Secret Code Breaker Online at ==> http://codebreaker.dids.com
"Ed Pugh" <[EMAIL PROTECTED]> wrote in message
news:9dd66i$rab$[EMAIL PROTECTED]...
> Please help!
>
> I just found out this evening, that I am giving a short
> presentation this weekend to some young folks. I thought I
> might do a simple story involving cryptography.
>
> I would like to give a hand-out at the end, so I am wondering
> if there is a "kids" web site anywhere that has a printable
> pattern for a simple cipher disk (the type with an outer and
> inner wheel with the alphabet going around each) with simple
> instructions on how to construct and use it (perhaps a simple
> monoalphabetic cipher for the younger kids, and polyalphabetic
> cipher for the "more advanced" ones. :-)
>
> This is for kids around ages 7-12 or so, so it should not be
> too fancy or complicated.
>
> Thanks for any help.
>
> Regards,
> --
> Ed Pugh, <[EMAIL PROTECTED]>
> Ottawa (Richmond), Ontario, Canada
> "Bum gall unwaith-hynny oedd, llefain pan ym ganed."
> (I was wise once, when I was born I cried - Welsh proverb)
------------------------------
From: [EMAIL PROTECTED] (Mitchell Morris)
Subject: NSA "Headline Puzzle" confusion ...
Date: 11 May 2001 15:27:27 GMT
First, here is a link to the NSA's "Headline Puzzle":
<URL:http://www.nsa.gov/programs/kids/standard/dashboard/master/index.shtml
>
Basically, there is a procedure that uses three English words to create a
set of related monoalphabetic ciphers. These ciphers are then used to
encipher hypothetical newspaper headlines, one headline per cipher. The
resulting ciphertexts are given to the player. The challenge is to
determine what the three initial words (key, setting, and hat) were.
After reading the "Strategy" page (which includes an example solution), I'm
rather confused. There, it suggests using the longest permutation chain
recovered as your candidate mixed alphabet, then using that as a plaintext
record each of the matching ciphertexts below it in a tableau. Each of
these ciphertexts must (by dint of the construction of them) be slides of
each other, and so you can fill in many of the missing blanks in the
tableau by correllating the rows. In the example, however, a 'W' appears in
the "solved" tableau when it didn't appear at all in the preliminary
tableau and I don't see where it came from.
The "example" then repeats this procedure with another permutation chain,
then concludes:
Now you can use the information you have from your headline
recoveries and the fact that you know that each row in the table
is a slide of every other row to complete the table and recover
a chain of all 26 letters.
followed by a diagram that includes a significantly larger tableau with one
row completely filled in and I don't see how tableaus 1 and 2 led to the
construction of tableau 3.
I have to assume I'm not an idiot, so I'm hoping I just misunderstood
something fairly trivial in the explanation. Can anyone suggest where I've
gone astray?
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Micali-Schnorr pseudorandom bit generator
Date: Fri, 11 May 2001 15:39:41 GMT
"Charles Blair" <[EMAIL PROTECTED]> wrote in message
news:awTK6.5694$[EMAIL PROTECTED]...
> "Tom St Denis" <[EMAIL PROTECTED]> writes:
>
>
> >"Charles Blair" <[EMAIL PROTECTED]> wrote in message
> >news:pnQK6.5666$[EMAIL PROTECTED]...
> >> "Tom St Denis" <[EMAIL PROTECTED]> writes:
> >>
> >>
> >> >"Klaus Pommerening" <[EMAIL PROTECTED]> wrote in message
> >> >news:9dgh4e$chl$[EMAIL PROTECTED]...
> >> >> In <[EMAIL PROTECTED]> Benjamin Goldberg wrote:
> >> >> > Also, since the Micali-Schnorr generator seems to be similar in
some
> >> >> > ways to the Blum-Blum-Schub generator, why not implement that,
> >instead?
> >> >> > BBS is a much more well known and analysed PRNG.
> >> >> >
> >> >> Because Micali-Schnorr is faster by several orders of magnitude.
> >> >> BBS is notorious as the slowest PRNG of all times :-)
> >>
> >> >The BBS has nice properties though.
> >>
> >> >3. It's provably as secure as factoring.
> >>
> >> I'm pretty sure the original paper related security to the problem
> >> of whether a number was or was not a square modulo pq, which is a
> >different
> >> problem from factoring pq. It is well-known that factoring allows
> >> square determination, but I did not know that the converse had been
> >> shown.
>
> >Finding square roots is the same as factoring.
>
> Yes, but the security proof in the original BBS paper was related
> to determining with probability greater than 1/2 whether a number was
> a square, WITHOUT exhibiting the square root.
Um ok. Well BBS is secure as long as you can't take square roots afaik...
I don't see how just knowing if X^2 is a QR will give you any info.
Tom
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Quasi Functions, a way to design Maximum Secure Cipher
Date: 11 May 2001 15:50:51 GMT
Kostadin Bajalcaliev <[EMAIL PROTECTED]> wrote:
> Hello
>
> After a years of research I have finally define the Quasi Function theory,
> and its practical implementation in cryptography the Polymorphic
> Encryption.
> Here is only the Introduction chapter of the thesis describing the results
> accomplished. I hope you will have interest to examine this thesis, all the
> comments and suggestions are welcomed. The full text of the thesis is
> available at
>
> http://eon.pmf.ukim.edu.mk/~kbajalc/algo/theory/pme
> or
> http://kbajalc.tripod.com/algo/theory/pme
No, it's not.
> As a illustration here is the round function of SQ6 the cipher
> implementing the theory described in the thesis:
>
> B0 B1 B2 B3 - are 32-bit words, Message BLOCK
> S0 S1 ... S15 - 32-bit words, the KEY
> F[0..0xFFFFFFFF](A1,A2) - array of functions returning 32-bit word
>
>
> Each Round is Defined as
>
> B3^=F[B0](B1,B2);
> (B0,B1,B2,B3)=(B3,B0,B1,B2) /* rotation */
>
>
> The function is defined as:
>
> T{i,j} denote the number formed from the i-th to the j-th bit of T
> Op = {+,xor,*,-}; Op[i] denote the i-th element of set Op
> S[0..15] array of 32-bit words = 512-bits of KEY
>
> F[G](A,B,C)= (S[g]<<<g) og A og (S[g]<<<g) og B og (S[q]<<<g)
>
> og - operation choused by G
> g - the value of a particular binary substring of G
>
> -------------------------
> F[T](A1,A2) = (S[{T{3..0}] <<< T{7..4}) \\
> op[T{25..24}] A1
> \\
> op[T{27..26}] (S[T{11..8}] <<< T{15..12}) \\
> op[T{29..28}] A2
> \\
> op[T{31..30}] (S[T{19..16}] <<< T{23..20});
I pause here to note that you're rotating 32-bit things by amounts
between 0 and 15. You really want 5-bit rotate amounts.
> Fox example having T=To=11 01 00 10 0010 1101 0101 1001 1011 1010
> The function F will be:
>
> F[To](A1,A2) = (S[10] <<< 11) * A1 + (S[9] <<< 5) xor A2 - (S[13] <<< 2);
Your cipher has very poor downwards diffusion. In particular, I believe
that a change in the top n <= 8 bits of any or all of the plaintext
words will only affect the top n bits of the ciphertext words. This (a)
is a trivial distinguisher for SQ6 and (b) leads to a fairly simple
key-recovery attack.
> ==================================================================
>
> 1. Introduction
>
> The best representative of the classical block-cipher design paradigm
> is Feistel Network with its most prominent realization, the Data
> Encryption Standard. The security in this approach is determined by
> the non-linearity of the S-box.
Not entirely, no. The diffusion properties of the linear
transformations are also vital for cipher strength.
> Even there have been a wide interest and discussion about the design
> of S-boxes there is no algorithm proposed for generating `secure
> S-box'. Maybe the invention of Differential and Linear cryptanalysis
> is the final word about this paradigm. DES-like ciphers are not
> candidates for Maximum Secure Cipher.
Total non-sequitur. We *can* construct DES-like ciphers which resist
differential and linear cryptanalysis. CAST and Blowfish spring to mind
immediately as examples.
> Maximum Secure Cipher (MSC) is an encryption algorithm immune to all
> possible (existing and to-be-invent) attacks.
That's a bold claim. Try proving it. Don't just wave hands: prove it.
> The first approach is to design cipher immune to the attack, and the
> second to design cipher incompatible to the attack. For example, there
> is no use of the Differential cryptanalysis if the cipher is not
> Feistel-Network based, AES is a nice example.
No. Completely wrong. Differential and linear-approximation techniques
can be applied to any cipher. It's not even true that Feistel networks
are particularly susceptible to these kinds of attacks. The reason that
Rijndael is resistant to differential cryptanalysis is that it's been
carefully optimized (using the wide-trail system).
Your cipher above, indeed, demonstrates differential weakness that is
well beyond anything exhibited by DES.
-- [mdw]
------------------------------
** 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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
