Subject: [Cfrg] How to brake bMAC-TS ?

From: Pascal Urien <[email-masked]>
Date: Fri, 13 Dec 2019 14:31:12 +0100

Hi All
Is there something wrong in these assumptions, in other words how to break
this algorithm i.e. time stamped bMAC (bMAC-TS, more details in
https://tools.ietf.org/html/draft-urien-core-bmac-05)
M is a memory space, in a Harvard computing architecture context, with m
byte addresses A(x) from 1 to m. The memory is fully written with a known
content. The code is stored in the memory.
q is a safe prime q=2p+1 (p is prime) and  q>m. There are p-1 generators of
order q-1 in Z/qZ*.
This p-1 generators are used to compute permutations Pg such as Pg(x)= g**x
mod q, x and Pg(x) in [1,q-1]
hash is a digest function (SHA2, SHA3, …).
The bMAC (bijective MAC) is defined as :
bMAC = h( A(Pg(1)) || A(Pg(2)) || ... A(Pg(m)) ), A(x) is empty (not used)
for Pg(x)>m
For example for 256 bits hash functions, the global size of possible
results is (p-1).32 bytes= 16q-48 > m. So the memory cannot store all the
p-1 possible results.
Therefore if bMAC is computed by a non genuine software, a
compression/decompression algorithm must be used, in order to compute a
particular bMAC.
The time stamped bMAC (bMAC_TS) is the exclusive or (exor) with the
computing time (CT).
bMAC-TS = bMAX exor CT
The computing time (CT) is dependent on the permutation (Pg).
Claim: a non genuine software, is not able to compute a correct bMAC-TS
value
Thoughts ?