I read the paper by Dieter Schmidt on Blowfish. He said that the first
64 bits of the key are ignored for the third and fourth round.

Although this  isn't an attack, is there any evidence that this
discovery would make it easier to extend any of the other attacks, such
as the Rijmen attack against 4 rounds, the Kelsey attack against 3
rounds, or the Vaudenay attack against weak keys?

No way, and the second 64 bits are ignored in the first and second
round!!!

...

You do realize that all key bits influence the sbox generation right?

Tom

So then the paper was a hoax? Maybe I misquoted it. It says that the
subkeys for the third and fourth round do not depend on the first 64
bits of the user key.

Five seconds with LibTomCrypt disproves the result...

#include "tomcrypt.h"

int main(void)
{
   symmetric_key skey;
   unsigned char key[16];

   memset(key, 0, 16);
   blowfish_setup(key, 16 ,0, &skey);
   memset(key, 1, 8);
   blowfish_setup(key, 16 ,0, &skey);
   return 0;

Gives

Key[ 0] = 706d9fcc1792d23a
Key[ 2] = 2db9d714966e1439
Key[ 4] = ac21a76d8324e988
Key[ 6] = ac0dc9dd2c38f6b3
Key[ 8] = 70619520fa23ecbe
Key[10] = 17b2f676eba13a04
Key[12] = 8b949e617a147caf
Key[14] = 56ccc6b64461b24d
Key[16] = 7361e6a1196a7c43
Key[ 0] = d4f62ce183c464ce
Key[ 2] = 61b90b19303a9d85
Key[ 4] = d26617236c259b3f
Key[ 6] = 2e7ad6052567fcab
Key[ 8] = 6479c8b49fd5df0b
Key[10] = 78e7bdd01ea558e0
Key[12] = a601910958356c0d
Key[14] = 5b4608b08c801daa
Key[16] = 956fdab1534d5baf

As output.  Both keys are completely different.

I edited my blowfish.c to have

   for (x = 0; x < 18; x += 2) {
       /* encrypt it */
       blowfish_ecb_encrypt(B, B, skey);
       /* copy it */
       LOAD32H(skey->blowfish.K[x], &B[0]);
       LOAD32H(skey->blowfish.K[x+1], &B[4]);
printf("Key[%2d] = %08lx%08lx\n", x, skey->blowfish.K[x],
skey->blowfish.K[x+1]);
   }

So his claim that "the first two round keys don't affect the latter
round keys" is totally wrong.

Tom

Some careful thinking later... What they're saying about P1/P2 may be
true but the conclusion is not.

It is not correct that all of the round keys do not depend on the first
64-bits of the key.  My demo disproves that.

It may be true that they don't depend on P1/P2 specifically but if your
key is shorter than 448-bits [which I'd suggest it should be] you will
repeat the internal key.  So really if you use 128-256 bit keys with
Blowfish this is of little to no consequence.

Better yet though use Twofish or AES instead which are faster and more
modern.

Tom

"Tom St Denis" <tomstde...@gmail.com> writes:

I used to use a Blowfish variant where the whole key schedule was done
twice (once with the usual S and P tables initialized with hex digits
of pi, and a second time starting with the result of the first pass).
This was endorsed by Bruce and guarantees total avalanche through the
entire S and P tables.  I agree with you that Blowfish isn't of much
interest any more and people should use AES instead (not sure about
Twofish).

Lately I'm interested in Serpent, which did poorly in the AES
competition because the designers used twice as many rounds as they
felt they needed to provide good security, while the other entrants
didn't do the same.  For a personal project that needs high speed
encryption, I'm thinking of using Serpent reduced to 16 rounds.  Also,
from Pentium II timings, it looks like using MMX speeds up Serpent
considerably despite any parallelism in the P2's normal integer pipes.
I think the P3/P4/Athlon won't have radically more parallelism than
the P2 had.

A "mini-twofish" would be better.  the fact the round function isn't
bijective is annoying...

Twofish is a decent cipher on its own.  AES is better because it's an
SPN but if I had a choice between memcpy and twofish ... ;-)

If you need high speed over short messages [and are not going standard]
why not use RC5-12/32/b.  It's very fast [~100 cycles per block on an
AMD64] and why attacks exist are not applicable to short messages.

Tom

"Tom St Denis" <tomstde...@gmail.com> writes:

This was before the Twofish era.  I'd have certainly used AES in that
application if it had been available back then.

I want to avoid patents, and I'm not concerned about short messages (I
want to encrypt 4KB blocks)).  That makes it feasible to do things
like use AES to create an RC4 key schedule and then encrypt the block
with RC4.  So I'm hoping for something faster than RC4.  If I
understand RC5 nomenclature, RC5/12/32 means a 64-bit blocksize, so
100 cycles/block would be 12.5 cycles/byte, which is pretty good, but
slower than RC4.  I'd like to think that bitsliced 16-round Serpent
using 128-bit SSE2 operations can beat that speed.

Why do you suggest keys shorter than 448 bits? Is there some security
disadvantage of having a key size too big?

Is there a security advantage?

Tom

The human brain cannot remember that number of random digits and most
people would make mistakes typing the number in.  However using emails
typing may no longer be required.

Andrew Swallow

CAST5?  hehehe

