search

miscreant / meta

Meta-repository for Miscreant: misuse-resistant symmetric encryption library with AES-SIV (RFC 5297) and AES-PMAC-SIV support
https://miscreant.io
Other
474 stars 27 forks source link

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

Open href opened 6 years ago

href commented 6 years ago

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 commented 6 years ago

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 commented 6 years ago

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.