Re: IBM press release - encryption and authentication
David Wagner wrote: Enzo Michelangeli wrote: OpenPGP tries to detect such "wrong key" situations for symmetrically-encrypted packets in a pretty simplistic way, [...] The repetition of 16 bits in the 80 bits of random data prefixed to the message allows the receiver to immediately check whether the session key is incorrect. This does not provide message integrity or message authentication. It provides a much weaker property: If you've decrypted with the wrong key, this will let you detect that fact. Padding also does that, of course. Cheers, Ben. -- http://www.apache-ssl.org/ben.html "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
Re: IBM press release - encryption and authentication
-BEGIN PGP SIGNED MESSAGE- David Wagner wrote: History shows that it is extremely easy to propose schemes for encryption-with-integrity that are plausible-looking yet nonetheless entirely broken. At this point, I don't think I would trust very much a proposal without a proof. For example, the chaining scheme used by Kerberos? Never-the-less, engineers traditionally propose incremental improvements, standing as it were on the shoulders of giants And I think it would be fair to say that CBCS falls into the camp of plausible but unproven proposals. (Correct me if I'm wrong!) Well, had you attended the particular conferences, you'd have heard the rationale. And the design notes in the documents describe the specifics. I'm not a crypto-mathematician, and I make no claim as to the sufficiency of proofs. You did review one of the early drafts of CBCS. In the other case, enhancing XEX-CBC, you provided a major amount of improved text regarding Replay Protection in an earlier part of the same paper, and agreed to be a named co-author. Presumably, had a proof been available at the time, you would have pointed to it However, as is often the case, later scholars have verified both schemes (for their own purposes)! CBCS has several security notes, summarized here: 1) the authentication/integrity function is separately keyed, rather than from the encryption function. 2) the IV feeds the CBCS function, which then feeds the encryption function, to generate unpredictable initial values for the first cipher block. 3) the IV is intended to be unique over the lifetime of the cipher session-key(s). 4) the IV incorporating the ESP Security Parameters Index (SPI) and the anti-replay ESP Sequence Number (SN) together can provide both uniqueness and mutual protection between the first block and the ESP header. 5) prevent linear cryptanalysis by incorporating a non-linear rotation function. This is specific to my choice for the authentication/integrity function, namely the combination of addition (sum) with a variable rotation. As CBCS was based on earlier schemes that XOR a key and/or previous ciphertext block with the next plaintext and/or ciphertext block, CBCS has the simple unstated assumption that the output of the cipher is uniformly distributed and unpredictable. That is, it probably is secure only when used with a robust cipher. I should have explicitly stated that -- I merely referenced it in other papers. Since then, somebody else has written a formal proof for the generic class of g(x) functions in the same or similar construction as CBCS. He presented at IETF last year. I'm sorry, I've never read the paper. I was incensed that he claimed a patent on his particular variant of the idea. XEX-CBC "whitening" in draft-simpson-ipsec-enhancement has a very simple stated security limitation: "It is insecure without combination with a robust cipher." The only reason that DES-XEX3-CBC wasn't adopted as the default cipher by IETF in 1995 was that there was no formal proof of its security. Likewise, the substitution of a PRNG, or one-way hash function as a PRNG, for the fixed secret(s) in XEX2 or XEX3, depends on the security of the underlying cipher. Since then, as referenced in my later XEX3-CBC Transform papers, Rogaway did an analysis of the security in 1996. The upshot of this exercise is that we have proposals developed in open fora that are patent free. We don't need to rely on patented variants. While I am thankful that later analysts have more rigorous proofs of security, I don't believe that the proofs are patentable. Moreover, I think that we should discourage scholars holding back on design publication in order to secure patent rights -- especially in the "information age", publish early and often! -BEGIN PGP SIGNATURE- Version: PGP 6.5.1 iQCVAwUBOj4x/Nm/qMj6R+sxAQHQwAP/Rz4IqjupVkvr89tQukyYBWVh3w4YQriv LGfFaOkweWJgDUeugxTRvfVhuxe61C9KKdJYTo5N+9wt/mVdxqJ14n/CT4sxwAek gE9iaRx1QlXLpQQSz1QOF/i3IRih6LDQRRrl4QGFWbpI3bV5i2kAl8E7NzDBz7+J i44awIe4m+c= =9kr9 -END PGP SIGNATURE-
Re: IBM press release - encryption and authentication
Enzo Michelangeli wrote: OpenPGP tries to detect such "wrong key" situations for symmetrically-encrypted packets in a pretty simplistic way, [...] The repetition of 16 bits in the 80 bits of random data prefixed to the message allows the receiver to immediately check whether the session key is incorrect. This does not provide message integrity or message authentication. It provides a much weaker property: If you've decrypted with the wrong key, this will let you detect that fact. For message integrity or authentication, it seems that you need either a full-blown MAC or else some scheme like Charanjit Jutla's.
Re: IBM press release - encryption and authentication
William Allen Simpson wrote: As far as I can tell, the only unique element is the mod 2^128 - 159 function. We just need to use another function. My own favorite (in CBCS) has been rotation by the population count [...] The uniquely valuable aspect of Jutla's scheme (and other related schemes, e.g. Gligor's or Rogaway's schemes) is that it comes with a proof of security. History shows that it is extremely easy to propose schemes for encryption-with-integrity that are plausible-looking yet nonetheless entirely broken. At this point, I don't think I would trust very much a proposal without a proof. And I think it would be fair to say that CBCS falls into the camp of plausible but unproven proposals. (Correct me if I'm wrong!)
Re: IBM press release - encryption and authentication
- Original Message - From: "David Wagner" [EMAIL PROTECTED] Newsgroups: isaac.lists.cryptography To: Sent: Monday, December 18, 2000 9:14 AM Subject: Re: IBM press release - encryption and authentication Enzo Michelangeli wrote: OpenPGP tries to detect such "wrong key" situations for symmetrically-encrypted packets in a pretty simplistic way, [...] The repetition of 16 bits in the 80 bits of random data prefixed to the message allows the receiver to immediately check whether the session key is incorrect. This does not provide message integrity or message authentication. It provides a much weaker property: If you've decrypted with the wrong key, this will let you detect that fact. Why? It will also let you detect if someone has tampered with the ciphertext in a block containing the redundant information (or preceding it, unless ECB is used). Also, if the identity of the sender is proved by the knowledge of the encryption key (which was my assumption in the post you quote) a successful decryption will additionally prove the authenticity of the message. Enzo
Re: IBM press release - encryption and authentication
Ray Dillinger writes: I may be misunderstanding what you are suggesting, but the construction that uses an encrypted CRC as a MAC is insecure. Eg. Stubblebine Gligor[1] show attacks on protocols which encrypt the concatenation of a packet and a CRC-32 using DES-CBC. The properties of the MAC, encrypted or not, do appear to matter. Yeah. The problem with an encrypted CRC is that it's relatively easy to find another plaintext that has the same CRC, hence you can substitute a different set of bits for the document. Actually, there are problems even if you use a function that does not have this property. There is a general attack, which David Wagner just pointed out to me, that applies even if we use a collision-resistant hash function instead: suppose your authenticating code is encrypt(m||H(m)), where H is a hash function. Then there is a chosen-message attack that asks the sender to encryptauthenticate the message m=m'||H(m')||pad. Then, by taking a prefix of the message, the attacker has a valid authentication on the message m'. Now, this is a bit of an esoteric attack, but it does violate the security conditions of a MAC. My point is that a CRC, or even an unkeyed hash function, does not guarantee authenticity, only integrity. Similarly, encrypting something does not guarantee authenticity, only secrecy, because it may be possible to get an encryption of what you want in a different context. Jutla's proof of security goes to some length to ensure that this does not occur with reasonable probability. - Nikita
Re: IBM press release - encryption and authentication
On 14 Dec 2000, Nikita Borisov wrote: I think, though, that the "parallelization-friendliness" of the result is much more interesting than being able to encrypt and MAC at the same time. Encrypt and MAC together are pretty useful too - it can result in a factor of two improvement in speed on a single CPU system. There's an improved version of the IBM mode at http://csrc.nist.gov/encryption/aes/modes/ in the 'OCB mode' paper. Clearly, it's a good idea to wait for new developments to stop happening to use the new modes. -Bram Cohen "Markets can remain irrational longer than you can remain solvent" -- John Maynard Keynes
Re: IBM press release - encryption and authentication
In article 010801c064d0$b64193a0$6000a8c0@em, Enzo Michelangeli [EMAIL PROTECTED] wrote: Apart from the parallelization-friendliness, wouldn't the same result be achieved by encrypting the concatenation of the plaintext with a MAC implemented through a fast error detection code (say, a sufficiently long CRC)? Due to the presence of encryption, the security properties of the inner MAC don't appear to really matter (as they would in the "DES-CBC first, then HMAC-MD5" scenario mentioned in the draft for comparison). I may be misunderstanding what you are suggesting, but the construction that uses an encrypted CRC as a MAC is insecure. Eg. Stubblebine Gligor[1] show attacks on protocols which encrypt the concatenation of a packet and a CRC-32 using DES-CBC. The properties of the MAC, encrypted or not, do appear to matter. I think, though, that the "parallelization-friendliness" of the result is much more interesting than being able to encrypt and MAC at the same time. - Nikita [1] "On Message Security in Cryptographic Protocols", IEEE Symposium on Security Privacy, Oakland 1992.
Re: IBM press release - encryption and authentication
Apart from the parallelization-friendliness, wouldn't the same result be achieved by encrypting the concatenation of the plaintext with a MAC implemented through a fast error detection code (say, a sufficiently long CRC)? Due to the presence of encryption, the security properties of the inner MAC don't appear to really matter (as they would in the "DES-CBC first, then HMAC-MD5" scenario mentioned in the draft for comparison). Enzo - Original Message - From: "Steven M. Bellovin" [EMAIL PROTECTED] To: "P.J. Ponder" [EMAIL PROTECTED] Cc: [EMAIL PROTECTED] Sent: Saturday, December 09, 2000 8:50 AM Subject: Re: IBM press release - encryption and authentication In message [EMAIL PROTECTED], "P .J. Ponder" writes: from: http://www.ibm.com/news/2000/11/30.phtml IBM develops algorithm that encrypts and authenticates simultaneously More precisely, this is a new mode of operation that does encryption and authentication in one pass. It's also amenable to parallelization, thus making it suitable for very high speed networks. (Traditional modes of operation, such as CBC, are problematic, since every block depends on the encryption of the previous block.) --Steve Bellovin
Re: IBM press release - encryption and authentication
On Sun, 10 Dec 2000, Rich Salz wrote: No word, of course, on how the thing actually works, or whether they intend to patent it. Not so. Search your nearest IETF internet-drafts repository for draft-jutla-ietf-ipsec-esp-iapm-00.txt I was complaining about the total lack of technical detail in the press release specifically. Thanks for the pointer. -Bram Cohen
Re: IBM press release - encryption and authentication
On Sun, 10 Dec 2000, Rodney Thayer wrote: P.s, when he spoke at Stanford I asked about patents and he said it was patented, and he said NIST is trying to get them to put it in the public domain. There are slides for it online at http://csrc.nist.gov/encryption/aes/modes/slides-jutla/index.htm it's not hard to figure it out just from the slides - there are actually two methods given, one which requires an extra lg(n) encryptions and one which requires two extra encryptions but has a bunch of modular arithmetic. Rijndael is so fast I suspect the second one might not prove all that useful. It really does, as advertized, offer MAC for almost no overhead, and parallelization for free. It would be a shame for these modes to not get used because of stupid patent bullshit. -Bram Cohen (who thinks doing the xors as a gray code instead of binary countup was a nice touch.)
Re: Re: IBM press release - encryption and authentication
[EMAIL PROTECTED] wrote: The world is not so simple, not so black and white. For example, you're completely omitting any outside factors beyond the crypto algorithm itself. Such as...? (Please restrict your answer to topics pertinent to this discussion list). Oh come on. The original statement assumes that the ONLY factor entering into the intellectual property decision is that of the cryptography itself. That's ridiculous. Cost recovery, trading for rights to use something else, establishing credibility with venture capitalists, etc. Yes, the net effect *might* be: everyone can use it, or everyone cannot use it, but to claim that as *the reason* is ridiculous. I believe this explanation of the obvious is off-topic, and I won't discuss it further. /r$ It's not obvious. Note that your reply did not address or reference anything specific in the commented-upon message. You might be talking about anything -- possibly off-topic stuff. Moreover, *is* it off-topic to discuss such aspects of cryptographic technology deployment? [Making clear which what is under consideration undoubtedly helps.] Paulo Barreto. [I've filtered a lot of these messages so far. I'm happy to see a discussion of patent issues and how they impact cryptographic deployment, but I think the discussion so far has been pretty uninteresting and largely has consisted of cliches. If people want me to forward their messages about this, they're going to have to say things that are a lot more interesting. --Perry]
Re: IBM press release - encryption and authentication
Rich Salz [EMAIL PROTECTED] writes: No word, of course, on how the thing actually works, or whether they intend to patent it. Not so. Search your nearest IETF internet-drafts repository for draft-jutla-ietf-ipsec-esp-iapm-00.txt Eh? It would be bad if a patented system became an IETF standard. And if we could make such a standard, it should almost certainly be one of the other proposals heard by NIST, Galois-field OCB. [A draft does not imply an IETF standard in the making. Anyone can publish a draft, or even an RFC. --Perry] -- __ \/ o\ [EMAIL PROTECTED] /\__/ http://www.cluefactory.org.uk/paul/
Re: IBM press release - encryption and authentication
In article [EMAIL PROTECTED],
Bram Cohen [EMAIL PROTECTED] wrote:
it's not hard to figure it out just from the slides - there are actually
two methods given, one which requires an extra lg(n) encryptions and one
which requires two extra encryptions but has a bunch of modular
arithmetic. Rijndael is so fast I suspect the second one might not prove
all that useful.
But in his examples, addition mod 2^128 - 159 can be implemented rather
quickly:
S_i = S_{i-1} + b [regular 128-bit addition]
if (b S_i) S_i += 159
- Nikita
Re: IBM press release - encryption and authentication
At 05:14 PM 12/11/2000 -0800, Nikita Borisov wrote:
But in his examples, addition mod 2^128 - 159 can be implemented rather
quickly:
S_i = S_{i-1} + b [regular 128-bit addition]
if (b S_i) S_i += 159
Ahhh, yes, a classical example of premature optimisation. This is, of
course, a different definition of modular arithmetic than most people would
use.
Suppose that the result of the addition S_i falls into the range
[2^128-159 .. 2^128)
then his nice quick method gives an answer that isn't reduced at all,
whereas it really ought to be in the range [0 .. 159) by most people's
definitions of modular arithmetic.
So long as both ends use the broken method, or you aren't terribly unlucky
(since only about 1 in 2^121 calculations will hit this case), it will all
still work.
Greg.
Greg Rose INTERNET: [EMAIL PROTECTED]
Qualcomm Australia VOICE: +61-2-9181-4851 FAX: +61-2-9181-5470
Level 3, 230 Victoria Road,http://people.qualcomm.com/ggr/
Gladesville NSW 2111232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C
Re: IBM press release - encryption and authentication
Greg Rose writes:
At 05:14 PM 12/11/2000 -0800, Nikita Borisov wrote:
But in his examples, addition mod 2^128 - 159 can be implemented rather
quickly:
S_i = S_{i-1} + b [regular 128-bit addition]
if (b S_i) S_i += 159
Ahhh, yes, a classical example of premature optimisation. This is, of
course, a different definition of modular arithmetic than most people would
use.
Well, it _does_ find a number congruent to S_{i-1} + b mod (2^128-159),
which is one definition of modular addition. But you're right -- unless
both sides are using this version of the algorithm, a final reduction is
necessary to find a representation in the range [0,2^128-159). I should
have looked at his slides more carefully...
- Nikita
Re: IBM press release - encryption and authentication
In message [EMAIL PROTECTED], "P .J. Ponder" writes: from: http://www.ibm.com/news/2000/11/30.phtml IBM develops algorithm that encrypts and authenticates simultaneously More precisely, this is a new mode of operation that does encryption and authentication in one pass. It's also amenable to parallelization, thus making it suitable for very high speed networks. (Traditional modes of operation, such as CBC, are problematic, since every block depends on the encryption of the previous block.) --Steve Bellovin
Re: IBM press release - encryption and authentication
On Thu, 7 Dec 2000, P.J. Ponder wrote: from: http://www.ibm.com/news/2000/11/30.phtml IBM develops algorithm that encrypts and authenticates simultaneously No word, of course, on how the thing actually works, or whether they intend to patent it. A note to the clueful about it being 'parellelizable' - almost all crypto stuff can be parallelized by putting different tasks on different processors, since the vast majority of crypto applications have multiple tasks on a server going on at once. Parallelism works well for things which require little interaction, and not at all for things which require a lot. -Bram Cohen [Parallelism is NOT a trivial property. The maximum data rate you can sustain depends a lot on whether or not an algorithm can be implemented in parallel in hardware. Some algorithms, like various keyed hashes, have bad properties in this regard. Claiming this isn't important is just not correct -- for many applications it is. --Perry]
Re: IBM press release - encryption and authentication
On Fri, 08 Dec 2000, Bram Cohen wrote: On Thu, 7 Dec 2000, P.J. Ponder wrote: from: http://www.ibm.com/news/2000/11/30.phtml IBM develops algorithm that encrypts and authenticates simultaneously No word, of course, on how the thing actually works, or whether they intend to patent it. A description of Jutla's mode of operation is available from NIST's AES site. And yes, IBM has filed patent for it. Cheers, Paulo Barreto.
Re: IBM press release - encryption and authentication
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 this is talking about parallizing processing of an individual message. the application for this is packet processing in a protocol stack, or "lower", packet processing in hardware below+/inside the protocol stack. you can't parallelize IPsec, for example, as you can't process the HMAC at the end until you've encrypted the body. P.s, when he spoke at Stanford I asked about patents and he said it was patented, and he said NIST is trying to get them to put it in the public domain. At 10:32 AM 12/8/00 -0800, Bram Cohen wrote: No word, of course, on how the thing actually works, or whether they intend to patent it. A note to the clueful about it being 'parellelizable' - almost all crypto stuff can be parallelized by putting different tasks on different processors, since the vast majority of crypto applications have multiple tasks on a server going on at once. -BEGIN PGP SIGNATURE- Version: PGP 7.0 iQA/AwUBOjOuJz/0TyQ4fTjtEQKVZgCg714v3imy9hER3PPwGsIj4UBPaFMAoO35 ieU2BbfR4ozm/8qUbWkl5YRi =8tTs -END PGP SIGNATURE-
Re: IBM press release - encryption and authentication
On Sun, 10 Dec 2000, Paulo S. L. M. Barreto wrote: A description of Jutla's mode of operation is available from NIST's AES site. And yes, IBM has filed patent for it. Note to cryptographers of the world - there are two reasons to patent an algorithm - 1) to keep anyone else from patenting it and release it into the public domain. 2) to keep anyone from using it If you're not doing 1, you're doing 2. -Bram Cohen
Re: IBM press release - encryption and authentication
No word, of course, on how the thing actually works, or whether they intend to patent it. Not so. Search your nearest IETF internet-drafts repository for draft-jutla-ietf-ipsec-esp-iapm-00.txt And in there you will find 5. Intellectual Property Issues IBM has filed U.S. patents on this mode and its vari- ants in April, 2000. Ennui has its places, this just wasn't one of them. :) /r$