On an AMD64 with it's 16 GPRs you could probably do 3-4 blocks at once
and interleave the instructions to get some parallelism.  

;-)

Tom

Using the new CTR accelerator framework I'm adding to LTC I wrote a 2x
RC5 core [which largely just uses the RC5 code ... mmm re-use].  I get
49 cycles/block [6.2 cycles/byte] in CTR mode which is nearly a 2x
improvement.  The %cl register is a bottleneck [which with register
renaming is alleviated] so 3x/4x may not be much better.

Single RC5 in CTR mode takes around 100 cycles/block.

Anyways this demo serves two purposes...

1.  To show off RC5 in 2x CTR mode [it's designed to be compatible with
RC5 in CTR mode normally].

2.  To show off how easy it is to write accelerators for LTC.  ;-)

Tom

"Tom St Denis" <tomstde...@gmail.com> writes:

That's pretty fast.  What's 2x mean?  You're doing two RC5 operations
in a single loop with separate registers, to get more parallelism?
Are there two barrel shifters, or do you just schedule it carefully?

I think I'd rather stay away from the data dependent rotates, to avoid
both patents and timing attacks.  Serpent is really nice--pure
combinational logic in bitslice mode.

CTR requires you encrypt a counter, so I'm encrypting "2i" and "2i + 1"
at the same time.

As for "scheduling" it's C code [with possibly unaligned mem access but
otherwise portable].  The trick is that modern cpus can rename
registers.  e.g. the rotate value is stored in %cl but the value of %cl
is short lived.  so the cpu can just map it to a temp register.

A quick example of this would be

movl (%esi),%edx
addl %eax,%edx
movl %edx,(%edi)

movl (%esi+4),%edx
addl %eax,%edx
movl %edx,(%edi+4)

The cpu decodes the instructions and sends them into instruction queues
but since the value of "edx" [this is gas syntax so the destination is
on the right] is short lived so let's rename %edx in the first case to
%t0 for "the first temp" we get

movl (%esi),%t0
addl %eax,%t0
movl %t0,(%edi)

movl (%esi+4),%edx
addl %eax,%edx
movl %edx,(%edi+4)

But now the cpu can also pair them

movl (%esi),%t0     ||   movl (%esi+4),%edx
addl %eax,%t0       ||   addl %eax,%edx
movl %t0,(%edi)     ||   movl %edx,(%edi)

The net result of the code after the last instruction is %edx has the
correct value [e.g. (esi+4)+eax] but the code can be run in parallel.
This is how the x86 series of processors gets any sort of performance
with only 6 or so GPRs.  The K8 [amd64] solves this a bit with the 16
GPRs but even it has register renaming support.

I would be very surprised if you manually renamed %edx in the first
case to say %ebx that the code would run any faster on the Athlon k7/k8
processors.

You're missing the point.  You want todo SSE2 optimized Serpent and I'm
saying you'll have a nice API to plug that into [e.g. use the cool
LibTomCrypt API that will call your optimized Serpent code].  See we
all win ;-)

like my "49 cycles/block" is from the my generic testing which calls
ctr_encrypt() [a generic CTR routine that you use todo CTR with *ANY*
cipher].  Because the rc5_2x descriptor has a CTR accelerator my code
calls it instead of emulating CTR mode with a single block ECB.  The
net result is a 2x performance boost.

Tom

"Tom St Denis" <tomstde...@gmail.com> writes:

OK, did you happen to count the instructions in the compiler output to
see how many cpi you got?  That would give some indication of whether
SSE helps or not.

This is good to know, though for this particular application (rather
special purpose), a semi-heavyweight general purpose library is sort
of overkill.

"Tom St Denis" <tomstde...@gmail.com> writes:

Hmm, did you happen to count the instructions in the compiler output
and compute the cpi?  That would say how much real parallelism you're
getting.

Thanks, that's good to know in general.  For the particular
specialized application I have in mind though, I'm better off with
something more bare bones.

I didn't.  Roughly speaking 12 rounds of RC5 requires *at least* 24
rotates, 26 additions, 24 XORs.  So at a very minimum it's 74
instructions per block.  So roughly speaking I'm getting 74/49 = 1.5
instructions per clock.

The original code was actually less than 1 cycle per clock and mostly
because there was a huge dependency chain forming around the rotates.

I'll try doing 4x later on tonight [my testbench uses 4KiB blocks so as
long as I divide that I'm all good... ;-)] and see what it gets up to.

Bullocks.  Can't get much more barebones than a WG511T or PS2 ;-)

Tom

"Tom St Denis" <tomstde...@gmail.com> writes:

Interesting.

You mean 4 loops using the extra a64 registers?  Hmm, might save you a
little loop overhead but it would sure be nice if you could use 64-bit
operations somehow.

The hardware isn't the problem, I just don't want to hair up the code
so much.

hmm. rather.

Sorry... couldn't resist...

Problem is they are not fixed rotates.  The x86 [even the amd64] still
uses %cl for the rotate count.  As annoying that is....

So far ~910 satifisfied downloaders of LTC 1.00 [they'll like 1.01 I'm
sure] and no complaints.

As an aside... some of my downloads are from weird places like Goldman
Sachs, the USDA, Ford, etc...

Anyone got a clue why folks like that would be downloading crypto?

Tom