idnits 2.17.1 draft-urien-core-bmac-06.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 -- Couldn't find a document date in the document -- date freshness check skipped. Checking references for intended status: Experimental ---------------------------------------------------------------------------- -- Missing reference section? '0' on line 153 looks like a reference -- Missing reference section? 'N-1' on line 140 looks like a reference -- Missing reference section? '255' on line 140 looks like a reference -- Missing reference section? 'M-1' on line 153 looks like a reference -- Missing reference section? '14' on line 423 looks like a reference -- Missing reference section? '19' on line 461 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 June 14 2020 7 Expires: December 2020 9 Bijective MAC for Constraint Nodes 10 draft-urien-core-bmac-06.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 are major 18 security issues, 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, especially for time stamped bMAC. 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 December 2020. 54 Copyright Notice 56 Copyright (c) 2020 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 Table of Contents 70 Abstract........................................................... 1 71 Requirements Language.............................................. 1 72 Status of this Memo................................................ 1 73 Copyright Notice................................................... 2 74 1 Overview......................................................... 4 75 2 Bijective MAC.................................................... 4 76 2.1 Memory space................................................ 4 77 2.2 Permutation................................................. 4 78 2.3 bMAC computation............................................ 5 79 2.4 Unused memory............................................... 5 80 2.5 Permutation entropy......................................... 5 81 2.6 Time-stamped bMAC........................................... 6 82 2.6.1 Rational ............................................. 6 83 2.6.2 Canonical time ....................................... 6 84 3. The Pq permutation family....................................... 7 85 3.1 How to find a generator..................................... 7 86 3.1.1 Method 1 ............................................. 7 87 3.1.2 Method 2 ............................................. 7 88 3.1.3 Method 3 ............................................. 8 89 3.2 How to compute generators................................... 8 90 3.2.1 Example 1 ............................................ 8 91 3.2.2 Example 2. ........................................... 8 92 3.2.3 Example 3. ........................................... 9 93 3.2.4 Example 4 ............................................ 9 94 3.2.5 Example 5 ............................................ 9 95 3.2.6 Example 6 ............................................ 9 96 3.3 Shifted permutation......................................... 9 97 3.4 Composition in Fq.......................................... 10 98 3.5 Code example............................................... 10 99 3.5.1 Example 1 ........................................... 10 100 3.5.2 Example 2 ........................................... 11 101 4 bMAC protocol................................................... 12 102 5 IANA Considerations............................................. 12 103 6 Security Considerations......................................... 12 104 7 References...................................................... 12 105 7.1 Normative References....................................... 12 106 7.2 Informative References..................................... 12 107 8 Authors' Addresses.............................................. 12 108 1 Overview 110 In this draft context, things are powered by micro controllers units 111 (MCU) comprising a set of memories such as static RAM (SRAM), FLASH 112 and EEPROM. The total memory size ranges from 10KB to a few 113 megabytes. 114 In this context code and data integrity is a major security issue 115 for the deployment of Internet of Things infrastructure. 116 The goal of the bijective MAC (bMAC) is to compute an integrity 117 value, which cannot be guessed by malicious software. 118 In classical keyed MACs, MAC is computing according to a fixed 119 order. 120 In the bijective MAC, the content of N addresses (A[0]...A[N-1]) is 121 hashed according to a hash function H and a permutation P (i.e. 122 bijective application in [0,N-1])so that : 124 bMAC(A, P) = H( A[P(0)] || A[P(1)] ... || A[P(N-1)] ) 126 The bijective MAC key is the permutation P. The number of 127 permutations for N addresses is N!, as an illustration 35! is 128 greater than 2**128. So the bMAC computation requires the knowledge 129 of the whole space memory. This is trivial for genuine software, but 130 could very difficult for corrupted software, especially for time 131 stamped bMAC. 133 2 Bijective MAC 135 2.1 Memory space 137 The memory space is represented by an application A, working with N 138 addresses, whose content is a byte value. 140 | [0,N-1] -> [0,255] 141 A | 142 | x -> A[x] 144 Non volatile memories (FLASH, EEPROM) MUST be included in the memory 145 space. A subset of SRAM is included in the memory, whose structure 146 relies on operational constraints (heap size, stack size,...). 148 2.2 Permutation 150 For practical reasons, permutation MAY use a range of M values, 151 greater than the size N of the memory space (M>=N). 153 | [0,M-1] -> [0,M-1] 154 P | 155 | x -> P(x) 156 For example, given a N memory space, and q a prime number so that 157 q>N, and g a generator for the group Z/qZ, the P permutation (with 158 M= q-1) can computed as: 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 199 2.6 Time-stamped bMAC 201 2.6.1 Rational 203 The main idea is to detect corrupted software that uses a code 204 compression algorithm. 206 +-------------------------+ +-------------------------------+ 207 | | | +-+ Genuine Code Compressed | 208 | | +-|-|---------------------------+ 209 | | | | | Code Compression Algo. | 210 | Genuine Code | +-|-|---------------------------+ 211 | | | V + Malicious bMAC + ^ | 212 | | +------------------------|-|----+ 213 | | | Genuine Code +-+ | 214 +-------------------------+ +-------------------------------+ 215 | bMAC | | MALWARE | 216 +-------------------------+ +-------------------------------+ 218 The basic principle of the time stamped bMAC is that the code 219 compression algorithm modifies the time needed for the bMAC 220 computing. Furthermore we assume that the time required by the bMAC 221 computing is dependent on the permutation. 223 Below is an illustration of C code that returns the content of a 224 corrupted address: 226 if ((Adr >= Adr-Min) && (Adr <= Adr-Max)) 227 v =decompress(Adr); 228 else 229 v= read(Adr); 231 Many computing cycles are added to the genuine code (read(Adr)) due 232 to Program Counter jumps and execution of the decompression 233 procedure. 235 2.6.2 Canonical time 237 We assume that the bMAC computing time (T) ranges between the values 238 Tmin and Tmax 240 Tmin <= T <= Tmax 242 If the computing time is fixed (Tmin=Tmax) then the Canonical Time 243 (cT) is the computing time T. 245 If Tmin#Tmax we define the following values: 246 Range = Tmax-Tmin+1 247 Delta = Tmin modulo Range 248 For a given computing time T, we define the canonical computing time 249 cT as: 250 cT = (T-Delta)/Range 252 For every T value, cT has a fix value equal to the quotient of 253 Tmin/Range. 255 The main interest of the canonical time is that it works as a secret 256 value, deduced from the bMAC computing but not stored in the 257 software memory image. 259 The time-stamped bMAC is computed from an exor operation between the 260 bMAC and the canonical time: 262 Time-Stamped bMAC = bMAC exor cT 264 3. The Pq permutation family 266 We consider a N memory space, and q a prime number so that q>N. 268 Z/qZ is a monogenous group with n=phi(q-1) generators (g), phi being 269 the Euler number. Generators (g) in Z/qZ can be used to build a 270 permutation family Pq= = {Pg1, Pg2,.., Pgn}, so that: 272 | [1,q-1] -> [1,q-1] 273 Pg(x) | 274 | x -> g**x mod q 276 Given a P permutation working in the [1,q-1] range (such as Pg), we 277 use the P*(P) permutation in order to enforce compatibility with the 278 memory space A(x) starting at the zero address : 280 | [0,q-2] -> [0,q-2] 281 P* | 282 | x -> P*(x) = P(1+x)-1 284 3.1 How to find a generator 286 3.1.1 Method 1 288 Given x in [2, q-1], 289 If x**k mod q # 1 for all k in [1, q-2], then g is a generator. 291 3.1.2 Method 2 293 Factorize q-1 into primes: q-1 = q1**k1...qi**ki...qn**kn 294 Find n integers ai (a1...an) of order qi**ki, in Z/qZ (phi(qi**ki) 295 elements) 296 The product of the n elements a1 x...x an, is a generator. 298 3.1.3 Method 3 300 q being a safe prime, q = 2*p+1 with p prime (p is the Sophie 301 Germain prime),and q = 7 mod 8. 303 phi(q-1) = phi(2p) = p-1 304 1 generator of order 2, i.e. q-1 305 p-1 generators of order p, i.e. 2**k mod q with k in [1,p-1] 306 p-1 generators gk of order q-1. 307 The generators gk are the product of (q-1).2**k mod q, for k in 308 [1,p-1]. In other words the generators gk are equal to q-(2**k mod 309 q), for k in [1,p-1] 311 3.2 How to compute generators 313 Find a generator g. 315 There are phi(q-1) generators g**k, with k prime with q-1. 317 GCD(k,q-1)=1, GCD being the Greatest Common Divisor of two integers. 319 3.2.1 Example 1 321 q=11, phi(10)= 4 322 10= 2x5, phi(2)=1, phi(5)=4 323 prime numbers with 10= {1,3,7,9} 325 k 1 2 3 4 5 6 7 8 9 10 326 x**k 1 327 2 4 8 5 10 9 7 3 6 1 328 3 9 5 4 1 329 4 5 9 3 1 330 5 3 4 9 1 331 6 3 7 9 10 5 8 4 2 1 332 7 5 2 3 10 4 6 9 8 1 333 8 9 6 4 10 3 2 5 7 1 334 9 4 3 5 1 335 10 1 337 10 has an order 2 338 3, 4, 5, 9 have order 5 339 10*3= 8, 4*10= 7, 5*10=6, 9*10=2 are generators 341 2 is a generator 342 2**3 = 8 is a generator 343 2**7 = 7 is a generator 344 2**9 = 6 is a generator 346 3.2.2 Example 2. 348 q= 23 = 2x11 + 1, p=11, q is a safe prime with q mod 8 =7 349 power of 2 mod 23 = {2**k, k in [1,10]}= {2,4,8,16,9,18,13,3,6,12} 350 10 generators gk of order 22 = {21,19,15,7,14,5,10,20,17,11} 352 3.2.3 Example 3. 354 Memory space N = 512B EEPROM + 8192B FLASH + 1024B SRAM = 9728B 355 Nearest prime number q = 9733 356 q-1 = 9732= 811 x 4 x 3 357 phi(9732) = 3240 358 2 is a generator 359 generators are numbers 2**k mod q, with k less than q-1, and k prime 360 with 811, 4 and 3. 362 3.2.4 Example 4 364 Memory space N = 512B EEPROM + 8192B FLASH + 1024B SRAM = 9728B 365 Safe prime = 9887 366 4943 generators 368 3.2.5 Example 5 370 Memory space N = 4096B EEPROM + 262144B FLASH + 1024B SRAM= 274432 371 prime number q = 278543 372 q-1= 278542 = 2 x 11**2 x 1151 373 phi(278542) = 126500 374 5 is a generator 375 generators are numbers, 5**k mod q, with k less than q-1, prime with 376 2, 11, and 1151 378 3.2.6 Example 6 380 Memory space N = 4096B EEPROM + 262144B FLASH + 1024B SRAM= 274432 381 Safe prime = 275447 382 137723 generators 384 3.3 Shifted permutation 386 Given an integer s in the range [0, q-1], the shifted permutation 387 P(g,s) is defined as 389 | [1,q-1] -> [1,q-1] 390 P(g,s)(x) | 391 | x -> s.g**x mod q 393 In other words P(g,s)(x) = s x Pg(x). 395 Because s can be written in the form s = g**d, s.g = g**(x+d), which 396 leads to a right shift. 397 The number of shifted permutations is (q-1)*phi(q-1). 398 The benefit of shifted permutation is to increase, with a low cost 399 computation, the bMAC entropy. 401 3.4 Composition in Fq 403 Given a set of k ptuples {(g1,s1), (g2,s2),..., (gk,sk)} and 404 associated shifted permutations P(gi,si), a permutation P(q,k) is 405 computed according to the relation : 407 P(q,k) = P(gk,sk) o ... o P(g2,s2) o P(g1,s1) 409 3.5 Code example 411 The bMAC is computed with a permutation P= P(g2) o P(g1,s1) 412 The pseudo code is written in a C like way. 413 H is a SHA3-256 KECCAK hash function. 415 3.5.1 Example 1 417 In this example 32 bits integers are used. 418 The prime number q is 9733. 419 The address space is N= 9664. 420 For a 8 bits processor, 12MHz clock, the bMAC is computed in about 421 10s, i.e. 1ms per byte. 423 uint32-t x,y,bitn,v,gi[14]; 424 uint32-t PRIME, g1=a-generator, s1=a-value, g2=a-generator; 425 bool tohash; 427 PRIME =9733; 428 H.reset(); 430 gi[0]= g2; 431 for (int n=1;n<=13;n++) 432 gi[n] = (gi[n-1] * gi[n-1]) % PRIME; 434 x= s1; 436 for(int i=1;i>1; 444 } 445 v = (y-1); 446 // if address v exists, read the v address content A(v) 447 // tohash=true ; 448 if (tohash) H.update(A(v)); 449 } 451 H.dofinal(); 452 3.5.2 Example 2 454 In this example 64 bits and 32 bits integers are used. 455 The prime number q is 278543. 456 The address space is N= 271360. 457 For a 8 bits processor, 16MHz clock, the bMAC is computed in about 458 320s, i.e. 1.1 ms per byte. 460 uint32-t bitn,v; 461 uint64-t x,y,gi[19]; 462 uint32-t PRIME, g1=a-generator, s1=a-value, g2=a-generator; 463 bool tohash; 465 PRIME = 278543; 466 H.reset(); 468 gi[0]=(uint64-t)g2; 469 for (n=1;n<=18;n++) 470 { gi[n] = gi[n-1] * gi[n-1]; 471 gi[n] = gi[n] % PRIME; 472 } 474 x= s1; 476 for(i=1;i>1; 489 } 491 v = (uint32-t)(y-1); 492 // if address v exists, read the v address content A(v) 493 // tohash=true ; 494 if (tohash) H.update(A(v)); 495 } 497 H.final(); 498 4 bMAC protocol 500 A bMAC protocol involves a bMAC requester and a bMAC provider. 502 The requester sends to the bMAC provider the parameters needed for 503 the P permutation. 505 The bMAC provider computes the bMAC according to the P permutation 506 and returns the result. 508 If the bMAC provider has access to internet, the requester 509 (typically a gateway) SHOULD control its internet access in order to 510 avoid side channel attack. 512 5 IANA Considerations 514 TODO 516 6 Security Considerations 518 TODO 520 7 References 522 7.1 Normative References 524 7.2 Informative References 526 8 Authors' Addresses 528 Pascal Urien 529 Telecom ParisTech 530 19 Place Marguerite Perey 531 91120 Palaiseau 532 France 534 Phone: NA 535 Email: Pascal.Urien@telecom-paristech.fr