Cryptography-Digest Digest #303, Volume #14 Sun, 6 May 01 14:13:01 EDT
Contents:
Re: annoying posts ("Tom St Denis")
Re: Best encrypting algoritme (SCOTT19U.ZIP_GUY)
Re: Best encrypting algoritme ("Tom St Denis")
Re: Tiny s-boxes (Tim Tyler)
Re: Tiny s-boxes ("Tom St Denis")
GF(2^W) sboxes timings ("Tom St Denis")
Re: Tiny s-boxes (Paul Rubin)
Re: Best encrypting algoritme (SCOTT19U.ZIP_GUY)
free en/decryption library (Frank Uepping)
----------------------------------------------------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: annoying posts
Date: Sun, 06 May 2001 16:29:10 GMT
"Stop Boschloo posting diarrhea" <[EMAIL PROTECTED]> wrote in
message news:[EMAIL PROTECTED]...
> NOTICE: This message may not have been sent by the Sender Name
> above. Always use cryptographic digital signatures to verify
> the identity of the sender of any usenet post or e-mail.
Does anyone remember when Boschloo posted last anyways?
Tom
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Best encrypting algoritme
Date: 6 May 2001 16:32:34 GMT
[EMAIL PROTECTED] (Tom St Denis) wrote in
<AKdJ6.27519$[EMAIL PROTECTED]>:
>
>"SCOTT19U.ZIP_GUY" <[EMAIL PROTECTED]> wrote in message
>news:[EMAIL PROTECTED]...
>> [EMAIL PROTECTED] (Tom St Denis) wrote in
>> <1UbJ6.27172$[EMAIL PROTECTED]>:
>>
>> >
>> >"SCOTT19U.ZIP_GUY" <[EMAIL PROTECTED]> wrote in message
>> >news:[EMAIL PROTECTED]...
>> >> [EMAIL PROTECTED] (Tom St Denis) wrote in
>> >> <BR4J6.25523$[EMAIL PROTECTED]>:
>> >>
>> >> >
>> >> >I still don't get your main points. If the system is a FSM
>> >> >(Finite State Machine) such as any computer program (they must be
>> >> >finite) then there are only a *finite* amount of states the
>> >> >program can be in. This means that no matter what you do, if it's
>> >> >a FSM then I can write a program to brute force it. There is no
>> >> >way to escape this logic. You can only make brute force
>> >> >impractical (i.e huge key, or something to that effect).
>> >>
>> >> Tom what you lack and refuse to learn or even seem to engage
>> >> your
>> >> brain is. I could write a cyrpto system with even a 1 byte block
>> >> size. and 2 bits of key space. Lets say I take my messages I don't
>> >> have many but I compress them done using bijective compression.
>> >> and then encrypt that bijectively compressed message with a 2 bit
>> >> key using bijective encryption.If you write a super duper brute
>> >> force machine you may get all of the 4 message I may of sent. There
>> >> may have
>> >been
>> >> 407 messages. You have reduced it to 4. Know which message is it.
>> >> The four are all equally likely.
>> >
>> >Yeah but you can't break a real cipher even in ECB mode with a single
>> >block. If you gave me say 15, 1-byte blocks with this 2-bit key I
>> >could figure out what the key is. No matter what you do.
>>
>> Actaully Tom we are in the bar room betting area. If you
>> can find a trusted person by both of us. I will write a cyrpto
>> system then use a bijective type of compression encryption system.
>> to map a message to at least 15 bytes. You then have a one in four
>> chance of winning money. How about 20 dollars. I don't like barroom
>> bets unless I have the odds in my favor.
>
>I will bet 1000 dollars that with a 2-bit key and a 15-byte message I
>could find the real key 100% of the time. Assuming the message is
>in fact english. Let's change this around.
Tell you what to make it more interesting and educational for you
how about a mode. where bijectivity really shines. You get to not see
the code but get to send and encrypt messages of your choice useing
your choice of the 4 keys. You can do up to 20 if your wish with
your buddy David W or Mr BS. You don't get to see the encryption
method in this second mode only the input and output pairs.
IN this second mode where bijectivity rains supremium. I also
send the cipher text of the message you want to break. But nothing
about the method other than its bijective with 4 states. where front end
BICOM with fixed pass word back end scott19u with fixed pasword.
the middle is a secrect but but will not include BICOM in its workings
all you know is that its impedanced matched to BICOMs output and
scott19u's input. There will be 4 paths in middle code based on
the 2 bit key. Notice with out matching transforms scott19u is
not bijective since it rejects short files. However with short
impedances matchers as I call them this problem vanishes. Such
a matcher would also go to the ouput of scott19u to make sure its
truely bijective front end to back end.
IN this method I will be more than generous you can use outside
help. I am willing to give you 100 dollars if you or your crypto
god buddies can break this 2 bit bijective system. I will give you
one more advantage. since you don't get a copy of code. You don't
have to give just give plaintext with a key and use the resulting
cipher text. You can give ciphertext and a key and I will tell you
the file that would encrypt to it. You can make the test message anything
except the exact copy of the message your trying to reverese.
After all its only a 2 bit bijective encryption system. If you win
this last one I give you 100 dollars. If you lose you lose
you give me 50 dollars. Actaully the trusted hold of the funds
gived the money out.
Does this seem fair to you.
If so let me go over it again. You send a file I would send
back the 4 key states and what the file encrypts to. I also
send you 4 key states and what the file decrypts to. So for
each file you get 8 files back. You then colboarte with your
buddies. And send another file. I send back 8 more as above.
You also have the encypted file. I don't tell you what key
is but it will be encrypted english text. YOur goal is so solve
this 2 bit cyrpto program for the secret message. One hint good
bijective crypto is not yours fathers crypto its a different kind
of cat. I could make the encrypted text some english sentence
from some standard book. where it is at least 60 ascii characters.
no line feed or carriage return just straight upper case A-Z with
single spaces between words and a period at the end.
As you most likely already realize. Its not like I will find
4 such texts from a 2 bit encryption system. But I am a gambler
and I realize decent 2 bit bijective crypto systems are 2 hard
for the psuedo crypto gods who post on this forum and act like
they know something that they don't. If you feel BICOM to
string we could even use scott19u front and back But both scott19u
and BICOM are using secret fixed passwords.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE "OLD VERSIOM"
http://www.jim.com/jamesd/Kong/scott19u.zip
My website http://members.nbci.com/ecil/index.htm
My crypto code http://radiusnet.net/crypto/archive/scott/
MY Compression Page http://members.nbci.com/ecil/compress.htm
**NOTE FOR EMAIL drop the roman "five" ***
Disclaimer:I am in no way responsible for any of the statements
made in the above text. For all I know I might be drugged or
something..
No I'm not paranoid. You all think I'm paranoid, don't you!
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Best encrypting algoritme
Date: Sun, 06 May 2001 16:59:08 GMT
"SCOTT19U.ZIP_GUY" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Tell you what to make it more interesting and educational for you
> how about a mode. where bijectivity really shines. You get to not see
> the code but get to send and encrypt messages of your choice useing
> your choice of the 4 keys. You can do up to 20 if your wish with
> your buddy David W or Mr BS. You don't get to see the encryption
> method in this second mode only the input and output pairs.
This is a different challenge. In the original challenge I get to see the
code the ciphertext and all related details. The only thing missing is the
key in the original challenge (and the plaintext of course...)
> IN this second mode where bijectivity rains supremium.
You mean by obscurity? The original question related to finding the key not
the algorithm.
<snip>
Ok since your not being halfway intelligent about this. This is the real
challenge.
You send me the program (complete source code) along with an encrypted
message (for our purposes using a small symmetric key) using some known
cipher say RC5 or TEA or something. Then I mount the brute force attack to
find the key (if possible).
My clain is that with about 8kb of text I could easily find the correct key
with virtually 100% certainty. (assuming the keyspace is small enough).
Tom
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Tiny s-boxes
Reply-To: [EMAIL PROTECTED]
Date: Sun, 6 May 2001 16:57:10 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
: "Tim Tyler" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
:> Tom St Denis <[EMAIL PROTECTED]> wrote:
:> : "Tim Tyler" <[EMAIL PROTECTED]> wrote in message
:> :> Tom St Denis <[EMAIL PROTECTED]> wrote:
:> :> : "Tim Tyler" <[EMAIL PROTECTED]> wrote in message
:> :> To be honest I haven't yet investigated in any depth how best to
:> :> implement tiny s-boxes in software.
:>
:> : Generally in software you group the bits. I.e two 4x4's into one 8x8
:> : etc...
:>
:> Yuck ;-) If someone told me that I had to do things like that then I
:> reckon I would be hard-pressed to make a case for using small s-boxes.
: No, it's flexibility. In GOST for example the 4x4's are ideal for hardware
: and embedded platforms. In software you can compute the entire round
: function with four 8x32 lookups and three OR's. That's fast.
GOST must have some order in its boxes (or something) to pull a trick
like that. Four 8 bit table lookups do not the block width of GOST make.
If you had a row of 32 4x4 independently-configured s-boxes (making a
total of 128 bits in output width) and combined them into 8x8 boxes for
the purpose of looking up the results you'd need 16 consecutive table
look-ups to calculate the result. Each table would take 256 bytes, and
you'd need a different table for every pair of s-boxes in your cypher.
I'm not sure I'm convinced about this big LUT idea. ISTM that - with
my tiny s-boxes - a promising approach would be to shift left 1, and 2
places, right 1 and 2 places, and then perform a sequence of masked
AND, OR and XOR operations, which calculated all the s-box outputs
for a single word in parallel. This wouldn't have to use a LUT at
all. The bigger the word size, the more attractive it would be.
/Maybe/ if all the LUTS for all the combinations of s-boxes in your cypher
fit into your cache then a LUT approach would not work too badly.
Anyway, if I was going hell for leather, I'd certainly be inclined to
investigate the performance of alternative methods thoroughly before
going for a LUT-based approach.
:> :> : You're right that small (i.e 4x4 => 8x8) sboxes should be used more
:> :> : often then larger ones [...]
:> :>
:> :> Well, as far as I understand it, this isn't terribly widely accepted.
:>
:> : How so? Twofish, Serpent, Rijndael, DES, GOST, SAFER, etc... are all
:> : ciphers using 4x4 to 8x8 sized transforms.
:>
:> Well, you're right - though AFAICS relatively few cyphers go down to 4x4,
:> there are quite a number that use 8x8 boxes.
: Serpent and GOST use 4x4's...
I mentioned both of those in my original post. I'd say two cyphers
was "relatively few" - but please don't take this as an invitation
to ferret out a few more ;-)
--
__________ http://rockz.co.uk/ http://alife.co.uk/ http://hex.org.uk/
|im |yler http://atoms.org.uk/ http://mandala.co.uk/ [EMAIL PROTECTED]
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Tiny s-boxes
Date: Sun, 06 May 2001 17:16:45 GMT
"Tim Tyler" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> Tom St Denis <[EMAIL PROTECTED]> wrote:
> : "Tim Tyler" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> :> Tom St Denis <[EMAIL PROTECTED]> wrote:
> :> : "Tim Tyler" <[EMAIL PROTECTED]> wrote in message
> :> :> Tom St Denis <[EMAIL PROTECTED]> wrote:
> :> :> : "Tim Tyler" <[EMAIL PROTECTED]> wrote in message
>
> :> :> To be honest I haven't yet investigated in any depth how best to
> :> :> implement tiny s-boxes in software.
> :>
> :> : Generally in software you group the bits. I.e two 4x4's into one 8x8
> :> : etc...
> :>
> :> Yuck ;-) If someone told me that I had to do things like that then I
> :> reckon I would be hard-pressed to make a case for using small s-boxes.
>
> : No, it's flexibility. In GOST for example the 4x4's are ideal for
hardware
> : and embedded platforms. In software you can compute the entire round
> : function with four 8x32 lookups and three OR's. That's fast.
>
> GOST must have some order in its boxes (or something) to pull a trick
> like that. Four 8 bit table lookups do not the block width of GOST make.
Hmm that's not clear to me. The round function in GOST is eight parallel
4x4 look ups followed by a rotate by 11 bits. You can do both as one set of
four 8x32 tables.
> I'm not sure I'm convinced about this big LUT idea. ISTM that - with
> my tiny s-boxes - a promising approach would be to shift left 1, and 2
> places, right 1 and 2 places, and then perform a sequence of masked
> AND, OR and XOR operations, which calculated all the s-box outputs
> for a single word in parallel. This wouldn't have to use a LUT at
> all. The bigger the word size, the more attractive it would be.
>
> /Maybe/ if all the LUTS for all the combinations of s-boxes in your cypher
> fit into your cache then a LUT approach would not work too badly.
I don't follow ya. GOST, Rijndael, Twofish, Square, etc can be done either
as 8x8's (or 4x4s for GOST) or as a set of 8x32's...
> Anyway, if I was going hell for leather, I'd certainly be inclined to
> investigate the performance of alternative methods thoroughly before
> going for a LUT-based approach.
>
> :> :> : You're right that small (i.e 4x4 => 8x8) sboxes should be used
more
> :> :> : often then larger ones [...]
> :> :>
> :> :> Well, as far as I understand it, this isn't terribly widely
accepted.
> :>
> :> : How so? Twofish, Serpent, Rijndael, DES, GOST, SAFER, etc... are all
> :> : ciphers using 4x4 to 8x8 sized transforms.
> :>
> :> Well, you're right - though AFAICS relatively few cyphers go down to
4x4,
> :> there are quite a number that use 8x8 boxes.
>
> : Serpent and GOST use 4x4's...
>
> I mentioned both of those in my original post. I'd say two cyphers
> was "relatively few" - but please don't take this as an invitation
> to ferret out a few more ;-)
Hehehe
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: GF(2^W) sboxes timings
Date: Sun, 06 May 2001 17:27:30 GMT
Using the code below I timed the function F(X) = X^7 in GF(2^32). It takes
about 2465 cycles on my Athlon Tbird to perform this function given random
inputs.
Just FYI :-) Of course I might be able to optimize the code better but I
doubt it since GCC makes fairly decent code.
On the bonus side this makes a 32x32 sbox with fairly low dp and lp bounds.
/* Perform a multiplication in GF(2^32) returning ab */
unsigned long gf_mul(unsigned long a, unsigned long b)
{
unsigned long result = 0;
while (a) {
if (a & 1)
result ^= b;
a >>= 1;
if (b & 0x80000000ul)
b = (b << 1) ^ 0xd59c382dul;
else
b <<= 1;
}
return result;
}
/* x^7 in GF(2^32) */
unsigned long gf_exp(unsigned long a)
{
unsigned long sqr, tmp;
sqr = gf_mul(a,a); /* sqr = a^2 */
tmp = gf_mul(sqr, sqr); /* tmp = a^4 */
tmp = gf_mul(tmp, sqr); /* tmp = a^6 */
return gf_mul(tmp, a); /* = a^7 */
}
--
Tom St Denis
---
http://tomstdenis.home.dhs.org
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: Tiny s-boxes
Date: 06 May 2001 10:55:20 -0700
Tim Tyler <[EMAIL PROTECTED]> writes:
> : 3way is described in Applied Cryptography.
>
> Thanks. I /did/ look there - but I went to the index - and there were
> no entries under "3" or the author's name...
It's definitely in there. Look under Three-way, or in the table of
contents, or just flip through the chapter on block ciphers til you find it.
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Best encrypting algoritme
Date: 6 May 2001 17:46:39 GMT
[EMAIL PROTECTED] (Tom St Denis) wrote in
<wpfJ6.28602$[EMAIL PROTECTED]>:
>
>"SCOTT19U.ZIP_GUY" <[EMAIL PROTECTED]> wrote in message
>news:[EMAIL PROTECTED]...
>> Tell you what to make it more interesting and educational for you
>> how about a mode. where bijectivity really shines. You get to not see
>> the code but get to send and encrypt messages of your choice useing
>> your choice of the 4 keys. You can do up to 20 if your wish with
>> your buddy David W or Mr BS. You don't get to see the encryption
>> method in this second mode only the input and output pairs.
>
>This is a different challenge. In the original challenge I get to see
>the code the ciphertext and all related details. The only thing missing
>is the key in the original challenge (and the plaintext of course...)
Actaually in the first type of challenge What I send is irrelavent
i send you cipher text and it makes no real differnence what the key
is since there will be 4 messages that map from the cipher text to
the key. Here is such a method
let the identity trandform be used for all files but 8 files
the eight files being message 1 to 4 and the bytes 00000001 to 00000100
if you send somthing other than the 8 files. I just xor the key 00 01 10
or 11 to the first byte. If it is one of the specail 8 i map
if 00 I map message1 to 00000001 and message 2 to 00000010
and so on. I also map the reverse so 000000001 goes to message 1
if I an using 01 as key i map do as above but map message 2 to 00000001
so I just rotate and I think it obvious how I do the rest. IN
each case those four messages map to the set of 1 to 4 in a single byte
and vica versa.
There I have described a full system for you. the ouput is 00000001
which message was it or which key. Fact you can't tell.
Message 1 is "Tom lacks the knowledge to understand bijective encryption"
Message 2 is "Will tommy every grow up."
Message 3 is "I douby tommy will ever learn crypto"
message 4 is "Crypto is to hard for tommy boy"
the message was encrypted to 00000001 what was the key or which one
of the message did I use. You have the complete cyrpto system tommy
boy what is it or what is the key.
>
>> IN this second mode where bijectivity rains supremium.
>
>You mean by obscurity? The original question related to finding the key
>not the algorithm.
I just gave you an example of first type for free guess which of the
messages is sent or what the key was you get only one guess since there
are only 4 anwsers. If you guess it today in next post I'll sen you
the money.
In the second challenge I am limited in the games I can play and
since a four state machine you should be able to get the anwser
especailly since I give you so much info where you see how alternate
files encrypt and decrypt. Hard isn't it. Well its only 2 bits Tommy
and I can see real crypto even at 2 bits is to hard for you.
>
><snip>
>
>Ok since your not being halfway intelligent about this. This is the
>real challenge.
>
>You send me the program (complete source code) along with an encrypted
>message (for our purposes using a small symmetric key) using some known
>cipher say RC5 or TEA or something. Then I mount the brute force attack
>to find the key (if possible).
IF I send you the program I want to use it would be with BICOM
or scott19u as part of it. I know these are more complicated than the toy
cipher you wish me to use but I wont use RC5 or TEA I wanted something
designed to be somewhat more secure than the kind you play with.
and with scott19u and bicom with 4 states that worked for any key
yes you can plug in the 4 values but still your guessing which of the
four solutions it is. Granted it may be hard to find places where all
four are ascii messages if I allow all files. But there are there.
>
>My clain is that with about 8kb of text I could easily find the correct
>key with virtually 100% certainty. (assuming the keyspace is small
>enough).
your clain is bogus. I just gave you such a system that is fully
bijective. We can repeat message 1 and 2..4 or add words of your
choice till its 8k in length. Then you can't do it. Wake up Tommy
smell the coffee. Try to think before you shoot your mouth off.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE "OLD VERSIOM"
http://www.jim.com/jamesd/Kong/scott19u.zip
My website http://members.nbci.com/ecil/index.htm
My crypto code http://radiusnet.net/crypto/archive/scott/
MY Compression Page http://members.nbci.com/ecil/compress.htm
**NOTE FOR EMAIL drop the roman "five" ***
Disclaimer:I am in no way responsible for any of the statements
made in the above text. For all I know I might be drugged or
something..
No I'm not paranoid. You all think I'm paranoid, don't you!
------------------------------
From: Frank Uepping <[EMAIL PROTECTED]>
Subject: free en/decryption library
Date: Sun, 06 May 2001 20:05:37 +0200
Hi,
I am new with en/decryption and I am looking for a free and open
en/decryption C/C++ library that compiles with gcc and C++ Builder.
Thanks
Frank U.
------------------------------
** 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
******************************
