Re: AES counter mode support missing from EVP
On Tue, 29 Apr 2008, Dr. Stephen Henson wrote: the problem is that now one can't offload AES counter modes to the engine unless the application itself specifies its own EVP functions and structures. However, even then, counter mode IDs and names are missing from obj*.h files so functions like OBJ_nid2sn() crash. That happens with openssl engine -c, for example. It is enough to add following 3 lines to objects.txt so that AES counter mode can be offloaded to the engine using the workaround mentioned: : AES-128-CTR : aes-128-ctr : AES-192-CTR : aes-192-ctr : AES-256-CTR : aes-256-ctr It would be better is standard OIDs existed for these modes and those were added instead. You can create OIDs dynamically with OBJ_create() too, that should work without the need to modify OpenSSL at all. aha, thanks, that's a good idea. It seems to me that I can't use OBJ_create() without providing an OID but ASN1_OBJECT_create() + OBJ_add_object() is OK for me and no phony OIDs are used then. J. -- Jan Pechanec __ OpenSSL Project http://www.openssl.org Development Mailing List openssl-dev@openssl.org Automated List Manager [EMAIL PROTECTED]
Re: AES counter mode support missing from EVP
On Tue, Apr 29, 2008, Jan Pechanec wrote: hi, I can see that EVP API doesn't support AES counter mode. My guess is that it might be because of the fact that current EVP API doesn't have a parameter for counter length. Is that the reason or is it something else? Nobody having time to develop it is the main reason. The lack of a parameter isn't a problem for EVP many cipher specific parameters can be set using the ctrl mechanism. the problem is that now one can't offload AES counter modes to the engine unless the application itself specifies its own EVP functions and structures. However, even then, counter mode IDs and names are missing from obj*.h files so functions like OBJ_nid2sn() crash. That happens with openssl engine -c, for example. It is enough to add following 3 lines to objects.txt so that AES counter mode can be offloaded to the engine using the workaround mentioned: : AES-128-CTR : aes-128-ctr : AES-192-CTR : aes-192-ctr : AES-256-CTR : aes-256-ctr It would be better is standard OIDs existed for these modes and those were added instead. You can create OIDs dynamically with OBJ_create() too, that should work without the need to modify OpenSSL at all. Steve. -- Dr Stephen N. Henson. Email, S/MIME and PGP keys: see homepage OpenSSL project core developer and freelance consultant. Homepage: http://www.drh-consultancy.demon.co.uk __ OpenSSL Project http://www.openssl.org Development Mailing List openssl-dev@openssl.org Automated List Manager [EMAIL PROTECTED]
Re: AES counter mode
In message [EMAIL PROTECTED] on Fri, 27 Jun 2003 09:56:38 +0200, Thierry Boivin
[EMAIL PROTECTED] said:
Thierry.Boivin Generalized approach : as differencies for the
Thierry.Boivin various applications are the way to build the IV, ie:
Thierry.Boivin nonce part /upper counter part / lower counter part
Thierry.Boivin /whatever part, and, in my opinion, not the way to
Thierry.Boivin increment such a global IV from block to block, I
Thierry.Boivin would make the library incrementing by one on the
Thierry.Boivin whole size of the IV, leaving boundaries aspects (the
Thierry.Boivin routine just don't care about the way the given IV was
Thierry.Boivin built) and associated overflow condition checks (the
Thierry.Boivin routine gives back the manipulated IV) to the
Thierry.Boivin responsability of the calling programs.
Do I understand correctly with this patch (for 0.9.8-dev, but should
work with 0.9.7 as well)?
Index: crypto/aes/aes_ctr.c
===
RCS file: /e/openssl/cvs/openssl/crypto/aes/aes_ctr.c,v
retrieving revision 1.5
diff -u -r1.5 aes_ctr.c
--- crypto/aes/aes_ctr.c13 Nov 2002 14:01:34 - 1.5
+++ crypto/aes/aes_ctr.c29 Jun 2003 15:11:17 -
@@ -62,19 +62,49 @@
/* NOTE: CTR mode is big-endian. The rest of the AES code
* is endian-neutral. */
-/* increment counter (128-bit int) by 2^64 */
+/* increment counter (128-bit int) by 1 */
static void AES_ctr128_inc(unsigned char *counter) {
unsigned long c;
- /* Grab 3rd dword of counter and increment */
+ /* Grab bottom dword of counter and increment */
#ifdef L_ENDIAN
- c = GETU32(counter + 8);
+ c = GETU32(counter + 0);
c++;
- PUTU32(counter + 8, c);
+ PUTU32(counter + 0, c);
#else
- c = GETU32(counter + 4);
+ c = GETU32(counter + 12);
c++;
- PUTU32(counter + 4, c);
+ PUTU32(counter + 12, c);
+#endif
+
+ /* if no overflow, we're done */
+ if (c)
+ return;
+
+ /* Grab 1st dword of counter and increment */
+#ifdef L_ENDIAN
+ c = GETU32(counter + 4);
+ c++;
+ PUTU32(counter + 4, c);
+#else
+ c = GETU32(counter + 8);
+ c++;
+ PUTU32(counter + 8, c);
+#endif
+
+ /* if no overflow, we're done */
+ if (c)
+ return;
+
+ /* Grab 2nd dword of counter and increment */
+#ifdef L_ENDIAN
+ c = GETU32(counter + 8);
+ c++;
+ PUTU32(counter + 8, c);
+#else
+ c = GETU32(counter + 4);
+ c++;
+ PUTU32(counter + 4, c);
#endif
/* if no overflow, we're done */
--
Richard Levitte \ Tunnlandsvägen 3 \ [EMAIL PROTECTED]
[EMAIL PROTECTED] \ S-168 36 BROMMA \ T: +46-8-26 52 47
\ SWEDEN \ or +46-708-26 53 44
Procurator Odiosus Ex Infernis-- [EMAIL PROTECTED]
Member of the OpenSSL development team: http://www.openssl.org/
Unsolicited commercial email is subject to an archival fee of $400.
See http://www.stacken.kth.se/~levitte/mail/ for more info.
__
OpenSSL Project http://www.openssl.org
Development Mailing List [EMAIL PROTECTED]
Automated List Manager [EMAIL PROTECTED]
Re: AES counter mode
Stephen Sprunk wrote: Thus spake Richard Levitte - VMS Whacker [EMAIL PROTECTED] lee_dilkie (the other thing to remember is that CTR can be used with lee_dilkie any block cipher, it's not limited to AES) Absolutely. However, since it's currently very obviously an experimental field, and it was originally requested for AES, that's where we currently have it. Of course, if we had general mode implementation instead of having them implemented with each algorithm, things would be easier. Unfortunately, we get bit by performance hits if we do that (I think it was Steve who said he'd experimented with things like that some time ago). I tested a bunch of different mode implementations, yes. Since some libcrypto ciphers implement the round function directly inside the mode loops (e.g. IDEA), there is no way to generalize modes and maintain performance. Others, such as AES, issue a function call and could be generalized, but the extra cost of calling a function pointer (vs a real function) is enough to outweigh the code savings. This is why most of the ciphers don't have generalised modes, of course! Cheers, Ben. -- http://www.apache-ssl.org/ben.html http://www.thebunker.net/ There is no limit to what a man can do or how far he can go if he doesn't mind who gets the credit. - Robert Woodruff __ OpenSSL Project http://www.openssl.org Development Mailing List [EMAIL PROTECTED] Automated List Manager [EMAIL PROTECTED]
RE: AES counter mode
At 12:21 24/06/03 -0400, you wrote: -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] Behalf Of David Maurus Sent: Tuesday, June 24, 2003 7:29 AM To: [EMAIL PROTECTED] Subject: Re: AES counter mode The easiest way to go about it would be to increment the user supplied IV by 1 for each encrypted block, and leave it to the user of this function to make sure that no overflow in the counter can occur. This obligation to the programmer should be written somewhere in big letters ;-) (i.e. DON'T USE COUNTER MODE TO ENCRYPT MORE THAN 2**32 [or 2**64, depending on the counter size] BLOCKS WITH THE SAME KEY!). Higher level routines, i.e. the SSL BIO, should avoid counter overflows automatically for the user by initiating a rehandshake. Agreed, just increment the user supplied IV, it's the most general approach and will work for all the protocols that need ctr mode but can't (shouldn't) agree on nounce/counter boundries. -lee I agree with this approach which leaves the crypto library very open and not to complex to manipulate, whatever the upper program to develop is. Generalized approach : as differencies for the various applications are the way to build the IV, ie: nonce part /upper counter part / lower counter part /whatever part, and, in my opinion, not the way to increment such a global IV from block to block, I would make the library incrementing by one on the whole size of the IV, leaving boundaries aspects (the routine just don't care about the way the given IV was built) and associated overflow condition checks (the routine gives back the manipulated IV) to the responsability of the calling programs. Thierry Boivin __ OpenSSL Project http://www.openssl.org Development Mailing List [EMAIL PROTECTED] Automated List Manager [EMAIL PROTECTED]
Re: AES counter mode
Michael Sierchio wrote: Completely. If we have confidence in the cipher and the secrecy of the key, make the nonce all zeroes. There's good reason for not doing this in the case of IPsec, but not for SSL/TLS. In theory, you may be right ;-). But: For one, I think that it can't hurt NOT to have complete confidence in the cipher. I prefer to err on the safe side. E.G. if an attack profits from having the same plaintext encrypted twice with different cipher texts, we would encounter these conditions a lot in http over SSL/TLS. This would be avoided by a nonce in the IV. And also, we should take into account that a lot of people use OpenSSL's crypto routines in another context than SSL/TLS. Best Regards, David __ OpenSSL Project http://www.openssl.org Development Mailing List [EMAIL PROTECTED] Automated List Manager [EMAIL PROTECTED]
Re: AES counter mode
Hello David,
David Maurus wrote:
Goetz Babin-Ebell wrote:
The application specifies 4 datas:
1. a step size
2. a bit mask.
3. a (optional) pointer to a function that is called if the
step bits that are not in the bit mask:
4. a (optional) pointer to a function doing the counting;
if (pCounter-Range)
return pCounter-Range(pCounter);
else
return Range_restart(pCounter);
The quoted code would restart counting when the counter overflows. That
would open up a predictable opportunity for attack. I am still convinced
that the default behaviour should be to report an error, and if this is
not possible, increment over the bit-bound of the counter (increment the
nonce), as this would cause the least damage.
OK.
The code was an example.
We can replace Range_Retsart() with Range_Terminate()...
The idea to have a function pointer for the increment function has the
advantage that one could implement a counter function that would
actually not count incrementally, but otherwise unique, as alluded to in
the NIST recommendation (also page 19):
This recommendation permits the use of any other incrementing function
that generates n unique
strings of m bits in succession from the allowable initial strings. For
example, if the initial string
of m bits is not the zero string, i.e., if it contains at least one
'1' bit, then an incrementing
function can be constructed from a linear feedback shift register that
is specialized to ensure a
sufficiently large period; see Ref. [5] for information about linear
feedback shift registers.
But then, a mask based range check would not be sufficient, since you
can't rely on any overflows.
Then we could let the Count() function handle the counter range
detection and return a third state:
[...]
int (*Count)(CounterData *pCounter); /* optional: handle a step,
returns: 0: error
returns: ==0: call Range
returns: 0: OK. */
[...]
Now the Do_Counter() would change to:
int Do_Counter(CounterData *pCounter)
{
int nRet;
if (!pCounter)
return -1;
if (pCounter-Count)
nRet = pCounter-Count(pCounter);
else
nRet = Count(pCounter);
if (nRet != 0)
return nRet;
if (pCounter-Range)
return pCounter-Range(pCounter);
else
return Range_terminate(pCounter);
return nRet;
}
In general, I'd prefer a more simple approach, like taking the counter
bits as a parameter, and returning an int code ERR_LIB_NONE (?) if
everything's OK, and an something like ERR_AES_CTR_OVERFLOW when the
counter overflows...
If we change the Count() function ro return
ERR_LIB_NONE on OK,
ERR_CTR_OVERFLOW on counter overflow
and any other error code to terminate,
Do_Counter would become:
int Do_Counter(CounterData *pCounter)
{
int nRet;
if (!pCounter)
return -1;
if (pCounter-Count)
nRet = pCounter-Count(pCounter);
else
nRet = Count(pCounter);
if (nRet == ERR_CTR_OVERFLOW)
{
if (pCounter-Range)
return pCounter-Range(pCounter);
else
return Range_terminate(pCounter);
}
return nRet;
}
Bye
Goetz
--
Goetz Babin-Ebell, TC TrustCenter AG, http://www.trustcenter.de
Sonninstr. 24-28, 20097 Hamburg, Germany
Tel.: +49-(0)40 80 80 26 -0, Fax: +49-(0)40 80 80 26 -126
smime.p7s
Description: S/MIME Cryptographic Signature
RE: AES counter mode
CTR mode offers very little advantage over CBC or CFB or OFB -- the motivation for IPsec was very high speed, parallel encryption with precomputation of the keystream (according to the Rt. Hon. Rev. Bellovin, IETF Security Area co-chair). A very important consideration for ultra high performance h/w ipsec implementations. Chaining modes like CBC just simply cannot go fast enough. It was also important for secure RTP, not for performance so much but for the alility to not have to pad plaintext out to an even blocksize of the cipher when using a block cipher (such as AES). This was very important for them because those tiny RTP packets would get expanded a lot when encrypted in a CBC mode. Stream ciphers could not be used for other reasons (packet reordering/loss, for example). Now.. Why SSL/TLS would need this mode is a bit more questionable.. ? I was just chiming in because OSSL's crypto libs are used for lots of non-SSL applications. -lee __ OpenSSL Project http://www.openssl.org Development Mailing List [EMAIL PROTECTED] Automated List Manager [EMAIL PROTECTED]
Re: AES counter mode
Thus spake Thierry Boivin [EMAIL PROTECTED] I agree with this approach which leaves the crypto library very open and not to complex to manipulate, whatever the upper program to develop is. Generalized approach : as differencies for the various applications are the way to build the IV, ie: nonce part /upper counter part / lower counter part /whatever part, and, in my opinion, not the way to increment such a global IV from block to block, I would make the library incrementing by one on the whole size of the IV, leaving boundaries aspects (the routine just don't care about the way the given IV was built) and associated overflow condition checks (the routine gives back the manipulated IV) to the responsability of the calling programs. I'm thinking this is the best general solution we can hope for. Also, we should explicitly include in the docs a warning to check the IV for overflow iff the counter is 64 bits. Richard, do you want me to write up the code change, or do you want to do it? S Stephen Sprunk God does not play dice. --Albert Einstein CCIE #3723 God is an inveterate gambler, and He throws the K5SSSdice at every possible opportunity. --Stephen Hawking __ OpenSSL Project http://www.openssl.org Development Mailing List [EMAIL PROTECTED] Automated List Manager [EMAIL PROTECTED]
Re: AES counter mode
Thus spake Richard Levitte - VMS Whacker [EMAIL PROTECTED] lee_dilkie (the other thing to remember is that CTR can be used with lee_dilkie any block cipher, it's not limited to AES) Absolutely. However, since it's currently very obviously an experimental field, and it was originally requested for AES, that's where we currently have it. Of course, if we had general mode implementation instead of having them implemented with each algorithm, things would be easier. Unfortunately, we get bit by performance hits if we do that (I think it was Steve who said he'd experimented with things like that some time ago). I tested a bunch of different mode implementations, yes. Since some libcrypto ciphers implement the round function directly inside the mode loops (e.g. IDEA), there is no way to generalize modes and maintain performance. Others, such as AES, issue a function call and could be generalized, but the extra cost of calling a function pointer (vs a real function) is enough to outweigh the code savings. FWIW, the performance gains of switching from __stdcall to __fastcall is staggering (at least on x86); that alone blows away all the experimentation I did with MMX and SSE extensions, hand-tuned ASM, etc. When I saw that, I gave up on any further algorithm improvements, though I'm sure there's still small improvements to be made here and there. S Stephen Sprunk God does not play dice. --Albert Einstein CCIE #3723 God is an inveterate gambler, and He throws the K5SSSdice at every possible opportunity. --Stephen Hawking __ OpenSSL Project http://www.openssl.org Development Mailing List [EMAIL PROTECTED] Automated List Manager [EMAIL PROTECTED]
Re: AES counter mode
Thus spake David Maurus [EMAIL PROTECTED] Stephen Sprunk wrote: In the specification of CTR mode, as proposed for AES, you will find the statement The number /nonce/ is incremented following each encryption. I interpreted this to mean that the top 2^64 bits are to be incremented for each successive block, and this is how I implemented the code. I assume that 'number /nonce/' should mean the result of the concatenated parts of the IV. No, in the proposal to NIST (by Lipmaa, Rogaway and Wagner), 'nonce' refers to the top 64 bits and 'ctr' refers to the lower 64 bits. In case of the AES-CTR IPSec draft, you get the IV by concatenating a msg number, a nonce, and the counter (at start initialized to 0). You can then safely incerement the 128 bit IV, *unless* you overflow the counter part (the lower 32 bits of the IV, according to the AES-CTR IPSec draft). NIST's version does not have a message number, and the counter is 64 bits. On the matter of overflowing the lower 64 bits, this is not specifically addressed in the submission (I think they assumed nobody would exceed 2^64 blocks per stream, which is reasonable) and thus I think wrapping is the correct failure. I'm not sure what you mean with 'the correct failure', but the clean way to handle a counter overflow would be to fail / report an error, instead of continuing to encrypt. Unfortunately, the current API has no way to report no more encryption possible, you must rekey. Given this limitation, two silent failure modes are possible: either wrap and reuse ctr values, or don't wrap and use nonce values the user didn't specify. The former is obviously bad, but IMHO the latter is equally bad. This discussion is academic for 64 bit counters, of course, as you probably won't see a 64 bit counter wrap very often. With a 32 bit counter however, the risk is a lot higher. Unfortunately, the current basic crypto functions offered by OpenSSL don't support returning an error condition, so 'failing' is not an option anyway. 64bit counters allow 256EB to be encrypted with a single key, and even at today's maximum link speed of 10Gb/s, that's just under 69,731 years of data. Famous last words perhaps, but I think we can safely ignore that problem. 32bit counters can wrap in under a minute; IPsec clearly has a pressing problem, but I'm not sure how to code to support both without giving up and making the ctr-increment function a user parameter. To increment the nonce introduces a more insidious failure mode where the user unintentionally reuses nonces. It is debatable whether wrapping the counter would be less bad than incrementing the nonce part. A wrapping counter is more predictable for an attacker (as it would occur *always* when the communication exceeds 2**32 or 2 **64 blocks) than an unlucky nonce choice. In other words: If we let the counter wrap, the user is always affected when the counter overflows, and the weak spot is predictable. If we allow to increment the nonce instead of wrapping the counter, the user is only affected when the counter overflows, *and* he continues to reuse the same key but chooses a new nonce, *and* the choosen nonce value collides with the incremented nonce. Per the NIST spec, the next nonce chosen will be the old nonce plus one, so the user's choice will always be unlucky. Unfortunately, implementing this (as has been requested) would require more significant changes to the API than I know how to make,as passing parameters to a mode doesn't appear to be supported today. The easiest way to go about it would be to increment the user supplied IV by 1 for each encrypted block, and leave it to the user of this function to make sure that no overflow in the counter can occur. This obligation to the programmer should be written somewhere in big letters ;-) (i.e. DON'T USE COUNTER MODE TO ENCRYPT MORE THAN 2**32 [or 2**64, depending on the counter size] BLOCKS WITH THE SAME KEY!). Higher level routines, i.e. the SSL BIO, should avoid counter overflows automatically for the user by initiating a rehandshake. While this option is tempting, and the user does have access to the counter at all times to check for impending overflow, experience shows that programmers ignore such warnings more often than not. S Stephen Sprunk God does not play dice. --Albert Einstein CCIE #3723 God is an inveterate gambler, and He throws the K5SSSdice at every possible opportunity. --Stephen Hawking __ OpenSSL Project http://www.openssl.org Development Mailing List [EMAIL PROTECTED] Automated List Manager [EMAIL PROTECTED]
Re: AES counter mode
Thus spake Michael Sierchio [EMAIL PROTECTED] Argument: let's write an Internet draft that describes the use of AES CTR mode in SSLv3/TLSv1. We can do it however we like, modulo the usual criticism and review in the IETF working group(s). Comments? Rich? Richard? Stephen? I'm a bit more ambitious... We should specify NIST-style CTR mode for all octet stream applications within the IETF's domain, with SSL/TLS as an example. For record-based systems, I don't know if NIST-style or IPsec-style would be more appropriate :-( Can someone explain why the IPsec folks felt they needed to reimplement CTR mode, especially in a way which appears to create more problems? S Stephen Sprunk God does not play dice. --Albert Einstein CCIE #3723 God is an inveterate gambler, and He throws the K5SSSdice at every possible opportunity. --Stephen Hawking __ OpenSSL Project http://www.openssl.org Development Mailing List [EMAIL PROTECTED] Automated List Manager [EMAIL PROTECTED]
RE: AES counter mode
Actually, SRTP was the first time I saw CTR mode and I believe it predates NIST (i could be wy wrong there). In SRTP, the counter is only 16 bits but that doesn't limit them to only encrypting 64K blocks of data, it only limits them to 64K blocks *in one rtp(udp) packet*. Obviously this isn't a limit as a udp packet cannot get that big. The nouce part is modified for each packet (based on info in the rtp header), so you can see there is no issue with counter overflow. What I was trying (unsuccessfully) to make a point about. Please don't code up your CTR mode to *just* do the NIST or Ipsec version of CTR mode. Please code a general CTR mode that can accommodate all the versions (including SRTP). I believe this is quite easy to do and does not require any special handling. That way, I can use your routines rather than my own, EVP-based, routines that kinda hack EVP under the covers and are probably going to be broken when I upgrade OSSL. :) (the other thing to remember is that CTR can be used with any block cipher, it's not limited to AES) regards, -lee -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] Behalf Of Stephen Sprunk Sent: Thursday, June 26, 2003 10:57 AM To: [EMAIL PROTECTED] Subject: Re: AES counter mode Thus spake Michael Sierchio [EMAIL PROTECTED] Argument: let's write an Internet draft that describes the use of AES CTR mode in SSLv3/TLSv1. We can do it however we like, modulo the usual criticism and review in the IETF working group(s). Comments? Rich? Richard? Stephen? I'm a bit more ambitious... We should specify NIST-style CTR mode for all octet stream applications within the IETF's domain, with SSL/TLS as an example. For record-based systems, I don't know if NIST-style or IPsec-style would be more appropriate :-( Can someone explain why the IPsec folks felt they needed to reimplement CTR mode, especially in a way which appears to create more problems? S Stephen Sprunk God does not play dice. --Albert Einstein CCIE #3723 God is an inveterate gambler, and He throws the K5SSSdice at every possible opportunity. --Stephen Hawking __ OpenSSL Project http://www.openssl.org Development Mailing List [EMAIL PROTECTED] Automated List Manager [EMAIL PROTECTED] __ OpenSSL Project http://www.openssl.org Development Mailing List [EMAIL PROTECTED] Automated List Manager [EMAIL PROTECTED]
Re: AES counter mode
In message [EMAIL PROTECTED] on Thu, 26 Jun 2003 12:55:22 -0400, Lee Dilkie [EMAIL PROTECTED] said: lee_dilkie What I was trying (unsuccessfully) to make a point lee_dilkie about. Please don't code up your CTR mode to *just* do the lee_dilkie NIST or Ipsec version of CTR mode. Please code a general lee_dilkie CTR mode that can accommodate all the versions (including lee_dilkie SRTP). I believe this is quite easy to do and does not lee_dilkie require any special handling. That way, I can use your lee_dilkie routines rather than my own, EVP-based, routines that lee_dilkie kinda hack EVP under the covers and are probably going to lee_dilkie be broken when I upgrade OSSL. :) OK, I've been follownig this discussion for a while, and it's time I ake action. Basically, to provide for all the current and future ways of handling the IV, I can see three alternatives: - have the application provide a function that manipulates the IV. - have the application specify exactly which part of the IV is the actual counter (in bit positions, or would byte positions be enough?). - a combination of the two (that would make our code extract the counters bits and only give those to the provided function, which then does the increment in any way it wishes). lee_dilkie (the other thing to remember is that CTR can be used with lee_dilkie any block cipher, it's not limited to AES) Absolutely. However, since it's currently very obviously an experimental field, and it was originally requested for AES, that's where we currently have it. Of course, if we had general mode implementation instead of having them implemented with each algorithm, things would be easier. Unfortunately, we get bit by performance hits if we do that (I think it was Steve who said he'd experimented with things like that some time ago). -- Richard Levitte \ Tunnlandsvägen 3 \ [EMAIL PROTECTED] [EMAIL PROTECTED] \ S-168 36 BROMMA \ T: +46-8-26 52 47 \ SWEDEN \ or +46-708-26 53 44 Procurator Odiosus Ex Infernis-- [EMAIL PROTECTED] Member of the OpenSSL development team: http://www.openssl.org/ Unsolicited commercial email is subject to an archival fee of $400. See http://www.stacken.kth.se/~levitte/mail/ for more info. __ OpenSSL Project http://www.openssl.org Development Mailing List [EMAIL PROTECTED] Automated List Manager [EMAIL PROTECTED]
Re: AES counter mode
Hello Richard,
Richard Levitte - VMS Whacker wrote:
In message [EMAIL PROTECTED]
on Thu, 26 Jun 2003 12:55:22 -0400, Lee Dilkie [EMAIL PROTECTED] said:
OK, I've been follownig this discussion for a while, and it's time I
ake action. Basically, to provide for all the current and future ways
of handling the IV, I can see three alternatives:
- have the application provide a function that manipulates the IV.
- have the application specify exactly which part of the IV is the
actual counter (in bit positions, or would byte positions be
enough?).
The application specifies 4 datas:
1. a step size
2. a bit mask.
3. a (optional) pointer to a function that is called if the
step bits that are not in the bit mask:
4. a (optional) pointer to a function doing the counting;
A quick draft of my idea:
typedef struct _CounterData CounterData;
struct _CounterData
{
Counter_Number nActual; /* the actual counter value */
Counter_Number nStep;/* Step size added each step */
Counter_Number nStepMask;/* Mask indikating when counter leaves
range */
int (*Count)(CounterData *pCounter); /* optional: handle a step,
returns: 0: error
returns: 0: OK. */
int (*Range)(CounterData *pCounter); /* optional: is called if
Count() returns out of range.
returns: 0: error
returns: 0: OK */
};
int Count(CounterData *pCounter)
{
if (!pCounter)
return -1;
pCounter-nActual+= pCounter-nStep;
return 1;
}
int Range_restart(CounterData *pCounter)
{
if (!pCounter)
return -1;
pCounter-nActual = ~pCounter-nStepMask;
return 1;
}
int Range_terminate(CounterData *pCounter)
{
return -1;
}
int Do_Counter(CounterData *pCounter)
{
int nRet;
if (!pCounter)
return -1;
if (pCounter-Count)
nRet = pCounter-Count(pCounter);
else
nRet = Count(pCounter);
if (nRet 0)
return nRet;
if (pCounter-nActual ~pCounter-nStepMask)
{
if (pCounter-Range)
return pCounter-Range(pCounter);
else
return Range_restart(pCounter);
}
return nRet;
}
OK.
The Mask could be an upper bound...
Any comments ?
Bye
Goetz
--
Goetz Babin-Ebell, TC TrustCenter AG, http://www.trustcenter.de
Sonninstr. 24-28, 20097 Hamburg, Germany
Tel.: +49-(0)40 80 80 26 -0, Fax: +49-(0)40 80 80 26 -126
smime.p7s
Description: S/MIME Cryptographic Signature
Re: AES counter mode
Steven, Stephen Sprunk wrote: Thus spake David Maurus [EMAIL PROTECTED] I assume that 'number /nonce/' should mean the result of the concatenated parts of the IV. No, in the proposal to NIST (by Lipmaa, Rogaway and Wagner), 'nonce' refers to the top 64 bits and 'ctr' refers to the lower 64 bits. Where did you find that? Is it possible that you've got an older version? In Nist's sp800-38a, available at http://csrc.nist.gov/publications/nistpubs/800-38a/sp800-38a.pdf the corresponding paragraph concerning counter mode with nonces reads (page 19): A second approach to satisfying the uniqueness property across messages is to assign to each message a unique string of b/2 bits (rounding up, if b is odd), in other words, a message nonce, and to incorporate the message nonce into every counter block for the message. The leading b/2 bits (rounding up, if b is odd) of each counter block would be the message nonce, and the standard incrementing function would be applied to the remaining m bits to provide an index to the counter blocks for the message. Thus, if N is the message nonce for a given message, then the jth counter block is given by Tj = N | [j]m, for j = 1n. The number of blocks, n, in any message must satisfy n 2m. A procedure should be established to ensure the uniqueness of the message nonces. In the middle of this quotation you'll find the sentence: 'The leading b/2 bits (rounding up, if b is odd) of each counter block would be the message nonce, and the standard incrementing function would be applied to the remaining m bits to provide an index to the counter blocks for the message. I think this is clear on the fact that e.g. with a 128 bit 'counter block' / IV, you'd use the leading 64 bits for the nonce (I'd interpret 'leading' as the Most Significant Bits, if the bits would represent a number), while the remaining 64 bits of the 'counter block' / IV are the bits that are actually counting up, i.e. get incremented. Unfortunately, the current API has no way to report no more encryption possible, you must rekey. Given this limitation, two silent failure modes are possible: either wrap and reuse ctr values, or don't wrap and use nonce values the user didn't specify. As I pointed out (I think), if you let the user provide an IV, let's say a 128 bit IV, and make clear in the documentation that the best way to use it would be to fill the highest 64 bit with a unique nonce, and clear the lowest 64 bits, as they will be used as a counter, there will be no problem. We could word the usage instructions even more general, saying that the lowest bits get used as counter, and that no more blocks should be encrypted with the same key and that counter, as the bits used as counter allow. 32bit counters can wrap in under a minute; IPsec clearly has a pressing problem, but I'm not sure how to code to support both without giving up and making the ctr-increment function a user parameter. You're right. While as Lee Dilkie pointed out, the IPSec message format will not allow that this 32 bit counter will overflow, I'd like to refrain from my previous recommendation to 'follow the IPSec draft as close as possible' in this issue, since 32 bit are obiously not enough for SSL. Per the NIST spec, the next nonce chosen will be the old nonce plus one, so the user's choice will always be unlucky. Again, in the version of the NIST document I've linked to above, I can't find a statment that the nonce is to be incremented. I can only find the requirement that the nonce must be unique for the encryption key. The easiest way to go about it would be to increment the user supplied IV by 1 for each encrypted block, and leave it to the user of this function to make sure that no overflow in the counter can occur. This obligation to the programmer should be written somewhere in big letters ;-) (i.e. DON'T USE COUNTER MODE TO ENCRYPT MORE THAN 2**32 [or 2**64, depending on the counter size] BLOCKS WITH THE SAME KEY!). Higher level routines, i.e. the SSL BIO, should avoid counter overflows automatically for the user by initiating a rehandshake. While this option is tempting, and the user does have access to the counter at all times to check for impending overflow, experience shows that programmers ignore such warnings more often than not. Of course I'd be glad if we could check the counter and throw an exception when it overflows, but the interface for the low level crypto routines doesn't seem to accommodate that. All functions return a 'void', e.g. nothing. I assume we cannot change that. (without breaking other parts). Best Regards, - David __ OpenSSL Project http://www.openssl.org Development Mailing List [EMAIL PROTECTED] Automated List Manager [EMAIL PROTECTED]
Re: AES counter mode
Gtz Babin-Ebell wrote: The application specifies 4 datas: 1. a step size 2. a bit mask. 3. a (optional) pointer to a function that is called if the step bits that are not in the bit mask: 4. a (optional) pointer to a function doing the counting; if (pCounter-Range) return pCounter-Range(pCounter); else return Range_restart(pCounter); The quoted code would restart counting when the counter overflows. That would open up a predictable opportunity for attack. I am still convinced that the default behaviour should be to report an error, and if this is not possible, increment over the bit-bound of the counter (increment the nonce), as this would cause the least damage. The idea to have a function pointer for the increment function has the advantage that one could implement a counter function that would actually not count incrementally, but otherwise unique, as alluded to in the NIST recommendation (also page 19): This recommendation permits the use of any other incrementing function that generates n unique strings of m bits in succession from the allowable initial strings. For example, if the initial string of m bits is not the zero string, i.e., if it contains at least one 1 bit, then an incrementing function can be constructed from a linear feedback shift register that is specialized to ensure a sufficiently large period; see Ref. [5] for information about linear feedback shift registers. But then, a mask based range check would not be sufficient, since you can't rely on any overflows. In general, I'd prefer a more simple approach, like taking the counter bits as a parameter, and returning an int code ERR_LIB_NONE (?) if everything's OK, and an something like ERR_AES_CTR_OVERFLOW when the counter overflows... - David __ OpenSSL Project http://www.openssl.org Development Mailing List [EMAIL PROTECTED] Automated List Manager [EMAIL PROTECTED]
Re: AES counter mode
Stephen Sprunk wrote: I'm a bit more ambitious... We should specify NIST-style CTR mode for all octet stream applications within the IETF's domain, with SSL/TLS as an example. For record-based systems, I don't know if NIST-style or IPsec-style would be more appropriate :-( There is no such thing as NIST-style. There's Helger Lipmaa's suggestion, and that's really it. A 64-bit counter offers the misleading sense that it is safe to use more than 2^32 blocks of keystream. CTR mode offers very little advantage over CBC or CFB or OFB -- the motivation for IPsec was very high speed, parallel encryption with precomputation of the keystream (according to the Rt. Hon. Rev. Bellovin, IETF Security Area co-chair). Can someone explain why the IPsec folks felt they needed to reimplement CTR mode, especially in a way which appears to create more problems? Yes. SSL/TLS have the advantage of operating over TCP -- where replay, delayed duplicates, out-of-order delivery, fragmentation, etc. are all handled magically and elsewhere. IPsec operates via a connectionless medium with no delivery guarantees (IP). Obviously we don't need nonces, just counters. __ OpenSSL Project http://www.openssl.org Development Mailing List [EMAIL PROTECTED] Automated List Manager [EMAIL PROTECTED]
Re: AES counter mode
Richard Levitte - VMS Whacker wrote: OK, I've been follownig this discussion for a while, and it's time I ake action. Basically, to provide for all the current and future ways of handling the IV, I can see three alternatives: - have the application provide a function that manipulates the IV. - have the application specify exactly which part of the IV is the actual counter (in bit positions, or would byte positions be enough?). - a combination of the two (that would make our code extract the counters bits and only give those to the provided function, which then does the increment in any way it wishes). There's no need for an IV for SSL/TLS encryption with AES CTR mode. All that's needed is a counter, and a mechanism to prevent using more than 2^38 or so bytes of keystream without changing the key. lee_dilkie (the other thing to remember is that CTR can be used with lee_dilkie any block cipher, it's not limited to AES) Absolutely. Not quite. You want to be sure to use block ciphers that are differentially strong. AES is particularly well-suited. __ OpenSSL Project http://www.openssl.org Development Mailing List [EMAIL PROTECTED] Automated List Manager [EMAIL PROTECTED]
Re: AES counter mode
In message [EMAIL PROTECTED] on Thu, 26 Jun 2003 13:31:37 -0700, Michael Sierchio [EMAIL PROTECTED] said: kudzu Richard Levitte - VMS Whacker wrote: kudzu kudzu OK, I've been follownig this discussion for a while, and it's time I kudzu ake action. Basically, to provide for all the current and future ways kudzu of handling the IV, I can see three alternatives: kudzu kudzu - have the application provide a function that manipulates the IV. kudzu - have the application specify exactly which part of the IV is the kudzuactual counter (in bit positions, or would byte positions be kudzuenough?). kudzu - a combination of the two (that would make our code extract the kudzucounters bits and only give those to the provided function, which kudzuthen does the increment in any way it wishes). kudzu kudzu There's no need for an IV for SSL/TLS encryption with AES CTR mode. kudzu All that's needed is a counter, and a mechanism to prevent using kudzu more than 2^38 or so bytes of keystream without changing the key. Whatever, I used the terms like this: - IV is a bitstring of some sort (possibly random), of the same size as the crypto algorithm block. In the AES case, it would be 128 bits. - For CTR mode, the counter is a part of the IV. The rest of the IV is some kind of random bits (a nonce). Those are the conditions I'm working from. Makes sense? kudzu lee_dilkie (the other thing to remember is that CTR can be used with kudzu lee_dilkie any block cipher, it's not limited to AES) kudzu kudzu Absolutely. kudzu kudzu Not quite. You want to be sure to use block ciphers that are kudzu differentially strong. AES is particularly well-suited. Point. -- Richard Levitte \ Tunnlandsvägen 3 \ [EMAIL PROTECTED] [EMAIL PROTECTED] \ S-168 36 BROMMA \ T: +46-8-26 52 47 \ SWEDEN \ or +46-708-26 53 44 Procurator Odiosus Ex Infernis-- [EMAIL PROTECTED] Member of the OpenSSL development team: http://www.openssl.org/ Unsolicited commercial email is subject to an archival fee of $400. See http://www.stacken.kth.se/~levitte/mail/ for more info. __ OpenSSL Project http://www.openssl.org Development Mailing List [EMAIL PROTECTED] Automated List Manager [EMAIL PROTECTED]
Re: AES counter mode
Richard Levitte - VMS Whacker wrote: Whatever, I used the terms like this: - IV is a bitstring of some sort (possibly random), of the same size as the crypto algorithm block. In the AES case, it would be 128 bits. - For CTR mode, the counter is a part of the IV. The rest of the IV is some kind of random bits (a nonce). Those are the conditions I'm working from. Makes sense? Completely. If we have confidence in the cipher and the secrecy of the key, make the nonce all zeroes. There's good reason for not doing this in the case of IPsec, but not for SSL/TLS. __ OpenSSL Project http://www.openssl.org Development Mailing List [EMAIL PROTECTED] Automated List Manager [EMAIL PROTECTED]
Re: AES counter mode
Stephen Sprunk wrote: In the specification of CTR mode, as proposed for AES, you will find the statement The number /nonce/ is incremented following each encryption. I interpreted this to mean that the top 2^64 bits are to be incremented for each successive block, and this is how I implemented the code. I assume that 'number /nonce/' should mean the result of the concatenated parts of the IV. In case of the AES-CTR IPSec draft, you get the IV by concatenating a msg number, a nonce, and the counter (at start initialized to 0). You can then safely incerement the 128 bit IV, *unless* you overflow the counter part (the lower 32 bits of the IV, according to the AES-CTR IPSec draft). Further review has indicated everyone else seems to think this means the nonce is incremented only between streams and it's the counter that is incremented between blocks; If you have a message number in the IV, you'd naturally incement the message number for each message (each message consisting of an arbitrary number of blocks), but then you'd also clear the counter to 0 and maybe even choose a new random nonce part. In the Schneier / Fergusson example, a 48 bit message number, a 16 bit random part and a 64 bit counter are used. When you start a new message, from my understanding you'd clear bits 0-63, and increment the msg number spanning bits 80-127. Probably, if your protocol or format allows for it, you'd also choose a new nonce (i.e. fill bits 64-79 with new random data). Since the recepient of the encryptded data can't guess the 16 bit random part if it changes, it is necessary to prepend the new IV, and accomodate for that in the message format or communication protocol. For online transmissions, it would be reasonable to start a re-keying handshake for this. On the matter of overflowing the lower 64 bits, this is not specifically addressed in the submission (I think they assumed nobody would exceed 2^64 blocks per stream, which is reasonable) and thus I think wrapping is the correct failure. I'm not sure what you mean with 'the correct failure', but the clean way to handle a counter overflow would be to fail / report an error, instead of continuing to encrypt. But this is also a matter of interoperability. Since you should not wrap the counter around (as it would offer a weakness for attackers), nobody who is trying to decrypt the data would expect to allow for wrapping. On the other hand, the same function is used for decrypting and encrypting, and when decrypting, failing might be worse than continuing. This discussion is academic for 64 bit counters, of course, as you probably won't see a 64 bit counter wrap very often. With a 32 bit counter however, the risk is a lot higher. Unfortunately, the current basic crypto functions offered by OpenSSL don't support returning an error condition, so 'failing' is not an option anyway. To increment the nonce introduces a more insidious failure mode where the user unintentionally reuses nonces. It is debatable whether wrapping the counter would be less bad than incrementing the nonce part. A wrapping counter is more predictable for an attacker (as it would occur *always* when the communication exceeds 2**32 or 2 **64 blocks) than an unlucky nonce choice. In other words: If we let the counter wrap, the user is always affected when the counter overflows, and the weak spot is predictable. If we allow to increment the nonce instead of wrapping the counter, the user is only affected when the counter overflows, *and* he continues to reuse the same key but chooses a new nonce, *and* the choosen nonce value collides with the incremented nonce. Other specifications have suggested that nonce be of unspecified length, not exactly 64 bits; this implies that the lower bits wrap in an overflow condition, otherwise there would be no need to specify a boundary between the different parts of counter at all. I think the intention of the boundary for the counter part is NOT to allow for wrapping, but to have a mechanism in place to ensure that a single IV (nonce + counter) is not used twice. If you just seeded the whole 128 bits with random data, and incremented them as if the counter was 128 bit, *and* you were using the same symmetric key for more than one message / transmission, you could be unlucky (most likely if your PRNG is suboptimal) and generate an IV that you've used already because of the counting. Separating the counter and the nonce leads to having a minimum distance of 32 or 64 bits between IVs, when you are careful to always use a fresh random nonce part. Implementing a mechanism to avoid collisions of IVs would be cumbersome otherwise. Unfortunately, implementing this (as has been requested) would require more significant changes to the API than I know how to make,as passing parameters to a mode doesn't appear to be supported today. The easiest way to go about it would be to increment the user supplied IV by 1 for each
RE: AES counter mode
-Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] Behalf Of David Maurus Sent: Tuesday, June 24, 2003 7:29 AM To: [EMAIL PROTECTED] Subject: Re: AES counter mode The easiest way to go about it would be to increment the user supplied IV by 1 for each encrypted block, and leave it to the user of this function to make sure that no overflow in the counter can occur. This obligation to the programmer should be written somewhere in big letters ;-) (i.e. DON'T USE COUNTER MODE TO ENCRYPT MORE THAN 2**32 [or 2**64, depending on the counter size] BLOCKS WITH THE SAME KEY!). Higher level routines, i.e. the SSL BIO, should avoid counter overflows automatically for the user by initiating a rehandshake. Agreed, just increment the user supplied IV, it's the most general approach and will work for all the protocols that need ctr mode but can't (shouldn't) agree on nounce/counter boundries. -lee __ OpenSSL Project http://www.openssl.org Development Mailing List [EMAIL PROTECTED] Automated List Manager [EMAIL PROTECTED]
Fwd: Re: AES counter mode
Hi,
http://archives.seul.org/mixminion/cvs/May-2002/msg00072.html shows that the problem
seems to have been submitted to the openssl team one year ago.I agree with Nick and go
to the same conclusion : as the openssl aes counter mode routines wants to count by
2**64 instead of by 1, the current implementation is not correct.
The source of disagreement seems to be the interpretation of a NIST document (Michael
pointed such a document when replying at first).
My understanding of this one is (in a practical perspective) is :
calling programs maintain a 64 bit long nonce counter. This counter is to be
incremented by one from messages to messages. As this nonce is used to form the high
part of a 128 bit long counter value -- we add 0 for the low part -- , the counter
element is globally incremented by 2**64 from messages to messages. This is for the
behavior of the calling program. If considering the routine implementing the message
encryption (so the openssl routine), message is to be split into blocks and each block
encrypted with a specific counter value : first block is used with the initial counter
given by the application (64 bit long value 64 + 64 bit long zeros.). Next blocks of
the message are then encrypted using a counter value of blockN = counter value of
blokcN-1 + 1 operation.
-- the AES_ctr128_inc routine, called internally on a block per block basis, should
therefore use a +1 operator instead of its current +2**64 operator.
Thierry Boivin
Date: Wed, 11 Jun 2003 08:06:34 +0200
To: [EMAIL PROTECTED]
From: Thierry Boivin [EMAIL PROTECTED]
Subject: Re: AES counter mode
At 07:48 10/06/03 -0700, you wrote:
Thierry Boivin wrote:
I agree with you about the way to build the initial ctr value from the nonce
value. My question is different : whithin the encryption of a whole plaintext
message (so a big block to be divided into 128 bit length blocks) , why to
increment ctr by 2^64 instead of 1 from block to block ?
My understanding of the operation is :
- increment nonce by one from messages to messages (so this is a 2^64 step if
considering ctr)
- but for each message:
- build initial ctr from the nonce value
- increment ctr by 1 from block to block
C'est votre compréhension et non votre accord que nous attendons!
Incrementing by 2^64 is incrementing the most significant 64-bit word by 1.
Yes, but my point is why does the routine increment by 2^64 ? Because the routine
is called on a block per block basis, i was expecting a +1 step instead of such a
+2^64 step.
For those who do not only expect comprehension et non votre accord, note that
patching the code in such a purpose allows the library to be compliant with reference
vectors given in :
http://www.ietf.org/internet-drafts/draft-ietf-ipsec-ciph-aes-ctr-04.txt
modified code :
/* increment low part of a 128 bit counter by 1 */
/* big endian representation */
static void AES_ctr128_inc(unsigned char *counter) {
unsigned long c;
c = GETU32(counter + 12);
c++;
PUTU32(counter + 12, c);
/* if no overflow, we're done */
if (c)
return;
c = GETU32(counter + 8);
c++;
PUTU32(counter + 8, c);
}
Thierry Boivin
__
OpenSSL Project http://www.openssl.org
Development Mailing List [EMAIL PROTECTED]
Automated List Manager [EMAIL PROTECTED]
Re: AES counter mode
In message [EMAIL PROTECTED] on Mon, 23 Jun 2003 18:22:37 +0200, Thierry Boivin [EMAIL PROTECTED] said: Thierry.Boivin My understanding of this one is (in a practical perspective) is : Thierry.Boivin calling programs maintain a 64 bit long nonce counter. This counter is to be incremented by one from messages to messages. As this nonce is used to form the high part of a 128 bit long counter value -- we add 0 for the low part -- , the counter element is globally incremented by 2**64 from messages to messages. This is for the behavior of the calling program. If considering the routine implementing the message encryption (so the openssl routine), message is to be split into blocks and each block encrypted with a specific counter value : first block is used with the initial counter given by the application (64 bit long value 64 + 64 bit long zeros.). Next blocks of the message are then encrypted using a counter value of blockN = counter value of blokcN-1 + 1 operation. And when should the increment by 2^64 occur? Is that something that the application should make sure happens with some kind of call to the currently non-existing functino AES_incr_ctr() (perhaps done in EVP_EncryptFinal())? If everyone can agree on such an interpretation, I have no problems changing it, as long as it also makes the implement crunch the available test vectors properly. -- Richard Levitte \ Tunnlandsvägen 3 \ [EMAIL PROTECTED] [EMAIL PROTECTED] \ S-168 36 BROMMA \ T: +46-8-26 52 47 \ SWEDEN \ or +46-708-26 53 44 Procurator Odiosus Ex Infernis-- [EMAIL PROTECTED] Member of the OpenSSL development team: http://www.openssl.org/ Unsolicited commercial email is subject to an archival fee of $400. See http://www.stacken.kth.se/~levitte/mail/ for more info. __ OpenSSL Project http://www.openssl.org Development Mailing List [EMAIL PROTECTED] Automated List Manager [EMAIL PROTECTED]
RE: AES counter mode
{jumping into a discussion somewhat late...}
I don't have experience with counter mode for SSL (if there is even such a
beast) or the NIST mode you are referencing (I believe Ipsec was looking at
that mode a few months ago) but I do have experience with counter mode for
SRTP (secure RTP; encryption of media streams). In fact, I wrote a counter
mode encryptor/decryptor using the EVP_* functions.
Counter mode for SRTP is a little different in that the counter part, the
part that increments for each keystream block (128 bits, for AES) is only
the lower 16 bits (rtp packets just don't get larger than that...) and the
application supplied starting count value (refered to as the packet IV in
SRTP) consumes 112 bits, starting at bit 16.
In general, the most flexible approach would be to provide an aes counter
encrypt function that took a 128 bit starting value (IV), incremented (+1)
it as many times as necessary to form the keystream (dependent on the size
of the buffer that needs encrypting), and performed the encryption and
subsquient xor'ing operation. As far as I can tell, the low bits that are
incremented will *not* overflow, by design, into the upper bits.
It should be up to the calling application to provide the 128 bit 'IV' for
each call to aes_ctr_encrypt(). You shouldn't need any AES_incr_ctr()
function. It's a little messier but it is more flexable and doesn't make
assumptions on where the counter ends and the IV begins.
(128 bit integers are a bit scarce to come by, I used char buffers myself,
which had the advantage of keeping things in network byte order as well).
There was one more generalization that I considered when the incrementation
value (+1 or +164) was still under discussion and that was to have the
application provide the increment value as well but this has performance
impacts.
-lee
-Original Message-
From: [EMAIL PROTECTED]
[mailto:[EMAIL PROTECTED] Behalf Of Richard
Levitte - VMS
Whacker
Sent: Monday, June 23, 2003 12:36 PM
To: [EMAIL PROTECTED]; [EMAIL PROTECTED]
Cc: [EMAIL PROTECTED]
Subject: Re: AES counter mode
In message [EMAIL PROTECTED]
on Mon, 23 Jun 2003 18:22:37 +0200, Thierry Boivin
[EMAIL PROTECTED] said:
Thierry.Boivin My understanding of this one is (in a
practical perspective) is :
Thierry.Boivin calling programs maintain a 64 bit long nonce
counter. This counter is to be incremented by one from
messages to messages. As this nonce is used to form the high
part of a 128 bit long counter value -- we add 0 for the low
part -- , the counter element is globally incremented by
2**64 from messages to messages. This is for the behavior of
the calling program. If considering the routine implementing
the message encryption (so the openssl routine), message is
to be split into blocks and each block encrypted with a
specific counter value : first block is used with the initial
counter given by the application (64 bit long value 64 + 64
bit long zeros.). Next blocks of the message are then
encrypted using a counter value of blockN = counter value
of blokcN-1 + 1 operation.
And when should the increment by 2^64 occur? Is that something that
the application should make sure happens with some kind of call to the
currently non-existing functino AES_incr_ctr() (perhaps done in
EVP_EncryptFinal())?
If everyone can agree on such an interpretation, I have no problems
changing it, as long as it also makes the implement crunch the
available test vectors properly.
--
Richard Levitte \ Tunnlandsvägen 3 \ [EMAIL PROTECTED]
[EMAIL PROTECTED] \ S-168 36 BROMMA \ T: +46-8-26 52 47
\ SWEDEN \ or +46-708-26 53 44
Procurator Odiosus Ex Infernis-- [EMAIL PROTECTED]
Member of the OpenSSL development team: http://www.openssl.org/
Unsolicited commercial email is subject to an archival fee of $400.
See http://www.stacken.kth.se/~levitte/mail/ for more info.
__
OpenSSL Project http://www.openssl.org
Development Mailing List [EMAIL PROTECTED]
Automated List Manager
[EMAIL PROTECTED]
__
OpenSSL Project http://www.openssl.org
Development Mailing List [EMAIL PROTECTED]
Automated List Manager [EMAIL PROTECTED]
Re: AES counter mode
Lee Dilkie wrote: I don't have experience with counter mode for SSL (if there is even such a beast) or the NIST mode you are referencing (I believe Ipsec was looking at that mode a few months ago) but I do have experience with counter mode for SRTP (secure RTP; encryption of media streams). In fact, I wrote a counter mode encryptor/decryptor using the EVP_* functions. CTR mode is not mentioned in the FIPS 197 document, NIST SP 800-38A specifies the CTR mode(s). This is a recommendation document, not a standards document. See appendix B.2 for a discussion of CTR values. This doc discusses the use of half the 128 bits as a nonce, and the remaining bits as a counter. Lipmaa, Rogaway and Wagner is the definitive recommendation for CTR mode operation, and the mode exists as part of AES (as opposed to Rijndael) because of Helger's efforts. They explicitly state Usage scenarios. In the recommended usage scenario, the party encrypting maintains an integer counter, nonce, initially 0, and produces the string ctr as the 128-bit string which encodes the number nonce . 2^64. (In other words, nonce is regarded as a 64-bit binary number, and ctr is constructed by appending to this number 64 zero-bits.) The number nonce is incremented following each encryption. Using AES Counter Mode With IPsec ESP - This mandates a 32-bit counter, requiring rekeying after 2^48 octets of stream material. http://www.ietf.org/internet-drafts/draft-ietf-ipsec-ciph-aes-ctr-04.txt Argument: let's write an Internet draft that describes the use of AES CTR mode in SSLv3/TLSv1. We can do it however we like, modulo the usual criticism and review in the IETF working group(s). Comments? Rich? Richard? Stephen? -- Well, Brahma said, even after ten thousand explanations, a fool is no wiser, but an intelligent man requires only two thousand five hundred. - The Mahabharata __ OpenSSL Project http://www.openssl.org Development Mailing List [EMAIL PROTECTED] Automated List Manager [EMAIL PROTECTED]
Re: AES counter mode
Thierry Boivin [EMAIL PROTECTED] said:
Thierry.Boivin My understanding of this one is (in a practical perspective) is :
Thierry.Boivin calling programs maintain a 64 bit long nonce counter.
This is not correct - to quote from the (btw excellent) new book from Bruce
Schneier and Neils Fergusson ('Practical Cryptography'), Page 75:
'CTR [Counter Mode] uses a remarkably simple method to generate the key stream. It
concatenates the nonce with the counter value, and encrypts it to form a single block
of the key stream. This requires that the counter and the nonce fit in a single block,
but with the modern 128-bit block sizes, this is rarely a problem. Oviously, the nonce
must be smaller than a single block, as there needs to be room for the counter value
i. A typical setup might use a 48-bit message number, 16 bits of additional nonce
data, and 64 bits for the counter i. This limits the system to encrypting 2**48
different messages using a single key, and limits eacht message to 2**68 bytes'
So apparently, the trick would be to leave the nonce untouched in the higher 64 bits, and increment the 64 lower bits. Instead of overflowing to bit 65 after 2**64 message blocks, the sensible option would be to stop the encryption with this key, and choose a new one. If we would continue counting despite the overflow into the nonce, we would risk to use (or better: have no mechanism in place to avoid using) the same key with the same 128 bit nonce/counter value twice, which would generate the same cipher output block again, which would mean that we would XOR different parts of the plain text with the same cipher bits, opening an opportunity for attack (albeit a very small one).
Richard Levitte - VMS Whacker wrote:
And when should the increment by 2^64 occur? Is that something that
the application should make sure happens with some kind of call to the
currently non-existing functino AES_incr_ctr() (perhaps done in
EVP_EncryptFinal())?
If everyone can agree on such an interpretation, I have no problems
changing it, as long as it also makes the implement crunch the
available test vectors properly.
Well, incrementing by 2**64 would only be reasonable if the nonce would
be in the lower 64 bits of the 128 bit nonce/counter value.
Best Regards,
David
__
OpenSSL Project http://www.openssl.org
Development Mailing List [EMAIL PROTECTED]
Automated List Manager [EMAIL PROTECTED]
Re: AES counter mode
Michael Sierchio wrote: Using AES Counter Mode With IPsec ESP - This mandates a 32-bit counter, requiring rekeying after 2^48 octets of stream material. Ah, this is interesting. Considering that OpenSSL is not only used for SSL / TLS encryption, and the mentioned RFC proposes to use a 32 bit counter and a 96 bit nonce, whereas other specs (NIST SP 800-38A) as you mention propose a 64 bit counter and a 64 bit nonce, it might be good to expose these differences in the interface of the crypto function and leave this choice to the caller. There also should be an error condition indicating that no further plaintext can be encoded unless a new key and nonce were generated (i.e. in an SSL/TLS context, a new handshake is required). Using AES Counter Mode With IPsec ESP - This mandates a 32-bit counter, requiring rekeying after 248 octets of stream material. The counter would overflow after the transmission of 2**32 blocks, a block being 2**4 octets (128 bits, 16 octets), so rekeying should be necessary after 2**36 octets (= 64 GB). http://www.ietf.org/internet-drafts/draft-ietf-ipsec-ciph-aes-ctr-04.txt Argument: let's write an Internet draft that describes the use of AES CTR mode in SSLv3/TLSv1. We can do it however we like, modulo the usual criticism and review in the IETF working group(s). I'd support that, too. If this is done, I would propose to follow the ipsec draft as much as possible (and RFC 3268 of course, which extended TLS/SSL for AES originally - http://www.ietf.org/rfc/rfc3268.txt). There is no need to reinvent the wheel, and the 96 bit nonce / 32 bit counter is indeed appropriate for the bulk of actual communication - it would be a very rare exception that even a 32 bit counter would overflow. - David __ OpenSSL Project http://www.openssl.org Development Mailing List [EMAIL PROTECTED] Automated List Manager [EMAIL PROTECTED]
Re: Re: AES counter mode
Thus spake Thierry Boivin [EMAIL PROTECTED] http://archives.seul.org/mixminion/cvs/May-2002/msg00072.html shows that the problem seems to have been submitted to the openssl team one year ago.I agree with Nick and go to the same conclusion : as the openssl aes counter mode routines wants to count by 2**64 instead of by 1, the current implementation is not correct. The source of disagreement seems to be the interpretation of a NIST document (Michael pointed such a document when replying at first). In the specification of CTR mode, as proposed for AES, you will find the statement The number /nonce/ is incremented following each encryption. I interpreted this to mean that the top 2^64 bits are to be incremented for each successive block, and this is how I implemented the code. Further review has indicated everyone else seems to think this means the nonce is incremented only between streams and it's the counter that is incremented between blocks; is there anyone out there who _disagrees_ with this? If not, it is a trivial matter to shift which bits in the counter are touched. On the matter of overflowing the lower 64 bits, this is not specifically addressed in the submission (I think they assumed nobody would exceed 2^64 blocks per stream, which is reasonable) and thus I think wrapping is the correct failure. To increment the nonce introduces a more insidious failure mode where the user unintentionally reuses nonces. Other specifications have suggested that nonce be of unspecified length, not exactly 64 bits; this implies that the lower bits wrap in an overflow condition, otherwise there would be no need to specify a boundary between the different parts of counter at all. Unfortunately, implementing this (as has been requested) would require more significant changes to the API than I know how to make,as passing parameters to a mode doesn't appear to be supported today. S Stephen Sprunk God does not play dice. --Albert Einstein CCIE #3723 God is an inveterate gambler, and He throws the K5SSSdice at every possible opportunity. --Stephen Hawking __ OpenSSL Project http://www.openssl.org Development Mailing List [EMAIL PROTECTED] Automated List Manager [EMAIL PROTECTED]
Re: AES counter mode
At 07:48 10/06/03 -0700, you wrote:
Thierry Boivin wrote:
I agree with you about the way to build the initial ctr value from the nonce
value. My question is different : whithin the encryption of a whole plaintext
message (so a big block to be divided into 128 bit length blocks) , why to increment
ctr by 2^64 instead of 1 from block to block ?
My understanding of the operation is :
- increment nonce by one from messages to messages (so this is a 2^64 step if
considering ctr)
- but for each message:
- build initial ctr from the nonce value
- increment ctr by 1 from block to block
C'est votre compréhension et non votre accord que nous attendons!
Incrementing by 2^64 is incrementing the most significant 64-bit word by 1.
Yes, but my point is why does the routine increment by 2^64 ? Because the routine
is called on a block per block basis, i was expecting a +1 step instead of such a
+2^64 step.
For those who do not only expect comprehension et non votre accord, note that
patching the code in such a purpose allows the library to be compliant with reference
vectors given in :
http://www.ietf.org/internet-drafts/draft-ietf-ipsec-ciph-aes-ctr-04.txt
modified code :
/* increment low part of a 128 bit counter by 1 */
/* big endian representation */
static void AES_ctr128_inc(unsigned char *counter) {
unsigned long c;
c = GETU32(counter + 12);
c++;
PUTU32(counter + 12, c);
/* if no overflow, we're done */
if (c)
return;
c = GETU32(counter + 8);
c++;
PUTU32(counter + 8, c);
}
Thierry Boivin
__
OpenSSL Project http://www.openssl.org
Development Mailing List [EMAIL PROTECTED]
Automated List Manager [EMAIL PROTECTED]
Re: AES counter mode
I agree with you about the way to build the initial ctr value from the nonce value. My question is different : whithin the encryption of a whole plaintext message (so a big block to be divided into 128 bit length blocks) , why to increment ctr by 2^64 instead of 1 from block to block ? My understanding of the operation is : - increment nonce by one from messages to messages (so this is a 2^64 step if considering ctr) - but for each message: - build initial ctr from the nonce value - increment ctr by 1 from block to block Thierry boivin At 07:23 06/06/03 -0700, you wrote: Thierry Boivin wrote: Hello, I am trying to play with AES crypto in counter mode. Using the crypto library against reference vectors found in IPSec RFC fails until the incrementation function (AES_ctr128_inc()) is modified in order to get a +1 step instead of a +2^64 step. Where does the actual increment by 2^64 come from ? Read the documents on AES counter mode. The counter is a 64-bit counter but the blocksize is 128, and the convention is that the counter is a Big Endian number with only the MSW used. [from Lipmaa, Rogaway Wagner] In the recommended usage scenario, the party encrypting maintains an integer counter, nonce, initially 0, and produces the string ctr as the 128-bit string which encodes the number nonce * 2^64. Don't ask me *why* it's that way -- the choice of a mere 64 bits is clearly done in order to avoid a well-known attack against stream ciphers, since one can begin to distinguish a stream from random after 2^90 or so samples. Maybe the Big Endian choice is a subtle protest against Wintel? -- Well, Brahma said, even after ten thousand explanations, a fool is no wiser, but an intelligent man requires only two thousand five hundred. - The Mahabharata __ OpenSSL Project http://www.openssl.org Development Mailing List [EMAIL PROTECTED] Automated List Manager [EMAIL PROTECTED] __ OpenSSL Project http://www.openssl.org Development Mailing List [EMAIL PROTECTED] Automated List Manager [EMAIL PROTECTED]
Re: AES counter mode
Thierry Boivin wrote: I agree with you about the way to build the initial ctr value from the nonce value. My question is different : whithin the encryption of a whole plaintext message (so a big block to be divided into 128 bit length blocks) , why to increment ctr by 2^64 instead of 1 from block to block ? My understanding of the operation is : - increment nonce by one from messages to messages (so this is a 2^64 step if considering ctr) - but for each message: - build initial ctr from the nonce value - increment ctr by 1 from block to block C'est votre compréhension et non votre accord que nous attendons! Incrementing by 2^64 is incrementing the most significant 64-bit word by 1. -- Well, Brahma said, even after ten thousand explanations, a fool is no wiser, but an intelligent man requires only two thousand five hundred. - The Mahabharata __ OpenSSL Project http://www.openssl.org Development Mailing List [EMAIL PROTECTED] Automated List Manager [EMAIL PROTECTED]
Re: AES counter mode
Thierry Boivin wrote: Hello, I am trying to play with AES crypto in counter mode. Using the crypto library against reference vectors found in IPSec RFC fails until the incrementation function (AES_ctr128_inc()) is modified in order to get a +1 step instead of a +2^64 step. Where does the actual increment by 2^64 come from ? Read the documents on AES counter mode. The counter is a 64-bit counter but the blocksize is 128, and the convention is that the counter is a Big Endian number with only the MSW used. [from Lipmaa, Rogaway Wagner] In the recommended usage scenario, the party encrypting maintains an integer counter, nonce, initially 0, and produces the string ctr as the 128-bit string which encodes the number nonce * 2^64. Don't ask me *why* it's that way -- the choice of a mere 64 bits is clearly done in order to avoid a well-known attack against stream ciphers, since one can begin to distinguish a stream from random after 2^90 or so samples. Maybe the Big Endian choice is a subtle protest against Wintel? -- Well, Brahma said, even after ten thousand explanations, a fool is no wiser, but an intelligent man requires only two thousand five hundred. - The Mahabharata __ OpenSSL Project http://www.openssl.org Development Mailing List [EMAIL PROTECTED] Automated List Manager [EMAIL PROTECTED]
Re: AES, counter mode, etc.
Thus spake John Viega: Additionally, with respect to counter mode, it might be best to implement external to the EVP proper interface, just like HMAC. There are a few issues I see that make counter mode a bit different from other modes: 1) You should be able to insert your own function for choosing a stream of counters. They don't have to be simple incrementing counters. The CTR mode proposal to NIST specifies starting a 1 and doing a simple increment. Unless other counter types are provably more secure, I prefer not to foster incompatible implementations. 2) Counter mode can be used in a random-access manner. For example, if you encrypt a file with counter mode, you can then access the blocks of that file independently, as long as you know the counter value. Good point. If you set the counter manually (instead of starting at 0), this should work properly. Were you looking for a more elegant way of doing this, or is my API broken? S -- Stephen Sprunk So long as they don't get violent, I want to CCIE #3723 let everyone say what they wish, for I myself have K5SSSalways said exactly what pleased me. --Albert Einstein __ OpenSSL Project http://www.openssl.org Development Mailing List [EMAIL PROTECTED] Automated List Manager [EMAIL PROTECTED]
Re: AES, counter mode, etc.
Thus spake John Viega: When I looked at the AES API, it looked like there was no way to specify a block size independently of the key size. Is that intentional? The NIST FIPS specifies AES with a 128-bit block size. Rijndael can be used in many other ways, but there is a significant performance loss in flexible implementations. 192- and 256-bit blocks may be added in the future, but there's higher priorities at the moment. Additionally, with respect to counter mode, it might be best to implement external to the EVP proper interface, just like HMAC. There are a few issues I see that make counter mode a bit different from other modes: Already under discussion, though in reference to ALL modes :) S -- Stephen Sprunk So long as they don't get violent, I want to CCIE #3723 let everyone say what they wish, for I myself have K5SSSalways said exactly what pleased me. --Albert Einstein __ OpenSSL Project http://www.openssl.org Development Mailing List [EMAIL PROTECTED] Automated List Manager [EMAIL PROTECTED]
Re: AES, counter mode, etc.
John Viega wrote: Additionally, with respect to counter mode, it might be best to implement external to the EVP proper interface, just like HMAC. There are a few issues I see that make counter mode a bit different from other modes: 1) You should be able to insert your own function for choosing a stream of counters. They don't have to be simple incrementing counters. 2) Counter mode can be used in a random-access manner. For example, if you encrypt a file with counter mode, you can then access the blocks of that file independently, as long as you know the counter value. That could be handled by passing the relevant info in a cipher ctrl call in the same way that other cipher parameters can be changed. The HMAC stuff could conceivable also be handled with ctrls at the digest level. However the ctrl functionality doesn't exist at the digest level at present and the HMAC stuff has been around since the SSLeay days. Steve. -- Dr Stephen N. Henson. http://www.drh-consultancy.demon.co.uk/ Personal Email: [EMAIL PROTECTED] Senior crypto engineer, Gemplus: http://www.gemplus.com/ Core developer of the OpenSSL project: http://www.openssl.org/ Business Email: [EMAIL PROTECTED] PGP key: via homepage. __ OpenSSL Project http://www.openssl.org Development Mailing List [EMAIL PROTECTED] Automated List Manager [EMAIL PROTECTED]
