[Cfrg] How to brake bMAC-TS ?

Pascal Urien <pascal.urien@gmail.com> Fri, 13 December 2019 13:31 UTC

Return-Path: <pascal.urien@gmail.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost []) by ietfa.amsl.com (Postfix) with ESMTP id CC611120048 for <cfrg@ietfa.amsl.com>; Fri, 13 Dec 2019 05:31:24 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.997
X-Spam-Status: No, score=-1.997 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id r3Q_B3__mRZi for <cfrg@ietfa.amsl.com>; Fri, 13 Dec 2019 05:31:23 -0800 (PST)
Received: from mail-ua1-x92e.google.com (mail-ua1-x92e.google.com [IPv6:2607:f8b0:4864:20::92e]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 6C03712003F for <cfrg@irtf.org>; Fri, 13 Dec 2019 05:31:23 -0800 (PST)
Received: by mail-ua1-x92e.google.com with SMTP id d8so770436uak.9 for <cfrg@irtf.org>; Fri, 13 Dec 2019 05:31:23 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:from:date:message-id:subject:to; bh=utMkw0eGGH2S+11G48fw01lNGazPd6j01JA+6t0dqfQ=; b=C5FwP+RTorRyFsdD9mW4wM/EevO820Yminx6dQlos1WfdIsQ/+IsVNi9RGZd1BiPlF Y0zuPBFnWDoZpd0rZCmfQyT/cycSs2f6X6bnUtiDXu04h0ohjPhF7DFcyXg5CIN544XQ AJ+W+TisCIaE630Gv26k20OduiW1AA1Ket7xq05imZ4235kxpvS0uVy+BffFgfOf2QSO WqtmoRDh0PRNlxb7MaHyOaOuFkjU1VvrNx0P/5KZ7r8xLBiqvNiAFpXiKsz5cgOLahYp H45MFsfcXewS6NhMrTXo/Q2Qgu7ahW9qfijXnm63ieUr51ZdQXKTFnbm9XeMmrF11yL0 07MA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:from:date:message-id:subject:to; bh=utMkw0eGGH2S+11G48fw01lNGazPd6j01JA+6t0dqfQ=; b=ApkcjUDa4FuovkLAyyneNB0myfWv1AXMw3zRm7GPnFhFKKA3ElWwrK5LNbq/pBP3IO jRBX1ejKaJtA+GLdQL9nnwJ95RgTu136uxnGIoSEyNT2PpWwiaW3CxZ8KEUgiSWJYShD reKat8sIn76lgf+Que20KJIYPd3V4RZgyYdR254J+rh9y8PfonLB61nWcQ2Q4ynu+FE/ xhtDvHOtszhejT2Ie0vj0MFdQZh8bLAZc/Fg26882Rrmi6Y08Co8svSsug2ep3FJDwLV YBc1VizwtbUSIGL0EKwE4S/D6UOQwky3ktgbPqcA9Z6jzXD5vEtFzhl606OnhEWy1iKM v+KA==
X-Gm-Message-State: APjAAAUWkuHVCGr/qxzu/l/YI/y55LNe8+5c3fX5UfsNh/efrROaszjk DJGx3LaIbf1kHDZc5c50wBsQKGnuStD+T4srz54JIHUg0bI=
X-Google-Smtp-Source: APXvYqzk8tbbHPmun6E1hX+YBTdaBlReyx8dViSrO2NEfpvOcQrvjyRSVhL4po0N107VQJZgqL6szzGxdBoWawXQTGg=
X-Received: by 2002:ab0:3387:: with SMTP id y7mr12586169uap.99.1576243881941; Fri, 13 Dec 2019 05:31:21 -0800 (PST)
MIME-Version: 1.0
From: Pascal Urien <pascal.urien@gmail.com>
Date: Fri, 13 Dec 2019 14:31:12 +0100
Message-ID: <CAEQGKXTnFbC_K42m1nB5eSkevK014a7eCjnkD-9aCsjYD1gu+A@mail.gmail.com>
To: cfrg@irtf.org
Content-Type: multipart/alternative; boundary="000000000000a99de5059995e031"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/T5W-QyM-lJt60iyxDMNmF1zGygc>
Subject: [Cfrg] How to brake bMAC-TS ?
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Fri, 13 Dec 2019 13:31:25 -0000

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
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
Thoughts ?