Re: [Cfrg] Point format endian (was: Adoption of draft-ladd-spake2 as a RG document)
"D. J. Bernstein" <djb@cr.yp.to> Wed, 28 January 2015 02:29 UTC
Return-Path: <djb-dsn2-1406711340.7506@cr.yp.to>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 344FF1A1B24 for <cfrg@ietfa.amsl.com>; Tue, 27 Jan 2015 18:29:53 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 3.496
X-Spam-Level: ***
X-Spam-Status: No, score=3.496 tagged_above=-999 required=5 tests=[BAYES_50=0.8, HELO_EQ_NL=0.55, HOST_EQ_NL=1.545, J_CHICKENPOX_64=0.6, UNPARSEABLE_RELAY=0.001] autolearn=no
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id g8NmYf9hdoGp for <cfrg@ietfa.amsl.com>; Tue, 27 Jan 2015 18:29:51 -0800 (PST)
Received: from calvin.win.tue.nl (calvin.win.tue.nl [131.155.70.11]) by ietfa.amsl.com (Postfix) with SMTP id 171221A00A8 for <cfrg@irtf.org>; Tue, 27 Jan 2015 18:29:50 -0800 (PST)
Received: (qmail 24548 invoked by uid 1017); 28 Jan 2015 02:30:10 -0000
Received: from unknown (unknown) by unknown with QMTP; 28 Jan 2015 02:30:10 -0000
Received: (qmail 10932 invoked by uid 1000); 28 Jan 2015 02:29:32 -0000
Date: Wed, 28 Jan 2015 02:29:32 -0000
Message-ID: <20150128022932.10930.qmail@cr.yp.to>
From: "D. J. Bernstein" <djb@cr.yp.to>
To: cfrg@irtf.org
Mail-Followup-To: cfrg@irtf.org
In-Reply-To: <9A043F3CF02CD34C8E74AC1594475C73AAF65EBB@uxcn10-tdc05.UoA.auckland.ac.nz>
MIME-Version: 1.0
Content-Type: text/plain; charset="utf-8"
Content-Disposition: inline
Content-Transfer-Encoding: 8bit
Archived-At: <http://mailarchive.ietf.org/arch/msg/cfrg/nV77hg7YDIm1gZM8T1QZSg29Wb0>
Subject: Re: [Cfrg] Point format endian (was: Adoption of draft-ladd-spake2 as a RG document)
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Wed, 28 Jan 2015 02:29:53 -0000
Peter Gutmann writes: > Looking at BN_bn2bin()/BN_bin2bn() from one > widely-used library that powers half the Internet (and mobile phone market), > it only supports the big-endian format. To evaluate this "support" claim, let's try writing actual code using BN_bn2bin() to print a 256-bit x-coordinate as a 32-byte binary string: BIGNUM *x = 0; char xstr[32]; ... BN_bn2bin(x,xstr); fwrite(xstr,1,32,stdout); Let's assume that the (omitted) code computing x guarantees that x is between 0 and 2^256-1 so that there isn't a buffer overflow here; assume that the fwrite() doesn't fail; etc. This code will pass typical test vectors. However, if you do thousands of random tests under valgrind etc., then you'll see that this code is simply wrong: integers x below 2^248 fail to write anything to the last byte of xstr. The number of bytes touched by BN_bn2bin() is the minimum number of bytes _needed_ for x, whereas what we want is exactly 32 bytes. Second try. Let's clear xstr before calling BN_bn2bin(): BIGNUM *x = 0; char xstr[32]; ... memset(xstr,0,32); BN_bn2bin(x,xstr); fwrite(xstr,1,32,stdout); This now passes memory tests---but it's still wrong, as sufficiently comprehensive correctness tests will show. The problem is again with the occasional integers x below 2^248: there's a difference between * the variable-size "big-endian" BN_bn2bin() format, aligning the first byte of output with the most significant byte used in x; and * the intended constant-size "big-endian" format, aligning 32 bytes of output with 32 bytes in x, no matter which bytes of x are 0. Notice that this discrepancy is very much tied to the use of big-endian: if the BN functions and target format had been little-endian then this code _would_ have worked. If you're thinking "Wait a minute, isn't there a symmetry between little-endian and big-endian?": Yes, there is, but this is tied to the symmetry between the convention of pointing to arrays via their _first_ element and the convention of pointing to arrays via their _last_ element. In the real world, machine languages and assembly languages and C and so on have all converged upon the first convention by default, and trying to fight this is silly. Third try, now that we understand how severe the mismatch is between the OpenSSL API and the target. Let's call an auxiliary OpenSSL function so that we can figure out where we're supposed to put the first byte of x: BIGNUM *x = 0; char xstr[32]; ... memset(xstr,0,32); BN_bn2bin(x,xstr + 32 - BN_num_bytes(x)); fwrite(xstr,1,32,stdout); This always works (I think---I'm not an OpenSSL expert), and it seems to be what Peter is alluding to when he tells us that OpenSSL "supports the big-endian format". For comparison, here's code that uses exactly the same OpenSSL functions but reverses the order of output bytes: BIGNUM *x = 0; char xstr[32]; int i; ... memset(xstr,0,32); BN_bn2bin(x,xstr + 32 - BN_num_bytes(x)); for (i = 31;i >= 0;--i) putchar(xstr[i]); For some reason Peter doesn't call this "support" for little-endian. I suppose he could argue that this code is marginally more complex than the previous code; but calling this a lack of "support"---and claiming that it's a serious argument for choosing one format over another---is quite a severe exaggeration of a tiny code change. The difference between little-endian and big-endian is much more noticeable for people doing serious size optimization of crypto code (e.g., complete crypto libraries in <20KB of compiled code). These people would never tolerate the ludicrously bloated code shown above: it's crazy to use three functions to create a 32-byte copy of something that should already be sitting in memory in the first place. These people are happiest when the CPU, via the ABI, has easy instructions to handle the I/O format---and at the CPU+ABI levels it's clear that the religious war is over: * The big-endian CPUs have been killed by the little-endian CPUs and the agnostic CPUs. * For agnostic CPUs the big-endian ABIs are rapidly being replaced by little-endian ABIs. I'm not saying that the resulting code-size benefit is very large; I'm just saying that it outweighs the miniscule benefits of what some people here are calling "tradition". ---Dan
- Re: [Cfrg] Point format endian (was: Adoption of … Dan Brown
- Re: [Cfrg] Point format endian (was: Adoption of … Peter Gutmann
- Re: [Cfrg] Point format endian (was: Adoption of … Alyssa Rowan
- Re: [Cfrg] Point format endian (was: Adoption of … Alyssa Rowan
- Re: [Cfrg] Point format endian (was: Adoption of … Michael Clark
- Re: [Cfrg] Point format endian (was: Adoption of … Michael Clark
- Re: [Cfrg] Point format endian (was: Adoption of … Watson Ladd
- Re: [Cfrg] Point format endian (was: Adoption of … Michael Clark
- Re: [Cfrg] Point format endian (was: Adoption of … Peter Gutmann
- Re: [Cfrg] Point format endian (was: Adoption of … Stephen Farrell
- Re: [Cfrg] Point format endian (was: Adoption of … Peter Gutmann
- Re: [Cfrg] Point format endian (was: Adoption of … Alyssa Rowan
- Re: [Cfrg] Point format endian (was: Adoption of … Stephen Farrell
- Re: [Cfrg] Point format endian (was: Adoption of … Peter Gutmann
- Re: [Cfrg] Point format endian (was: Adoption of … Stephen Farrell
- Re: [Cfrg] Point format endian (was: Adoption of … Salz, Rich
- Re: [Cfrg] Point format endian Derek Atkins
- Re: [Cfrg] Point format endian Salz, Rich
- Re: [Cfrg] Point format endian Stephen Farrell
- Re: [Cfrg] Point format endian Paul Hoffman
- Re: [Cfrg] Point format endian Derek Atkins
- Re: [Cfrg] Point format endian Derek Atkins
- Re: [Cfrg] Point format endian Blumenthal, Uri - 0558 - MITLL
- Re: [Cfrg] Point format endian Paul Hoffman
- Re: [Cfrg] Point format endian Watson Ladd
- Re: [Cfrg] Point format endian (was: Adoption of … Dan Harkins
- Re: [Cfrg] Point format endian (was: Adoption of … Watson Ladd
- Re: [Cfrg] Point format endian (was: Adoption of … Andy Lutomirski
- Re: [Cfrg] Point format endian (was: Adoption of … Dan Harkins
- Re: [Cfrg] Point format endian (was: Adoption of … Stephen Farrell
- Re: [Cfrg] Point format endian Tony Arcieri
- Re: [Cfrg] Point format endian (was: Adoption of … Michael Clark
- Re: [Cfrg] Point format endian Damien Miller
- Re: [Cfrg] Point format endian Phillip Hallam-Baker
- Re: [Cfrg] Point format endian Phillip Hallam-Baker
- Re: [Cfrg] Point format endian (was: Adoption of … Watson Ladd
- Re: [Cfrg] Point format endian (was: Adoption of … D. J. Bernstein
- Re: [Cfrg] Point format endian (was: Adoption of … Dan Harkins
- Re: [Cfrg] Point format endian (was: Adoption of … Watson Ladd