idnits 2.17.1 draft-urien-core-bmac-02.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (November 25, 2019) is 1613 days in the past. Is this intentional? Checking references for intended status: Experimental ---------------------------------------------------------------------------- -- Missing reference section? '0' on line 150 looks like a reference -- Missing reference section? 'N-1' on line 137 looks like a reference -- Missing reference section? '255' on line 137 looks like a reference -- Missing reference section? 'M-1' on line 150 looks like a reference -- Missing reference section? '14' on line 363 looks like a reference -- Missing reference section? '19' on line 404 looks like a reference Summary: 0 errors (**), 0 flaws (~~), 1 warning (==), 7 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 CORE Working Group Working Group P. Urien 3 Internet Draft Telecom ParisTech 4 Intended status: Experimental 6 November 25, 2019 7 Expires: May 2020 9 Bijective MAC for Constraint Nodes 10 draft-urien-core-bmac-02.txt 12 Abstract 14 In this draft context, things are powered by micro controllers units 15 (MCU) comprising a set of memories such as static RAM (SRAM), FLASH 16 and EEPROM. The total memory size, ranges from 10KB to a few 17 megabytes. In this context code and data integrity is a major 18 security issue, for the deployment of Internet of Things 19 infrastructure. The goal of the bijective MAC (bMAC) is to compute 20 an integrity value, which cannot be guessed by malicious software. 21 In classical keyed MACs, MAC is computing according to a fixed 22 order. 23 In the bijective MAC, the content of N addresses is hashed according 24 to a permutation P (i.e. bijective application). 25 The bijective MAC key is the permutation P. 26 The number of permutations for N addresses is N!. So the computation 27 of the bMAC requires the knowledge of the whole space memory; this 28 is trivial for genuine software, but could very difficult for 29 corrupted software. 31 Requirements Language 33 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 34 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 35 document are to be interpreted as described in RFC 2119. 37 Status of this Memo 39 This Internet-Draft is submitted in full conformance with the 40 provisions of BCP 78 and BCP 79. 42 Internet-Drafts are working documents of the Internet Engineering 43 Task Force (IETF). Note that other groups may also distribute 44 working documents as Internet-Drafts. The list of current Internet- 45 Drafts is at http://datatracker.ietf.org/drafts/current/. 47 Internet-Drafts are draft documents valid for a maximum of six 48 months and may be updated, replaced, or obsoleted by other documents 49 at any time. It is inappropriate to use Internet-Drafts as reference 50 material or to cite them other than as "work in progress." 52 This Internet-Draft will expire on May 2020. 54 Copyright Notice 56 Copyright (c) 2019 IETF Trust and the persons identified as the 57 document authors. All rights reserved. 59 This document is subject to BCP 78 and the IETF Trust's Legal 60 Provisions Relating to IETF Documents 61 (http://trustee.ietf.org/license-info) in effect on the date of 62 publication of this document. Please review these documents 63 carefully, as they describe your rights and restrictions with 64 respect to this document. Code Components extracted from this 65 document must include Simplified BSD License text as described in 66 Section 4.e of the Trust Legal Provisions and are provided without 67 warranty as described in the Simplified BSD License. 69 Bijective MAC for Constraint Nodes November 2019 71 Table of Contents 72 Abstract........................................................... 1 73 Requirements Language.............................................. 1 74 Status of this Memo................................................ 1 75 Copyright Notice................................................... 2 76 1 Overview......................................................... 4 77 2 Bijective MAC.................................................... 4 78 2.1 Memory space................................................ 4 79 2.2 Permutation................................................. 4 80 2.3 bMAC computation............................................ 5 81 2.4 Unused memory............................................... 5 82 2.5 Permutation entropy......................................... 5 83 2.6 Time-stamped bMAC........................................... 5 84 3. The Pq permutation family....................................... 6 85 3.1 How to find a generator..................................... 6 86 3.1.1 Method 1 ............................................. 6 87 3.1.2 Method 2 ............................................. 6 88 3.2 How to compute generators................................... 7 89 3.2.1 Example 1 ............................................ 7 90 3.2.2 Example 2. ........................................... 7 91 3.2.3 Example 3. ........................................... 7 92 3.3 Shifted permutation......................................... 8 93 3.4 Composition in Fq........................................... 8 94 3.5 Code example................................................ 8 95 3.5.1 Example 1 ............................................ 8 96 3.5.2 Example 2 ............................................ 9 97 4 bMAC protocol................................................... 10 98 5 IANA Considerations............................................. 10 99 6 Security Considerations......................................... 10 100 7 References...................................................... 10 101 7.1 Normative References....................................... 10 102 7.2 Informative References..................................... 11 103 8 Authors' Addresses.............................................. 11 104 Bijective MAC for Constraint Nodes November 2019 106 1 Overview 108 In this draft context, things are powered by micro controllers units 109 (MCU) comprising a set of memories such as static RAM (SRAM), FLASH 110 and EEPROM. The total memory size ranges from 10KB to a few 111 megabytes. 112 In this context code and data integrity is a major security issue 113 for the deployment of Internet of Things infrastructure. 114 The goal of the bijective MAC (bMAC) is to compute an integrity 115 value, which cannot be guessed by malicious software. 116 In classical keyed MACs, MAC is computing according to a fixed 117 order. 118 In the bijective MAC, the content of N addresses (A[0]...A[N-1]) is 119 hashed according to a hash function H and a permutation P (i.e. 120 bijective application in [0,N-1])so that : 122 bMAC(A, P) = H( A[P(0)] || A[P(1)] ... || A[P(N-1)] ) 124 The bijective MAC key is the permutation P. The number of 125 permutations for N addresses is N!, as an illustration 35! is 126 greater than 2**128. So the bMAC computation requires the knowledge 127 of the whole space memory; this is trivial for genuine software, but 128 could very difficult for corrupted software. 130 2 Bijective MAC 132 2.1 Memory space 134 The memory space is represented by an application A, working with N 135 addresses, whose content is a byte value. 137 | [0,N-1] -> [0,255] 138 A | 139 | x -> A[x] 141 Non volatile memories (FLASH, EEPROM) MUST be included in the memory 142 space. A subset of SRAM is included in the memory, whose structure 143 relies on operational constraints (heap size, stack size,...). 145 2.2 Permutation 147 For practical reasons, permutation MAY use a range of M values, 148 greater than the size N of the memory space (M>=N). 150 | [0,M-1] -> [0,M-1] 151 P | 152 | x -> P(x) 154 For example, given a N memory space, and q a prime number so that 155 q>N+1, and g a generator for the group Z/qZ, the P permutation (with 156 M= q-1) can computed as : 158 Bijective MAC for Constraint Nodes November 2019 160 | [0,q-2] -> [0,q-2] 161 P | 162 | x -> (g**(1+x) mod q)-1 164 2.3 bMAC computation 166 We consider a one way hash function H (such as SHA2 or SHA3) with 167 three procedures, H.reset, H.update, and H.final. 169 Given a space memory N, a permutation P with M values, the bMAC, 170 according to C like notation, is computed as: 172 H.reset() ; 173 for (i=0; i< M; i++) 174 { if (P(i) < N) 175 H.update(A[P[i]); 176 } 177 bMAC= H.final(); 179 2.4 Unused memory 181 Unused memory MAY be filled by pseudo random values, before 182 performing the bMAC computation. 184 2.5 Permutation entropy 186 A family of Pk permutations is a subset of M! permutations of M 187 elements, which is computed according to dedicated algorithms. 189 We note #Pk the number of elements of a Pk family. 191 The entropy is the integer e, such as 2**e is closed to #Pk: 193 2**e <= #Pk < 2**(e+1) 195 The entropy of a family may be increased by the composition of Pk 196 functions so that : 198 P(k1,k2,...,kn) = Pkn o ... o Pk2 o Pk1 200 2.6 Time-stamped bMAC 202 We assume that the bMAC computing time (T) ranges between the values 203 Tmin and Tmax: 205 Tmin <= T <= Tmax 207 We define the following values: 209 Bijective MAC for Constraint Nodes November 2019 211 Range = Tmax-Tmin+1 212 Delta = Tmin modulo Range 214 For a given computing time T, we define the canonical computing time 215 cT as : 216 cT = (T-Delta)/Range 218 For every T value, cT has a fix value equal to the quotient of 219 Tmin/Range. 221 The main interest of the canonical time is that it could work as a 222 secret value, deduced from the bMAC computing but not stored in the 223 software memory image. 225 The time-stamped bMAC is computed from an exor operation between the 226 bMAC and the canonical time: 228 Time-stamped bMAC = bMAC exor cT 230 3. The Pq permutation family 232 We consider a N memory space, and q a prime number so that q > N. 234 Z/qZ is a monogenous group with n=phi(q-1) generators (g), phi being 235 the Euler number. Generators (g) in Z/qZ can be used to build a 236 permutation family Pq= = {Pg1, Pg2,.., Pgn}, so that: 238 | [1,q-1] -> [1,q-1] 239 Pg(x) | 240 | x -> g**x mod q 242 Given a P permutation working in the [1,q-1] range (such as Pg), we 243 use the P*(P) permutation in order to enforce compatibility with the 244 memory space A(x) starting at the zero address : 246 | [0,q-2] -> [0,q-2] 247 P* | 248 | x -> P*(x) = P(1+x)-1 250 3.1 How to find a generator 252 3.1.1 Method 1 254 Given x in [1, q-1], 255 If x**k mod q # 1 for all k in [1, q-2], then g is a generator. 257 3.1.2 Method 2 259 Factorize q-1 into primes: q-1 = q1**k1...qi**ki...qn**kn 260 Bijective MAC for Constraint Nodes November 2019 262 Find n integers ai (a1...an) of order qi**ki, in Z/qZ (phi(qi**ki) 263 elements) 264 The product of the n elements a1 x...x an, is a generator. 266 3.2 How to compute generators 268 Find a generator g. 270 There are phi(q-1) generators g**k, with k prime with q-1. 272 GCD(k,q-1)=1, GCD being the Greatest Common Divisor of two integers. 274 3.2.1 Example 1 275 q=11, phi(10)= 4 276 10= 2x5, phi(2)=1, phi(5)=4 277 prime numbers with 10= {1,3,7,9} 279 k 1 2 3 4 5 6 7 8 9 10 280 x**k 1 281 2 4 8 5 10 9 7 3 6 1 282 3 9 5 4 1 283 4 5 9 3 1 284 5 3 4 9 1 285 6 3 7 9 10 5 8 4 2 1 286 7 5 2 3 10 4 6 9 8 1 287 8 9 6 4 10 3 2 5 7 1 288 9 4 3 5 1 289 10 1 291 10 has an order 2 292 3, 4, 5, 9 have order 5 293 10*3= 8, 4*10= 7, 5*10=6, 9*10=2 are generators 295 2 is a generator 296 2**3 = 8 is a generator 297 2**7 = 7 is a generator 298 2**9 = 6 is a generator 300 3.2.2 Example 2. 302 Memory space N = 512B EEPROM + 8192B FLASH + 1024B SRAM = 9728B 303 Nearest prime number q = 9733 304 q-1 = 9732= 811 x 4 x 3 305 phi(9732) = 3240 306 2 is a generator 307 generators are numbers 2**k mod q, with k less than q-1, and k prime 308 with 811, 4 and 3. 310 3.2.3 Example 3. 312 Memory space N = 4096B EEPROM + 262144B FLASH + 1024B SRAM= 274432 313 Bijective MAC for Constraint Nodes November 2019 315 prime number q = 278543 316 q-1= 278542 = 2 x 11**2 x 1151 317 phi(278542) = 126500 318 5 is a generator 319 generators are numbers, 5**k mod q, with k less than q-1, prime with 320 2, 11, and 1151 322 3.3 Shifted permutation 324 Given an integer s in the range [0, q-1], the shifted permutation 325 P(g,s) is defined as 327 | [1,q-1] -> [1,q-1] 328 P(g,s)(x) | 329 | x -> s.g**x mod q 331 In other words P(g,s)(x) = s x Pg(x). 333 Because s can be written in the form s = g**d, s.g = g**(x+d), which 334 leads to a right shift. 336 The number of shifted permutations is (q-1)*phi(q-1). 338 The benefit of shifted permutation is to increase, with a low cost 339 computation, the bMAC entropy. 341 3.4 Composition in Fq 343 Given a set of k ptuples {(g1,s1), (g2,s2),..., (gk,sk)} and 344 associated shifted permutations P(gi,si), a permutation P(q,k) is 345 computed according to the relation : 347 P(q,k) = P(gk,sk) o ... o P(g2,s2) o P(g1,s1) 349 3.5 Code example 351 The bMAC is computed with a permutation P= P(g2) o P(g1,s1) 352 The pseudo code is written in a C like way. 353 H is a SHA3-256 KECCAK hash function. 355 3.5.1 Example 1 357 In this example 32 bits integers are used. 358 The prime number q is 9733. 359 The address space is N= 9664. 360 For a 8 bits processor, 12MHz clock, the bMAC is computed in about 361 10s, i.e. 1ms per byte. 363 uint32-t x,y,bitn,v,gi[14]; 364 uint32-t PRIME, g1=a-generator, s1=a-value, g2=a-generator; 365 Bijective MAC for Constraint Nodes November 2019 367 bool tohash; 369 PRIME =9733; 370 H.reset(); 372 gi[0]= g2; 373 for (int n=1;n<=13;n++) 374 gi[n] = (gi[n-1] * gi[n-1]) % PRIME; 376 x= s1; 378 for(int i=1;i>1; 386 } 387 v = (y-1); 388 // if address v exists, read the v address content A(v) 389 // tohash=true ; 390 if (tohash) H.update(A(v)); 391 } 393 H.dofinal(); 395 3.5.2 Example 2 397 In this example 64 bits and 32 bits integers are used. 398 The prime number q is 278543. 399 The address space is N= 271360. 400 For a 8 bits processor, 16MHz clock, the bMAC is computed in about 401 320s, i.e. 1.1 ms per byte. 403 uint32-t bitn,v; 404 uint64-t x,y,gi[19]; 405 uint32-t PRIME, g1=a-generator, s1=a-value, g2=a-generator; 406 bool tohash; 408 PRIME = 278543; 409 H.reset(); 411 gi[0]=(uint64-t)g2; 412 for (n=1;n<=18;n++) 413 { gi[n] = gi[n-1] * gi[n-1]; 414 gi[n] = gi[n] % PRIME; 415 } 416 Bijective MAC for Constraint Nodes November 2019 418 x= s1; 420 for(i=1;i>1; 433 } 435 v = (uint32-t)(y-1); 436 // if address v exists, read the v address content A(v) 437 // tohash=true ; 438 if (tohash) H.update(A(v)); 439 } 441 H.final(); 443 4 bMAC protocol 445 A bMAC protocol involves a bMAC requester and a bMAC provider. 447 The requester sends to the bMAC provider the parameters needed for 448 the P permutation. 450 The bMAC provider computes the bMAC according to the P permutation 451 and returns the result. 453 If the bMAC provider has access to internet, the requester 454 (typically a gateway) SHOULD control its internet access in order to 455 avoid side channel attack. 457 5 IANA Considerations 459 TODO 461 6 Security Considerations 463 TODO 465 7 References 467 7.1 Normative References 468 Bijective MAC for Constraint Nodes November 2019 470 7.2 Informative References 472 8 Authors' Addresses 474 Pascal Urien 475 Telecom ParisTech 476 19 Place Marguerite Perey 477 91120 Palaiseau 478 France 480 Phone: NA 481 Email: Pascal.Urien@telecom-paristech.fr