Table-based CTZ implementation (used to implement PMAC in JS, Python, and Ruby) does not support large messages

[href]

Using AES-PMAC-SIV with Python 3.6 as follows produces as an error:

from miscreant.aead import AEAD
from secrets import token_bytes

aead = AEAD('AES-PMAC-SIV', key=b'0'*64)

# this works:
aead.seal(token_bytes(1024*4), nonce=b'0' * 16)

# this fails:
aead.seal(token_bytes(1024*5), nonce=b'0' * 16)

Traceback (most recent call last):
  File "error.py", line 5, in <module>
    aead.seal(token_bytes(1024*5), nonce=b'0' * 16)
  File "/Users/denis/.virtualenvs/spare/lib/python3.6/site-packages/miscreant/aead.py", line 60, in seal
    return self.siv.seal(plaintext, [associated_data, nonce])
  File "/Users/denis/.virtualenvs/spare/lib/python3.6/site-packages/miscreant/aes/siv.py", line 47, in seal
    v = self.__s2v(associated_data, plaintext)
  File "/Users/denis/.virtualenvs/spare/lib/python3.6/site-packages/miscreant/aes/siv.py", line 114, in __s2v
    mac.update(plaintext[:difference])
  File "/Users/denis/.virtualenvs/spare/lib/python3.6/site-packages/miscreant/mac/pmac.py", line 118, in update
    self.__process_buffer()
  File "/Users/denis/.virtualenvs/spare/lib/python3.6/site-packages/miscreant/mac/pmac.py", line 145, in __process_buffer
    self.offset.xor_in_place(self.l[ctz.trailing_zeroes(self.counter + 1)])
  File "/Users/denis/.virtualenvs/spare/lib/python3.6/site-packages/miscreant/ctz.py", line 25, in trailing_zeroes
    return CTZ_TABLE[value]
IndexError: list index out of range

With AES-SIV this error does not occur.

[tarcieri]

Oh my, yes the table-based CTZ implementation used for PMAC is completely bogus for this purpose, at least unless it were to be iterated modulo the the table size when it overflows like this.

That said, I have been meaning to go through all of the implementations of CTZ in languages that don't provide an intrinsic for it (which is Python, Ruby, and JavaScript, as Go and Rust provide one) and replace them with with a method based on De Bruijn sequences, which IMO is the "proper" solution.

If you don't mind, I'll hijack this ticket as a tracking issue for that...

[href]

If you don't mind, I'll hijack this ticket as a tracking issue for that...

Sure, go ahead. I just wanted to make sure to report this, especially since it's rather simple to reproduce.