RFR 8181594: Efficient and constant-time modular arithmetic

Xuelei Fan xuelei.fan at oracle.com
Tue Mar 20 15:22:47 UTC 2018

I have no other comments.


On 3/20/2018 7:50 AM, Adam Petcher wrote:
> Latest webrev: http://cr.openjdk.java.net/~apetcher/8181594/webrev.02/
> Comments inline below.
> In addition, I also changed the name of IntegerModuloP_Base to 
> IntegerModuloP, and IntegerModuloP to ImmutableIntegerModuloP.
> On 3/11/2018 12:04 PM, Xuelei Fan wrote:
>> On 2/26/2018 10:39 AM, Adam Petcher wrote:
>>> On 2/23/2018 12:46 PM, Xuelei Fan wrote:
>>>> ArrayUtil.java:
>>>> ===============
>>>> I'm not very sure how widely this utilities will be used in the 
>>>> future. Looks like only BigIntegerModuloP uses this classes.  I may 
>>>> prefer to define private methods for byte array swap in 
>>>> BigIntegerModuloP.
>>> It is also used by XDHPublicKeyImpl (in the XDH code review). XDH 
>>> public keys are represented as BigInteger, and I use the array 
>>> reverse method to convert encoded keys to BigInteger.
>> If it is not widely used by other classes, please have these methods 
>> in the class where is get called.   The sun.security.util is exported 
>> to other modules as well, we may not want to add stuff into this 
>> package unless it is really necessary.
> Okay. I put these methods in BigIntegerModuloP and removed the ArrayUtil 
> class. This array reverse code will be duplicated where it is used by 
> XDH public keys (in the other code review).
>>>> MutableIntegerModuloP.java
>>>> ==========================
>>>> void conditionalSwapWith(MutableIntegerModuloP b, int swap);
>>>> As the 'swap' parameter can only be 0 or 1, could it be a boolean 
>>>> parameter?
>>> I couldn't come up with a way to implement this without branching 
>>> when the swap parameter is boolean. See 
>>> IntegerPolynomial.conditionalSwap to see how this is implemented in 
>>> arithmetic with an int swap argument. If you (or anyone) can think of 
>>> a way to do this with boolean, let me know.
>>> I added a sentence to the comment above conditionalSwapWith that 
>>> describes why it is an int instead of a boolean.
>> I did not get the point about the need to avoid branching.  Can you 
>> have more details?
> The goal is to avoid things like if(secret){...}, in order to prevent 
> the secrets from leaking into side channels (mostly timing and cache). 
> The way this method is used by XDH, the swap parameter is a single bit 
> of the private key. By storing this bit as an integer, and then doing 
> the swap using only integer arithmetic, we can avoid branching which may 
> leak the bits of the key.
>>>> Except the conditionalSwapWith() method, I did not get the points 
>>>> why we need a mutable version.  Would you please have more 
>>>> description of this requirement?
>>> The comment above the class definition has this sentence:
>>> "This interface can be used to improve performance and avoid the 
>>> allocation of a large number of temporary objects."
>>> Do you need more information than this in the comments? The 
>>> performance motivation is so that a.add(b).multiply(c)... can be done 
>>> without allocating a new buffer for each operation. For example, 
>>> without mutable field elements, an X25519 point multiplication would 
>>> allocate around 4,300 temporary arrays totaling 350,000 bytes. If I 
>>> remember correctly, switching the X25519 implementation to mutable 
>>> field elements reduced the point multiplication time by about half.
>> I see your point.  The benefits is obviously.
>> OK, why you need the immutable version then? Sounds like the mutable 
>> version interface is sufficient, including performance. If an 
>> immutable version is really needed, we can have the implementation 
>> making the decision.  Accordingly, the conditionalSwapWith() can be 
>> defined as optional method, if it is not required to be implemented in 
>> immutable implementation.
>> It's confusing to me that the immutable and mutable and the base 
>> versions/interfaces mixed together.  It would be nice if we can 
>> simplify the interface a little bit.
>> For internal APIs, sometimes we don't want the same quality level as 
>> public APIs.  I think this set of class will be widely used by new EC 
>> curves, ChaCha20/Poly1305, or more in the future.  It would be nice if 
>> we could do it good at the beginning.
> The mutable version adds the conditional swap as well as mutable 
> versions of many of the basic operations. The XDH implementation uses 
> both the mutable and immutable versions. The immutable version allows me 
> to simplify the client code because I don't have to worry about whether 
> some value has been modified. For example, the XDH code keeps a 
> representation of 0, 1, and the constant that defines the curve as 
> immutable values.
> So I prefer to have both. It complicates this API a bit, but it allows 
> simpler and more robust code in the client of this API.
>>>> IntegerModuloP_Base.java
>>>> ========================
>>>> default byte[] addModPowerTwo(IntegerModuloP_Base b, int len)
>>>> void addModPowerTwo(IntegerModuloP_Base b, byte[] result);
>>>> For the first sign of the method names, I thought it is to calculate 
>>>> as "(this + b) ^ 2 mod m". 
>>> To be precise, it calculates "((this % p) + (b % p)) % 2^m" (where p 
>>> is the prime that defines the field, and m is the desired length, in 
>>> bits). Note that the addition here is normal integer addition (not 
>>> addition in GF(p)).
>>> This operation is not used in XDH, but it is used in Poly1305 to add 
>>> the AES encryption of a nonce to a field element. So you can get more 
>>> information about this operation by reading the Poly1305 paper/RFC.
>> I was not meant to say the function of the method.  I meant that the 
>> method name is a little bit misleading, not very straightforward to me.
>>>> Besides, what's the benefits of the two methods?  Could we just use:
>>>>       this.add(b).asByteArray()
>>> No, because that would calculate "((this + b) mod p) mod 2^m". The 
>>> value of (this + b) can be larger than p, so this would not produce 
>>> the desired result.
>>>  >>
>>>> I guess, but not very sure, it is for constant time calculation. If 
>>>> the function is required, could it be renamed as:
>>>>       // the result is inside of the size range
>>>>       IntegerModuloP addModSize(IntegerModuloP_Base b, int size)
>>>> Or
>>>>       // the result is wrapped if outside of the size range
>>>>       IntegerModuloP addOnWrap(IntegerModuloP_Base b, int size)
>>>> and the use may look like:
>>>>       this.addModSize(b, size).asByteArray()
>>> Any attempt to perform the addition in IntegerModuloP and then pull 
>>> out the byte array will not work.
>> Does it mean if I perform a addition, and cannot get the byte array in 
>> the following step?
>>      that = this.add(b);
>>      byte[] bs = that.asByteArray();           // does not work?
>> or
>>      byte[] bs = that.asByteArray(length);    // does not work?
>> or
>>      byte[] bs = that.asByteArray(byteArray); // does not work?
>>> This class can only represent field elements, so the sum would be in 
>>> the field, which is not what we want.
>> I did not get the point.  If getting an add result, the add is done 
>> (sum in the field).  Did you have an example that pulling out the byte 
>> array will not work?
> Say we are in the field of integers modulo 269, and the final result of 
> some computation will be stored in a single byte. In this example, we 
> discard information when we truncate to the byte array. This may seem 
> strange, but it is exactly what Poly1305 does. Now say we want to add x 
> with itself, and x has the value 260.
> // x.add(x) has value 251
> byte[] result = new byte[1];
> x.add(x).asByteArray(result); // result has value 251
> x.addModPowerTwo(x, result) // result has value 8
> The difference between the two statements above is that the first one 
> does a reduction mod 269 after the addition (and before converting to a 
> byte array), while the second one does not. I can't split addModPowerTwo 
> into two method calls without also adding another type for integers 
> modulo a possibly-non-prime, and I didn't think it was worth the effort.
> I don't have a problem with renaming the method if you think this will 
> make it more clear. Let me know which name you prefer. The name 
> addModSize is probably okay, although technically we are reducing mod 
> 2^size, so the name might be slightly misleading. Maybe something a 
> little less precise like addToSize?

More information about the core-libs-dev mailing list