RFR 8181594: Efficient and constant-time modular arithmetic

[Adam Petcher]

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?