python - How to correctly implement the multiplication function used by GHASH function in AES-256-GCM? - Stack Overflow

admin管理员组

文章数量:1383694

I am trying to implement AES-256-GCM in Python without using any external libraries, and I have implemented encryption and decryption in AES-256-ECB, AES-256-CBC, AES-256-CTR, and AES-256-OFB modes, and I also implemented Base64 encoding and decoding plus JSON serialization and deserialization, all are working properly and I have verified the results rigorously against various sources.

You can see an earlier version of my work here, I have implemented the code all by myself according to various sources.

I plan to add AES-256-CFB and AES-256-PCBC modes, it is extremely trivial for me to implement them at this point, plus I have found this, but I am not adding those modes because I am currently trying to implement AES-256-GCM which is my original goal, but I can't implement it. Currently there is no way for me to verify if my results were right.

I have found this specification and this and this.

A direct implementation of the algorithm for multiplication used in GHASH function is:

GHASH_POLY = 0xE1000000000000000000000000000000


def ghash_mul(a: int, b: int) -> int:
    c = 0
    for i in range(127, -1, -1):
        if a >> i:
            c ^= b
        
        if b & 1:
            b = (b >> 1) ^ GHASH_POLY
        else:
            b >>= 1
    
    return c

I have found this, it is easy for me to adapt the code to my needs, but I can't verify its correctness.

Specifically, the multiplication function it uses is the following:

def ghash_mult(x, y):
    res = 0
    for i in range(127, -1, -1):
        res ^= x * ((y >> i) & 1)
        x = (x >> 1) ^ ((x & 1) * GHASH_POLY)
    
    return res

I got rid of the comment and assert blocks as they weren't necessary.

For some inputs, my function agrees with the function from the linked repository, but the outputs aren't the same for all inputs:

In [354]: ghash_mul(255, 255)
Out[354]: 184305769290552241502318497701996581888

In [355]: ghash_mult(255, 255)
Out[355]: 184305769290552241502318497701996581888

In [356]: ghash_mult(12345, 255)
Out[356]: 176413478065579303506952143281585670830

In [357]: ghash_mul(12345, 255)
Out[357]: 184305769290552241502318497702000014804

In [358]: ghash_mul(MAX128, MAX128)
Out[358]: 324345477096475565862205004031948663466

In [359]: ghash_mult(MAX128, MAX128)
Out[359]: 324345477096475565862205004031948663466

In [360]: ghash_mult(999, 999)
Out[360]: 184305769290552241502318497701997396837

In [361]: ghash_mul(999, 999)
Out[361]: 237807196120895105386696731878281261212

Which one is correct? Or are they both wrong? How can I correctly implement the multiplication function used in GHASH?

I am trying to implement AES-256-GCM in Python without using any external libraries, and I have implemented encryption and decryption in AES-256-ECB, AES-256-CBC, AES-256-CTR, and AES-256-OFB modes, and I also implemented Base64 encoding and decoding plus JSON serialization and deserialization, all are working properly and I have verified the results rigorously against various sources.

You can see an earlier version of my work here, I have implemented the code all by myself according to various sources.

I plan to add AES-256-CFB and AES-256-PCBC modes, it is extremely trivial for me to implement them at this point, plus I have found this, but I am not adding those modes because I am currently trying to implement AES-256-GCM which is my original goal, but I can't implement it. Currently there is no way for me to verify if my results were right.

I have found this specification and this and this.

A direct implementation of the algorithm for multiplication used in GHASH function is:

GHASH_POLY = 0xE1000000000000000000000000000000


def ghash_mul(a: int, b: int) -> int:
    c = 0
    for i in range(127, -1, -1):
        if a >> i:
            c ^= b
        
        if b & 1:
            b = (b >> 1) ^ GHASH_POLY
        else:
            b >>= 1
    
    return c

I have found this, it is easy for me to adapt the code to my needs, but I can't verify its correctness.

Specifically, the multiplication function it uses is the following:

def ghash_mult(x, y):
    res = 0
    for i in range(127, -1, -1):
        res ^= x * ((y >> i) & 1)
        x = (x >> 1) ^ ((x & 1) * GHASH_POLY)
    
    return res

I got rid of the comment and assert blocks as they weren't necessary.

For some inputs, my function agrees with the function from the linked repository, but the outputs aren't the same for all inputs:

In [354]: ghash_mul(255, 255)
Out[354]: 184305769290552241502318497701996581888

In [355]: ghash_mult(255, 255)
Out[355]: 184305769290552241502318497701996581888

In [356]: ghash_mult(12345, 255)
Out[356]: 176413478065579303506952143281585670830

In [357]: ghash_mul(12345, 255)
Out[357]: 184305769290552241502318497702000014804

In [358]: ghash_mul(MAX128, MAX128)
Out[358]: 324345477096475565862205004031948663466

In [359]: ghash_mult(MAX128, MAX128)
Out[359]: 324345477096475565862205004031948663466

In [360]: ghash_mult(999, 999)
Out[360]: 184305769290552241502318497701997396837

In [361]: ghash_mul(999, 999)
Out[361]: 237807196120895105386696731878281261212

Which one is correct? Or are they both wrong? How can I correctly implement the multiplication function used in GHASH?

• python
• encryption
• cryptography
• aes

Share Improve this question Follow asked Apr 1 at 20:21 Ξένη ΓήινοςΞένη Γήινος 3,42411 gold badge1818 silver badges5959 bronze badges

Add a comment  | 

1 Answer 1

Sorted by: Reset to default 1

I have figured it out. It was caused by a typo.

I fot that & 1 in the first if condition, so that the condition is always true if the number is greater than 1 regardless of the ith bit's value.

I have fixed the code:

def ghash_mul(a: int, b: int) -> int:
    c = 0
    for i in range(127, -1, -1):
        if (a >> i) & 1:
            c ^= b
        
        if b & 1:
            b = (b >> 1) ^ GHASH_POLY
        else:
            b >>= 1
    
    return c

And the fixed code is correct, as is the function from the repository:

In [369]: import random

In [370]: for _ in range(65536):
     ...:     a = random.randrange(MAX128)
     ...:     b = random.randrange(MAX128)
     ...:     assert ghash_mul(a, b) == ghash_mult(a, b)

And somehow the branchless code performs worse than my naive implementation with if conditions:

In [371]: %timeit ghash_mul(a, b)
36 μs ± 746 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

In [372]: %timeit ghash_mult(a, b)
51.1 μs ± 543 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

本文标签：