Re: Looking for Source of AES code

[Brian Gladman]

Damien O'Rourke wrote:
Hi,
I have some AES code here in C and I am trying to find it's author and
source.  I can't find
it on the Internet so I figure it was taken from a book.  Now I don't want
to send the entire
code to the list for obvious reasons however I was hoping you could help me
from the following
small snippet.  Maybe the use of  _fastcall  might jog someone's memory.
If there is
code that appears similar to this but is not exactly the same I would
appreciate the source
of that also.
void _fastcall encrypt(FILE *Encryption_File, FILE *Encrypted_File, unsigned
*expkey)
{
uchar in[16], out[16];
unsigned state[NumberOfBytes], rnd, i;
while (!feof(Encryption_File))
{
  uchar k=0;
   fread(in,sizeof(uchar),16,Encryption_File);/
   *(state+0)= *(in+0)24 | *(in+1) 16  | *(in+2)8  | *(in+3);
   *(state+1)= *(in+4)24 | *(in+5) 16  | *(in+6)8  | *(in+7)  ;
   *(state+2)= *(in+8)24 | *(in+9) 16  | *(in+10)8 | *(in+11)  ;
   *(state+3)= *(in+1)24 | *(in+3) 16  | *(in+14)8 | *(in+15)  ;
I don't know whose code it is but it has bugs in it.
The line above should be:
 *(state+3)= *(in+12)24 | *(in+13) 16  | *(in+14)8 | *(in+15);
I doubt that this is the only problem in this code either.
[snip]
Brian Gladman
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: AES Modes

[Brian Gladman]

Ian Grigg wrote:
Has anyone kept up to date with AES modes?
http://csrc.nist.gov/CryptoToolkit/modes
http://csrc.nist.gov/CryptoToolkit/modes/proposedmodes/
I'm looking for basic mode to encrypt blocks (using AES)
of about 1k in length, +/- an order of magnitude.  Looking
at the above table (2nd link) there are oodles of proposed
ones.
It would be nice to have a mode that didn't also require
a separate MAC operation - I get the impression that
this is behind some of the proposals?
I provide some code and some speed comparison data for some of the AES 
modes here:

  http://fp.gladman.plus.com/AES/index.htm
I focus mainly on the combined encryption/authentication modes but I 
only cover those that I believe are free of licensing costs.

Brian Gladman
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: AES Modes

[Brian Gladman]

Ian Grigg wrote:
Jack Lloyd also passed along lots of good comments I'd
like to forward (having gained permission) FTR.  I've
edited them for brevity and pertinence.
[snip]
 I'm obviously being naive here ... I had thought that the combined 
mode would
  be faster, as it would run through the data once only, and that AES 
seems to
  clip along faster than SHA1.

AFAIK all of the modes that use only one block cipher invocation per 
block of
input are patented. EAX+CCM both use two AES operations per block, and
byte-for-byte SHA-1 is 2-5x faster than AES (at least in the 
implementations
I've seen/used/written), so using AES+HMAC is probably going to be 
faster than
AES/EAX or AES/CCM. The obvious exception being boxes with hardware AES 
chips
and slow CPUs (eg, an ARM7 with an AES coprocessor), where AES will of 
course
be much faster than SHA-1.
Maybe my C implementation of SHA1 is hopeless but I get SHA1 on an x86 
at about 17 cycles per byte (over 100,000 bytes) and AES in C at 21 
cycles per byte.

So I would put these two algorihms at about the same speed in C. In 
consequence I rather suspect that the 'two encryptions per block' cost 
might also apply to combined modes when AES is used with HMAC-SHA1.

Rich Schroeppel's CS mode has been added to the NIST modes list earlier 
this year and is not patented. It seems to have a cost that is close to 
'one encryption per block' but it has the 'interesting' property of 
using the internal 'mid-point' state of the cipher algorithm that is in use.

   Brian Gladman
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: AES Modes

[Brian Gladman]

Eric Young wrote:
Quoting Brian Gladman [EMAIL PROTECTED]:

Ian Grigg wrote:

Jack Lloyd also passed along lots of good comments I'd
like to forward (having gained permission) FTR.  I've
edited them for brevity and pertinence.
[snip]
I'm obviously being naive here ... I had thought that the combined 
mode would
 be faster, as it would run through the data once only, and that AES 
seems to
 clip along faster than SHA1.

AFAIK all of the modes that use only one block cipher invocation per 
block of
input are patented. EAX+CCM both use two AES operations per block, and
byte-for-byte SHA-1 is 2-5x faster than AES (at least in the 
implementations
I've seen/used/written), so using AES+HMAC is probably going to be 
faster than
AES/EAX or AES/CCM. The obvious exception being boxes with hardware AES 
chips
and slow CPUs (eg, an ARM7 with an AES coprocessor), where AES will of 
course
be much faster than SHA-1.
Maybe my C implementation of SHA1 is hopeless but I get SHA1 on an x86 
at about 17 cycles per byte (over 100,000 bytes) and AES in C at 21 
cycles per byte.

So I would put these two algorihms at about the same speed in C. In 
consequence I rather suspect that the 'two encryptions per block' cost 
might also apply to combined modes when AES is used with HMAC-SHA1.
Are you running on a P4?  ASM for sha1 on a P4 takes about 11.9 cycles 
per byte.  The P4 is a very touchy x86 implementation.
On most other architectures I nearly always see a bit less than 2 times faster
sha1 vs AES.  On AMD64, asm, I have
AES-cbc at 12.2 cycles per byte and sha1 at 6.8.  This is about
as good a CPU as it gets (IPC near 3 for both implementations).
The SHA1 figure is for a P3 using VC++ set to generate code that will 
run on all Pentium family machines.  I have not optimised the C code for 
any particular machine. 17/12 for C/ASM is a bit worse than I would have 
hoped for but is not that bad.

I would not be surprised to see an average AES/SHA1 speed comparison in 
the 1.5:2.5 range but I was a bit surprised to see Jack's 2.0:5.0 range.

I will have to see if VC++ can be coaxed down from 17 cycles per byte 
for SHA1 without giving up on code that runs on all Pentium compatible 
machines :-)

   Brian Gladman
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: AES cache timing attack

[Brian Gladman]

Hal Finney wrote:

 Steven M. Bellovin writes:


Dan Bernstein has a new cache timing attack on AES:
http://cr.yp.to/antiforgery/cachetiming-20050414.pdf


 This is a pretty alarming attack.  Bernstein was actually able to recover
 the AES key using a somewhat artificial server which reported its own
 timing to do an AES operation.  In principle the same attack would be
 possible on a typical remote server, using a larger number of requests
 to average out timing variations.

This is a very nice piece of work by Bernstein but I am not convinced
about the practical significance of the attack.

And I certainly don't see any reason to abandon some of the design
approaches (e.g table lookup) as he has been suggesting just because
they are exploitable in some situations. In many situations they are not
exploitable at all and in those situations where they might cause
problems it is up to system designers to decide whether or not they need
to deploy countermeasures.


 He also had some critical things to say about the AES selection
 process, which apparently dropped the ball on this issue.  Other ciphers
 got dinged for nonconstant execution time, but no one thought that cache
 misses would be that significant.


 Dan has more information at http://cr.yp.to/mac.html, including
 graphs showing the variability in timings for various
 implementations at http://cr.yp.to/mac/variability1.html and
 http://cr.yp.to/mac/variability2.html, and his own attempt at a (nearly)
 constant-time AES implementation as part of his poly1305-aes MAC
function.

 It would be interesting to see how the speed of his AES implementation
 compares to that of other widely used versions like Brian Gladman's.
 How much speed penalty do you pay to get the constant speed?  As Dan
 notes, you can easily make a slow AES that runs at constant speed, but
 a fast one is far more difficult.


Nevertheless Bernstein has shown up one issue that I had not been
conscious of and this is that on modern (Intel) x86 systems there is no
longer a significant speed penalty for unaligned memory accesses to
32-bit words, a feature that allows AES to be implemented with very much
less table space than is normally the case.

There is almost no speed penalty in terms of best speed and the typical
speed is likely to be a lot better in most practical situations because
the load on the cache is greatly reduced.  And the timing variability of
this code is greatly reduced so its an all round win on the x86.

The downside is that, although unaligned accesses on x86 are ok, on many
other architectures these cause exceptions and this makes it tedious to
build compressed table operation into portable C code. In fact it is so
tedious that I am not going to offer this and have instead simply
published x86 assembler code which I report on here:

   http://fp.gladman.plus.com/AES/index.htm

For those who can live with x86 only, and with an assembler
implementation, this code matches the maximum speed of my large table
assembler version on the P3 and P4.

Another issue that this raises is that of the crypto API since in those
situations where the timing attack matters it is necessary to control
the position of the expanded AES key on the stack and this requires that
key expansion and encryption is done as one integrated API call, aka:

   encrypt(key[], in[], out[], no_of_blocks)

I hope this helps but if not I will try and answer any other questions.

   Brian Gladman



-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: TPM disk crypto

[Brian Gladman]

Adam Back wrote:

 So the part about being able to detect viruses, trojans and attest
 them between client-server apps that the client and server have a
 mutual interest to secure is fine and good.
 
 The bad part is that the user is not given control to modify the hash
 and attest as if it were the original so that he can insert his own
 code, debug, modify etc.
 
 (All that is needed is a debug option in the BIOS to do this that only
 the user can change, via BIOS setup.)

I haven't been keeping up to date with this trusted computing stuff over
the last two years but when I was last involved it was accepted that it
was vital that the owner of a machine (not necessarily the user) should
be able to do the sort of things you suggest and also be able to exert
ultimate control over how a computing system presents itself to the
outside world.

Only in this way can we undermine the treacherous computing model of
trusted machines with untrusted owners and replace it with a model in
which trust in this machine requires trust in its owner on which real
information security ultimately depends (I might add that even this
model has serious potential problems when most machine owners do not
understand security).

Does anyone know the current state of affairs on this issue within the
Trusted Computing Group (and the marketed products of its members)?

   Brian Gladman


-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: [-SPAM-] Re: Can you keep a secret? This encrypted drive can...

[Brian Gladman]

David Johnston wrote:
 Jon Callas wrote:


 Moreover, AES-256 is 20-ish percent slower than AES-128. 
 Compared to AES-128, AES-256 is 140% of the rounds to encrypt 200% as
 much data. So when implemented in hardware, AES-256 is substantially
 faster.

AES-256 does not encrypt any more data per round than AES-128.

My guess is that you are thinking about Rijndael with a 256 bit block
and a 256 bit key.

  Brian Gladman

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: [-SPAM-] Re: Can you keep a secret? This encrypted drive can...

[Brian Gladman]

Jon Callas wrote:
 I just ran a speed test on my laptop. Here are some relevant excerpts:
 
 CipherKey Size  Block Size  Enc KB/sec  Dec KB/sec
     --  --  --
 IDEA  128 bits   8 bytes  24032.0924030.66
 3DES  192 bits   8 bytes  10387.6710399.30
 CAST5 128 bits   8 bytes  29331.1729459.49
 Twofish   256 bits  16 bytes  20233.6319185.82
 AES-128   128 bits  16 bytes  44100.2346266.98
 AES-192   192 bits  16 bytes  39731.3341228.87
 AES-256   256 bits  16 bytes  36017.9537302.43
 Blowfish  128 bits   8 bytes  35347.3438311.22
 
 Comparing AES-128 and AES-256, encrypt speed is 1.2243959x and decrypt
 is 1.2403208x. So that makes my
 lick-your-finger-and-stick-it-in-the-wind rule of thumb of 20% slower
 okay. I'll try to say 20-25% in the future.
 
 Of course, though, implementation matters a lot. I'm running a PPC-32
 machine. You'll get different answers on an ia32, and different ones an
 AMD64.

For AES the round function and key scheduling cost per round are
basically the same for both AES-128 and AES-256.  In consequence I would
expect the speed ratio to be close to the ratio of the number of rounds,
which is 14 / 10 or 40%.

My own figures on AMD64 are 1.35 for encryption and 1.39 for decryption.
And on a P4 they are 1.36 and 1.38 respectively. These are hence close
to the expected 40% figure.

This suggests to me that a figure around 20% would apply in applications
in which about half the time is spent in encryption and half in other
higher level activities.

Can I hence assume that your benchmark is being run at application level
rather than algorithm level?  If not why is the ratio only 22% on the
PPC-32?

   Brian Gladman

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: It's a Presidential Mandate, Feds use it. How come you are not using FDE?

[Brian Gladman]

Steven M. Bellovin wrote:
 On Tue, 16 Jan 2007 07:56:22 -0800
 Steve Schear [EMAIL PROTECTED] wrote:
 
 At 06:32 AM 1/16/2007, Steven M. Bellovin wrote:
 Disk encryption, in general, is useful when the enemy has physical
 access to the disk.  Laptops -- the case you describe on your page --
 do fit that category; I have no quarrel with disk encryption for
 them. It's more dubious for desktops and *much* more dubious for
 servers.
 As governments widen their definitions of just who is a potential
 threat it makes increasing sense for citizens engaged in previous
 innocuous activities (especially political and financial privacy) to
 protect their data from being useful if seized.  This goes double for
 those operating privacy-oriented services and their servers.  As an
 example, when TOR servers were recently seized in German raids (with
 the implication that they were being used as conduits for child porn)
 the police knew enough to only take the hot-swap drives (which were
 encrypted and therefore paper weights after removal) if only for
 show.  The main loss to the operators was repair to the cage locks.

 Legal access is a special case -- what is the law (and practice) in any
 given country on forced access to keys?  If memory serves, Mike Godwin
 -- a lawyer who strongly supports crypto, etc. -- has opined that under
 US law, a subpoena for keys would probably be upheld by the courts.  I
 believe that British law explicitly mandates key disclosure.  

The situation here in the UK is that Parliament has passed a law (RIPA)
that allows the UK government to introduce key disclosure powers if it
wishes to do so.

So far these powers have not been bought into operation but the UK
government initiated a consultation last year on whether it should take
this step.  We are still awaiting a decision on this.

   Brian Gladman

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: 5x speedup for AES using SSE5?

[Brian Gladman]

Eric Young wrote:
 Eric Young wrote:
 I've not looked at it enough yet, but currently I'm doing an AES round
 in about 140 cycles a block (call it 13 per round plus overhead) on a
 AMD64, (220e6 bytes/sec on a 2ghz cpu) using normal instructions. 
 Urk, correction, I forgot I've recently upgraded from a 2ghz machine to
 2.5ghz.
 So that should read about 182 cycles per block, and 18 cycles per round.
 I though the number seems strange :-(.  I tent to always quote numbers
 from a 2-3 second run encrypting a 4k buffer, not a machine cycle
 counter over one or two blocks, so I leave myself open to this kind of
 error :-(

The best figure I obtain on an AMD64 system is 11 cycles/byte, which
matches your results (you had me worried for a while with 9 cycles/byte!)

To go 5 times faster than this would mean close to 2 cycles/byte, a
speed that I find hard to believe without hardware acceleration

But a fully byte oriented implementation runs at about 140 cycles/byte
and here the S-Box substitution step is a significant bottleneck.  I too
think the PPERM instruction could be used for this and it seems possible
that this would produce large savings.  So 30 cycles/byte might well be
achievable in this case.

I hence wonder whether this is the comparison that AMD are making.

It is also possible that the PPERM instruction could be used to speed up
the Galois field calculations to produce the S-Box mathematically rather
than by table lookup. I have tried this in the past but it has not
proved competitive.  But PPERM looks interesting here as well.

   Brian Gladman

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: full-disk subversion standards released

[Brian Gladman]

- Original Message - 
From: Jonathan Thornburg jth...@astro.indiana.edu

To: Brian Gladman b...@gladman.plus.com
Cc: John Gilmore g...@toad.com; Peter Gutmann 
pgut...@cs.auckland.ac.nz; cryptography@metzdowd.com; 
s...@cs.columbia.edu

Sent: Monday, February 02, 2009 3:53 AM
Subject: Re: full-disk subversion standards released

[snip]

It's this variety of different software encryption schemes -- and
compilers to turn them into binary code (which is what the NSA/Intel
backdoor ultimately has to key on) that, I think, makes it so much
harder for a hardware backdoor to work (i.e. to subvert software
encryption) in this context.


I well understand the difficulties of mounting attacks but the fact remains 
that if someone else is able to take over _control_ of your machine you 
won't obtain any security irrespective of whether your interest is in 
network or storage encryption.


And _if_ Intel were to be interested in being able to take over your machine 
whenever it wished to do so -- which I don't believe it is -- subverting its 
processor designs to make this possible will be many, many orders of 
magnitude more effective than subverting the design of a TPM that 99.999...% 
of machines won't have.


I am personally happy to trust Intel and I am also happy to trust the design 
of the TPM I happen to use.  And it is completey useless for DRM provided 
only that Intel and the TPM supplier have not been subverted.


I simply don't believe that TPM's will ever achieve (or could ever have 
achieved) the widespread adoption that effective DRM demands and I don't 
personally believe that such applications ever played much part in the 
design.   But _provided_ the hardware suppplier can be trusted, hardware 
based security is able to achieve a much higher level of assurance than pure 
software ever can.TPMs are hence useful in custom security applications 
and I am personally much more confident in my security using my TPM based 
solution than if I would be if I were relying on a pure software approach.


I am _not_ advocating TPM technology since I doubt its general utility for 
widespread adoption but I reject the idea that TPMs are part of an evil plot 
to infect the world with DRM.


   Brian Gladman

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com

Re: [Cryptography] Bruce Schneier has gotten seriously spooked

[Brian Gladman]

On 07/09/2013 01:48, Chris Palmer wrote:
 Q: Could the NSA be intercepting downloads of open-source encryption 
 software and silently replacing these with their own versions?
 
 Why would they perform the attack only for encryption software? They
 could compromise people's laptops by spiking any popular app.

Because NSA and GCHQ are much more interested in attacking communictions
in transit rather than attacking endpoints.

Endpoint attacks cost more to undertake, only give access to a limited
amount of data and involve much greater risks that their attack will
either be discovered or their means of attack will leave evidence of
what they have done and how they have done it.  The internal bueaucratic
costs of gaining approval for (adverarial) endpoint attacks also makes
it a more costly process than the use of network based interception.

There is significant use of open source encryption software in end to
end encryption solutions, in file archivers, in wifi and network
routers, and in protecing the communications used to manage and control
such components when at remote locations.  The open source software is
provided in source code form and is compiled from source in a huge
number of applications and this means that the ability to covertly
substitute broken source code could provide access to a huge amount of
traffic without the risks involved in endpoint attacks.

I stress that I am NOT suggesting that this has happened (or is
happening), simply that it has attractions from an NSA/GCHQ viewpoint.
Fortunately, I think it is a difficult attack to mount covertly (that
is, without the acqiecience of the author(s) of the software in question).

On the more general debate here, in my view, 'security for the masses'
through the deployment of encryption is a 'pipe dream' that isn't going
to happen.  Functionality (and the complexity that comes with it) is the
enemy of security and it is very clear that the public places a much
higher value on functionality than it does on security (or privacy).

Every time a new device comes onto the market, it starts with limited
functionality and some hope of decent security but rapidly evolves to be
a high functionality product in which the prospect of decent security
declines rapidly to zero.  Raspberry Pis look interesting _now_ but I
would be willing to bet that they won't buck the trend of increasing
funtionality and declining security simply because this is what the
majority in even this limited user community will want.

To buck this trend we need an effort like the Raspberry Pi effort but
one driven by our community with a strong commitment to simplicty and
deliberately limited functionality in both hardware and software.

   Brian Gladman

___
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography

Re: [Cryptography] AES-256- More NIST-y? paranoia

[Brian Gladman]

On 02/10/2013 13:58, John Kelsey wrote:
 On Oct 1, 2013, at 5:58 PM, Peter Fairbrother zenadsl6...@zen.co.uk wrote:
 
 AES, the latest-and-greatest block cipher, comes in two main forms - AES-128 
 and AES-256.

 AES-256 is supposed to have a brute force work factor of 2^256  - but we 
 find that in fact it actually has a very similar work factor to that of 
 AES-128, due to bad subkey scheduling.

 Thing is, that bad subkey scheduling was introduced by NIST ... after 
 Rijndael, which won the open block cipher competition with what seems to be 
 all-the-way good scheduling, was transformed into AES by NIST.
 
 What on Earth are you talking about?  AES' key schedule wasn't designed by 
 NIST.  The only change NIST made to Rijndael was not including some of the 
 alternative block sizes.  You can go look up the old Rijndael specs online if 
 you want to verify this.

As someone who was heavily involved in writing the AES specification as
eventually used by NIST, I can confirm what John is saying.

The NIST specification only eliminated Rijndael options - none of the
Rijndael options included in AES were changed in any way by NIST.

   Brian Gladman

___
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography

Re: [Cryptography] AES-256- More NIST-y? paranoia

[Brian Gladman]

On 03/10/2013 04:13, Ray Dillinger wrote:
 On 10/02/2013 02:13 PM, Brian Gladman wrote:
 
 The NIST specification only eliminated Rijndael options - none of the
 Rijndael options included in AES were changed in any way by NIST.
 
 Leaving aside the question of whether anyone weakened it, is it
 true that AES-256 provides comparable security to AES-128?

I may be wrong about this, but if you are talking about the theoretical
strength of AES-256, then I am not aware of any attacks against it that
come even remotely close to reducing its effective key length to 128
bits.  So my answer would be 'no'.

But, having said that, I consider the use of AES-256 in place of AES-128
to be driven more by marketing hype than by reality.  The theoreticaal
strength of modern cryptographic algorithms is the least of our worries
in producing practical secure systems.

   Brian Gladman

___
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography