idnits 2.17.1 draft-urien-core-bmac-05.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 (December 12, 2019) is 1591 days in the past. Is this intentional? Checking references for intended status: Experimental ---------------------------------------------------------------------------- -- Missing reference section? '0' on line 157 looks like a reference -- Missing reference section? 'N-1' on line 144 looks like a reference -- Missing reference section? '255' on line 144 looks like a reference -- Missing reference section? 'M-1' on line 157 looks like a reference -- Missing reference section? '14' on line 439 looks like a reference -- Missing reference section? '19' on line 479 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 December 12, 2019 7 Expires: June 2020 9 Bijective MAC for Constraint Nodes 10 draft-urien-core-bmac-05.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 June 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 December 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........................................... 6 84 2.6.1 Rational ............................................. 6 85 2.6.2 Canonical time ....................................... 6 86 3. The Pq permutation family....................................... 7 87 3.1 How to find a generator..................................... 7 88 3.1.1 Method 1 ............................................. 7 89 3.1.2 Method 2 ............................................. 7 90 3.1.3 Method 3 ............................................. 8 91 3.2 How to compute generators................................... 8 92 3.2.1 Example 1 ............................................ 8 93 3.2.2 Example 2. ........................................... 8 94 3.2.3 Example 3. ........................................... 9 95 3.2.4 Example 4 ............................................ 9 96 3.2.5 Example 5 ............................................ 9 97 3.2.6 Example 6 ............................................ 9 98 3.3 Shifted permutation......................................... 9 99 3.4 Composition in Fq.......................................... 10 100 3.5 Code example............................................... 10 101 3.5.1 Example 1 ........................................... 10 102 3.5.2 Example 2 ........................................... 11 103 4 bMAC protocol................................................... 12 104 5 IANA Considerations............................................. 12 105 6 Security Considerations......................................... 12 106 7 References...................................................... 12 107 7.1 Normative References....................................... 12 108 7.2 Informative References..................................... 12 109 8 Authors' Addresses.............................................. 12 110 Bijective MAC for Constraint Nodes December 2019 112 1 Overview 114 In this draft context, things are powered by micro controllers units 115 (MCU) comprising a set of memories such as static RAM (SRAM), FLASH 116 and EEPROM. The total memory size ranges from 10KB to a few 117 megabytes. 118 In this context code and data integrity is a major security issue 119 for the deployment of Internet of Things infrastructure. 120 The goal of the bijective MAC (bMAC) is to compute an integrity 121 value, which cannot be guessed by malicious software. 122 In classical keyed MACs, MAC is computing according to a fixed 123 order. 124 In the bijective MAC, the content of N addresses (A[0]...A[N-1]) is 125 hashed according to a hash function H and a permutation P (i.e. 126 bijective application in [0,N-1])so that : 128 bMAC(A, P) = H( A[P(0)] || A[P(1)] ... || A[P(N-1)] ) 130 The bijective MAC key is the permutation P. The number of 131 permutations for N addresses is N!, as an illustration 35! is 132 greater than 2**128. So the bMAC computation requires the knowledge 133 of the whole space memory. This is trivial for genuine software, but 134 could very difficult for corrupted software, especially for time 135 stamped bMAC. 137 2 Bijective MAC 139 2.1 Memory space 141 The memory space is represented by an application A, working with N 142 addresses, whose content is a byte value. 144 | [0,N-1] -> [0,255] 145 A | 146 | x -> A[x] 148 Non volatile memories (FLASH, EEPROM) MUST be included in the memory 149 space. A subset of SRAM is included in the memory, whose structure 150 relies on operational constraints (heap size, stack size,...). 152 2.2 Permutation 154 For practical reasons, permutation MAY use a range of M values, 155 greater than the size N of the memory space (M>=N). 157 | [0,M-1] -> [0,M-1] 158 P | 159 | x -> P(x) 160 Bijective MAC for Constraint Nodes December 2019 162 For example, given a N memory space, and q a prime number so that 163 q>N, and g a generator for the group Z/qZ, the P permutation (with 164 M= q-1) can computed as: 166 | [0,q-2] -> [0,q-2] 167 P | 168 | x -> (g**(1+x) mod q)-1 170 2.3 bMAC computation 172 We consider a one way hash function H (such as SHA2 or SHA3) with 173 three procedures, H.reset, H.update, and H.final. 175 Given a space memory N, a permutation P with M values, the bMAC, 176 according to C like notation, is computed as: 178 H.reset() ; 179 for (i=0; i< M; i++) 180 { if (P(i) < N) 181 H.update(A[P[i]); 182 } 183 bMAC= H.final(); 185 2.4 Unused memory 187 Unused memory MAY be filled by pseudo random values, before 188 performing the bMAC computation. 190 2.5 Permutation entropy 192 A family of Pk permutations is a subset of M! permutations of M 193 elements, which is computed according to dedicated algorithms. 195 We note #Pk the number of elements of a Pk family. 197 The entropy is the integer e, such as 2**e is closed to #Pk: 199 2**e <= #Pk < 2**(e+1) 201 The entropy of a family may be increased by the composition of Pk 202 functions so that : 204 P(k1,k2,...,kn) = Pkn o ... o Pk2 o Pk1 205 Bijective MAC for Constraint Nodes December 2019 207 2.6 Time-stamped bMAC 209 2.6.1 Rational 211 The main idea is to detect corrupted software that uses a code 212 compression algorithm. 214 +-------------------------+ +-------------------------------+ 215 | | | +-+ Genuine Code Compressed | 216 | | +-|-|---------------------------+ 217 | | | | | Code Compression Algo. | 218 | Genuine Code | +-|-|---------------------------+ 219 | | | V + Malicious bMAC + ^ | 220 | | +------------------------|-|----+ 221 | | | Genuine Code +-+ | 222 +-------------------------+ +-------------------------------+ 223 | bMAC | | MALWARE | 224 +-------------------------+ +-------------------------------+ 226 The basic principle of the time stamped bMAC is that the code 227 compression algorithm modifies the time needed for the bMAC 228 computing. Furthermore we assume that the time required by the bMAC 229 computing is dependent on the permutation. 231 Below is an illustration of C code that returns the content of a 232 corrupted address: 234 if ((Adr >= Adr-Min) && (Adr <= Adr-Max)) 235 v =decompress(Adr); 236 else 237 v= read(Adr); 239 Many computing cycles are added to the genuine code (read(Adr)) due 240 to Program Counter jumps and execution of the decompression 241 procedure. 243 2.6.2 Canonical time 245 We assume that the bMAC computing time (T) ranges between the values 246 Tmin and Tmax 248 Tmin <= T <= Tmax 250 If the computing time is fixed (Tmin=Tmax) then the Canonical Time 251 (cT) is the computing time T. 253 If Tmin#Tmax we define the following values: 254 Range = Tmax-Tmin+1 255 Delta = Tmin modulo Range 256 Bijective MAC for Constraint Nodes December 2019 258 For a given computing time T, we define the canonical computing time 259 cT as: 260 cT = (T-Delta)/Range 262 For every T value, cT has a fix value equal to the quotient of 263 Tmin/Range. 265 The main interest of the canonical time is that it works as a secret 266 value, deduced from the bMAC computing but not stored in the 267 software memory image. 269 The time-stamped bMAC is computed from an exor operation between the 270 bMAC and the canonical time: 272 Time-Stamped bMAC = bMAC exor cT 274 3. The Pq permutation family 276 We consider a N memory space, and q a prime number so that q>N. 278 Z/qZ is a monogenous group with n=phi(q-1) generators (g), phi being 279 the Euler number. Generators (g) in Z/qZ can be used to build a 280 permutation family Pq= = {Pg1, Pg2,.., Pgn}, so that: 282 | [1,q-1] -> [1,q-1] 283 Pg(x) | 284 | x -> g**x mod q 286 Given a P permutation working in the [1,q-1] range (such as Pg), we 287 use the P*(P) permutation in order to enforce compatibility with the 288 memory space A(x) starting at the zero address : 290 | [0,q-2] -> [0,q-2] 291 P* | 292 | x -> P*(x) = P(1+x)-1 294 3.1 How to find a generator 296 3.1.1 Method 1 298 Given x in [2, q-1], 299 If x**k mod q # 1 for all k in [1, q-2], then g is a generator. 301 3.1.2 Method 2 303 Factorize q-1 into primes: q-1 = q1**k1...qi**ki...qn**kn 304 Find n integers ai (a1...an) of order qi**ki, in Z/qZ (phi(qi**ki) 305 elements) 306 The product of the n elements a1 x...x an, is a generator. 308 Bijective MAC for Constraint Nodes December 2019 310 3.1.3 Method 3 312 q being a safe prime, q = 2*p+1 with p prime (p is the Sophie 313 Germain prime),and q = 7 mod 8. 315 phi(q-1) = phi(2p) = p-1 316 1 generator of order 2, i.e. q-1 317 p-1 generators of order p, i.e. 2**k mod q with k in [1,p-1] 318 p-1 generators gk of order q-1. 319 The generators gk are the product of (q-1).2**k mod q, for k in 320 [1,p-1]. In other words the generators gk are equal to q-(2**k mod 321 q), for k in [1,p-1] 323 3.2 How to compute generators 325 Find a generator g. 327 There are phi(q-1) generators g**k, with k prime with q-1. 329 GCD(k,q-1)=1, GCD being the Greatest Common Divisor of two integers. 331 3.2.1 Example 1 333 q=11, phi(10)= 4 334 10= 2x5, phi(2)=1, phi(5)=4 335 prime numbers with 10= {1,3,7,9} 337 k 1 2 3 4 5 6 7 8 9 10 338 x**k 1 339 2 4 8 5 10 9 7 3 6 1 340 3 9 5 4 1 341 4 5 9 3 1 342 5 3 4 9 1 343 6 3 7 9 10 5 8 4 2 1 344 7 5 2 3 10 4 6 9 8 1 345 8 9 6 4 10 3 2 5 7 1 346 9 4 3 5 1 347 10 1 349 10 has an order 2 350 3, 4, 5, 9 have order 5 351 10*3= 8, 4*10= 7, 5*10=6, 9*10=2 are generators 353 2 is a generator 354 2**3 = 8 is a generator 355 2**7 = 7 is a generator 356 2**9 = 6 is a generator 358 3.2.2 Example 2. 360 q= 23 = 2x11 + 1, p=11, q is a safe prime with q mod 8 =7 361 Bijective MAC for Constraint Nodes December 2019 363 power of 2 mod 23 = {2**k, k in [1,10]}= {2,4,8,16,9,18,13,3,6,12} 364 10 generators gk of order 22 = {21,19,15,7,14,5,10,20,17,11} 366 3.2.3 Example 3. 368 Memory space N = 512B EEPROM + 8192B FLASH + 1024B SRAM = 9728B 369 Nearest prime number q = 9733 370 q-1 = 9732= 811 x 4 x 3 371 phi(9732) = 3240 372 2 is a generator 373 generators are numbers 2**k mod q, with k less than q-1, and k prime 374 with 811, 4 and 3. 376 3.2.4 Example 4 378 Memory space N = 512B EEPROM + 8192B FLASH + 1024B SRAM = 9728B 379 Safe prime = 9887 380 4943 generators 382 3.2.5 Example 5 384 Memory space N = 4096B EEPROM + 262144B FLASH + 1024B SRAM= 274432 385 prime number q = 278543 386 q-1= 278542 = 2 x 11**2 x 1151 387 phi(278542) = 126500 388 5 is a generator 389 generators are numbers, 5**k mod q, with k less than q-1, prime with 390 2, 11, and 1151 392 3.2.6 Example 6 394 Memory space N = 4096B EEPROM + 262144B FLASH + 1024B SRAM= 274432 395 Safe prime = 275447 396 137723 generators 398 3.3 Shifted permutation 400 Given an integer s in the range [0, q-1], the shifted permutation 401 P(g,s) is defined as 403 | [1,q-1] -> [1,q-1] 404 P(g,s)(x) | 405 | x -> s.g**x mod q 407 In other words P(g,s)(x) = s x Pg(x). 409 Because s can be written in the form s = g**d, s.g = g**(x+d), which 410 leads to a right shift. 411 The number of shifted permutations is (q-1)*phi(q-1). 412 The benefit of shifted permutation is to increase, with a low cost 413 computation, the bMAC entropy. 415 Bijective MAC for Constraint Nodes December 2019 417 3.4 Composition in Fq 419 Given a set of k ptuples {(g1,s1), (g2,s2),..., (gk,sk)} and 420 associated shifted permutations P(gi,si), a permutation P(q,k) is 421 computed according to the relation : 423 P(q,k) = P(gk,sk) o ... o P(g2,s2) o P(g1,s1) 425 3.5 Code example 427 The bMAC is computed with a permutation P= P(g2) o P(g1,s1) 428 The pseudo code is written in a C like way. 429 H is a SHA3-256 KECCAK hash function. 431 3.5.1 Example 1 433 In this example 32 bits integers are used. 434 The prime number q is 9733. 435 The address space is N= 9664. 436 For a 8 bits processor, 12MHz clock, the bMAC is computed in about 437 10s, i.e. 1ms per byte. 439 uint32-t x,y,bitn,v,gi[14]; 440 uint32-t PRIME, g1=a-generator, s1=a-value, g2=a-generator; 441 bool tohash; 443 PRIME =9733; 444 H.reset(); 446 gi[0]= g2; 447 for (int n=1;n<=13;n++) 448 gi[n] = (gi[n-1] * gi[n-1]) % PRIME; 450 x= s1; 452 for(int i=1;i>1; 460 } 461 v = (y-1); 462 // if address v exists, read the v address content A(v) 463 // tohash=true ; 464 if (tohash) H.update(A(v)); 465 } 467 H.dofinal(); 468 Bijective MAC for Constraint Nodes December 2019 470 3.5.2 Example 2 472 In this example 64 bits and 32 bits integers are used. 473 The prime number q is 278543. 474 The address space is N= 271360. 475 For a 8 bits processor, 16MHz clock, the bMAC is computed in about 476 320s, i.e. 1.1 ms per byte. 478 uint32-t bitn,v; 479 uint64-t x,y,gi[19]; 480 uint32-t PRIME, g1=a-generator, s1=a-value, g2=a-generator; 481 bool tohash; 483 PRIME = 278543; 484 H.reset(); 486 gi[0]=(uint64-t)g2; 487 for (n=1;n<=18;n++) 488 { gi[n] = gi[n-1] * gi[n-1]; 489 gi[n] = gi[n] % PRIME; 490 } 492 x= s1; 494 for(i=1;i>1; 507 } 509 v = (uint32-t)(y-1); 510 // if address v exists, read the v address content A(v) 511 // tohash=true ; 512 if (tohash) H.update(A(v)); 513 } 515 H.final(); 516 Bijective MAC for Constraint Nodes December 2019 518 4 bMAC protocol 520 A bMAC protocol involves a bMAC requester and a bMAC provider. 522 The requester sends to the bMAC provider the parameters needed for 523 the P permutation. 525 The bMAC provider computes the bMAC according to the P permutation 526 and returns the result. 528 If the bMAC provider has access to internet, the requester 529 (typically a gateway) SHOULD control its internet access in order to 530 avoid side channel attack. 532 5 IANA Considerations 534 TODO 536 6 Security Considerations 538 TODO 540 7 References 542 7.1 Normative References 544 7.2 Informative References 546 8 Authors' Addresses 548 Pascal Urien 549 Telecom ParisTech 550 19 Place Marguerite Perey 551 91120 Palaiseau 552 France 554 Phone: NA 555 Email: Pascal.Urien@telecom-paristech.fr