CORE Working Group Working Group P. Urien
Internet Draft Telecom ParisTech
Intended status: Experimental
November 4, 2019
Expires: May 2020
Bijective MAC for Constraint Nodes
draft-urien-core-bmac-00.txt
Abstract
In this draft context, things are powered by micro controllers units
(MCU) comprising a set of memories such as static RAM (SRAM), FLASH
and EEPROM. The total memory size, ranges from 10KB to a few
megabytes.
In this context code and data integrity is a major security issue,
for the deployment of Internet of Things infrastructure. The goal of
the bijective MAC (bMAC) is to compute an integrity value, which
cannot be guessed by malicious software.
In classical keyed MAC, MAC is computing according to a fix order.
In the bijective MAC, the content of N addresses is hashed according
to a permutation P (i.e. bijective application).
The bijective MAC key is the permutation P.
The number of permutations for N addresses is N!. So the computation
of the bMAC requires the knowledge of the whole space memory; this
is trivial for genuine software, but could very difficult for
corrupted software.
Requirements Language
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC 2119.
Status of this Memo
This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet-
Drafts is at http://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six
months and may be updated, replaced, or obsoleted by other documents
at any time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
This Internet-Draft will expire on May 2020.
Urien Expires May 2020 [Page 1]
Copyright Notice
Copyright (c) 2019 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with
respect to this document. Code Components extracted from this
document must include Simplified BSD License text as described in
Section 4.e of the Trust Legal Provisions and are provided without
warranty as described in the Simplified BSD License.
Urien Expires May 2020 [page 2]
Bijective MAC for Constraint Nodes November 2019
Table of Contents
Abstract........................................................... 1
Requirements Language.............................................. 1
Status of this Memo................................................ 1
Copyright Notice................................................... 2
1 Overview......................................................... 4
2 Bijective MAC.................................................... 4
2.1 Memory space................................................ 4
2.2 Permutation................................................. 4
2.3 bMAC computation............................................ 5
2.4 Unused memory............................................... 5
2.5 Permutation entropy......................................... 5
2.6 Time-stamped bMAC........................................... 5
3. The Pq permutation family....................................... 6
3.1 How to compute generators................................... 6
3.2 Shifted permutation......................................... 7
3.3 Composition in Fq........................................... 7
3.4 Code example................................................ 7
3.4.1 Example 1 ............................................ 7
3.4.2 Example 2 ............................................ 8
4 bMAC protocol.................................................... 9
5 IANA Considerations.............................................. 9
6 Security Considerations.......................................... 9
7 References....................................................... 9
7.1 Normative References....................................... 10
7.2 Informative References..................................... 10
8 Authors' Addresses.............................................. 10
Urien Expires May 2020 [Page 3]
Bijective MAC for Constraint Nodes November 2019
1 Overview
In this draft context, things are powered by micro controllers units
(MCU) comprising a set of memories such as static RAM (SRAM), FLASH
and EEPROM. The total memory size ranges from 10KB to a few
megabytes.
In this context code and data integrity is a major security issue
for the deployment of Internet of Things infrastructure.
The goal of the bijective MAC (bMAC) is to compute an integrity
value, which cannot be guessed by malicious software.
In classical keyed MAC, MAC is computing according to a fix order.
In the bijective MAC, the content of N addresses (A[0]...A[N-1]) is
hashed according to a hash function H and a permutation P (i.e.
bijective application in [0,N-1])so that :
bMAC(A, P) = H( A[P(0)] || A[P(1)] ... || A[P(N-1)] )
The bijective MAC key is the permutation P. The number of
permutations for N addresses is N!, as an illustration 35! is
greater than 2**128. So the computation of the bMAC requires the
knowledge of the whole space memory; this is trivial for genuine
software, but could very difficult for corrupted software.
2 Bijective MAC
2.1 Memory space
The memory space is represented by an application A, working with N
addresses, whose content is a byte value.
| [0,N-1] -> [0,255]
A |
| x -> A[x]
Non volatile memories (FLASH, EEPROM) MUST be included in the memory
space. A subset of SRAM is included in the memory, whose structure
relies on operational constraints.
2.2 Permutation
For practical reasons, permutation MAY use a range of M values,
greater than the size N of the memory space.
| [0,M-1] -> [0,M-1]
P |
| x -> P(x)
For example, given a N memory space, and q a prime number so that
q>N+1, and g a generator for the group Z/qZ, the P permutation (with
M= q-1) can computed as :
Urien Expires May 2020 [Page 4]
Bijective MAC for Constraint Nodes November 2019
| [0,q-2] -> [0,q-2]
P |
| x -> g**(1+x)-1
2.3 bMAC computation
We consider a one way hash function H (such as SHA2 or SHA3) with
three procedures, H.reset, H.update, and H.final.
Given a space memory N, a permutation P with M values, the bMAC,
according to C like notation, is computed as:
H.reset() ;
for (i=0; i< M; i++)
{ if (P(i) < N)
H.update(A[P[i]);
}
bMAC= H.final();
2.4 Unused memory
Unused memory MAY be filled by pseudo random values, before
performing the bMAC computation.
2.5 Permutation entropy
A family of Pk permutations is a subset of M! existing permutations
of M elements, which is computed according to dedicated algorithms.
We note O(Pk) the number of elements of a Pk family.
The entropy is the integer e, such as 2**e is closed to O(Pk):
2**e <= O(Pk) < 2**(e+1)
The entropy of a family may be increased by the composition of Pk
functions so that :
P(k1,k2,...,kn) = Pkn o ... o Pk2 o Pk1
2.6 Time-stamped bMAC
We assume that the bMAC computing time (T) ranges between the values
Tmin and Tmax:
Tmin <= T <= Tmax
We define the following values:
Range = Tmax-Tmin+1
Urien Expires May 2020 [Page 5]
Bijective MAC for Constraint Nodes November 2019
Delta = Tmin modulo Range
For a given computing time T we define the canonical computing time
cT as :
cT = (T-Delta)/Range
For every T value, cT has a fix value equal to the quotient of
Tmin/Range.
The main interest of the canonical time is that it could work as a
secret value, deduced from the bMAC computing but not stored in the
software memory image.
The time-stamped bMAC is computed from an exor operation between the
bMAC and the canonical time:
Time-stamped bMAC = bMAC exor cT
3. The Pq permutation family
We consider a N memory space, and q a prime number so that q>N+1.
Z/qZ is a monogenous group with n=phi(q-1) generators (g), phi being
the Euler number. Generators (g) in Z/qZ can be used to build a
permutation family Pq= = {Pg1, Pg2,.., Pgn}, so that:
| [1,q-1] -> [1,q-1]
Pg(x) |
| x -> g**x
Given a P permutation working in the [1,q-1] range (such as Pg), we
use the P*(P) permutation in order to enforce compatibility with the
memory space A(x) starting at the zero address :
| [0,q-2] -> [0,q-2]
P* |
| x -> P*(x) = P(1+x)-1
3.1 How to compute generators
The group order being q-1, generators are numbers prime with q-1,
i.e. :
GCD(g,q-1)=1, GCD being the Greatest Common Divisor of two integers.
Example 1.
Memory space N = 512B EEPROM + 8192B FLASH + 1024B SRAM = 9728B
Nearest prime number q = 9733
q-1 = 9732= 811 x 4 x 3
phi(9732) = 3240
generators are numbers, less than q=9733, prime with 811, 4 and 3.
Urien Expires May 2020 [Page 6]
Bijective MAC for Constraint Nodes November 2019
Example 2.
Memory space N = 4096B EEPROM + 262144B FLASH + 1024B SRAM= 274432
prime number q = 278543
q-1= 278542 = 2 x 11**2 x 1151
phi(278542) = 126500
generators are numbers, less than q=278543, prime with 2, 11, and
1151
3.2 Shifted permutation
Given an integer s in the range [0, q-1], the shifted permutation
P(g,s) is defined as
| [1,q-1] -> [1,q-1]
P(g,s)(x) |
| x -> s.g**x
In other words P(g,s)(x) = s x Pg(x).
Because s can be written in the form s = g**d, s.g = g**(x+d), which
leads to a right shift.
The number of shifted permutations is (q-1)*phi(q-1).
The benefit of shifted permutation is to increase, with a low cost
computation, the bMAC entropy.
3.3 Composition in Fq
Given a set of k ptuples {(g1,s1), (g2,s2),..., (gk,sk)} and
associated shifted permutations P(gi,si), a permutation P(q,k) is
computed according to the relation :
P(q,k) = P(gk,sk) o ... o P(g2,s2) o P(g1,s1)
3.4 Code example
The bMAC is computed with a permutation P= P(g2) o P(g1,s1)
The pseudo code is written in a C like way.
H is a SHA3-256 KECCAK hash function.
3.4.1 Example 1
In this example 32 bits integers are used.
The prime number q is 9733.
The address space is N= 9664.
With a 8 bits processor, 12MHz clock, the bMAC is computed in about
10s, i.e. 1ms per byte.
Urien Expires May 2020 [Page 7]
Bijective MAC for Constraint Nodes November 2019
uint32-t x,y,bitn,v,gi[13];
uint32-t PRIME, g1=a-generator, s1=a-value, g2=a-generator;
bool tohash;
PRIME =9733;
H.reset();
gi[0]= g2;
for (int n=1;n<=13;n++)
gi[n] = (gi[n-1] * gi[n-1]) % PRIME;
x= s1;
for(int i=1;i>1;
}
v = (y-1);
// if address v exists, read the v address content A(v)
// tohash=true ;
if (tohash) H.update(A(v));
}
H.dofinal();
3.4.2 Example 2
In this example 64 bits and 32 bits integers are used.
The prime number q is 278543.
The address space is N= 271360.
With a 8 bits processor, 16MHz clock, the bMAC is computed in about
320s, i.e. 1.1 ms per byte.
uint32-t bitn,v;
uint64-t x,y,gi[19];
uint32-t PRIME, g1=a-generator, s1=a-value, g2=a-generator;
bool tohash;
PRIME = 278543;
H.reset();
gi[0]=(uint64-t)g2;
for (n=1;n<=19;n++)
{ gi[n] = gi[n-1] * gi[n-1];
gi[n] = gi[n] % PRIME;
Urien Expires May 2020 [Page 8]
Bijective MAC for Constraint Nodes November 2019
}
x= s1;
for(i=1;i>1;
}
v = (uint32-t)(y-1);
// if address v exists, read the v address content A(v)
// tohash=true ;
if (tohash) H.update(A(v));
}
H.final();
4 bMAC protocol
A bMAC protocol involves a bMAC requester and a bMAC provider.
The requester sends to the bMAC provider the parameters needed for
the P permutation.
The bMAC provider computes the bMAC according to the P permutation
and returns the result.
If the bMAC provider has access to internet, the requester
(typically a gateway) SHOULD control its internet access in order to
avoid side channel attack.
5 IANA Considerations
TODO
6 Security Considerations
TODO
7 References
Urien Expires May 2020 [Page 9]
Bijective MAC for Constraint Nodes November 2019
7.1 Normative References
7.2 Informative References
8 Authors' Addresses
Pascal Urien
Telecom ParisTech
19 Place Marguerite Perey
91120 Palaiseau
France
Phone: NA
Email: Pascal.Urien@telecom-paristech.fr
Urien Expires May 2020 [Page 10]