idnits 2.17.1 draft-urien-core-bmac-01.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 17, 2019) is 1593 days in the past. Is this intentional? Checking references for intended status: Experimental ---------------------------------------------------------------------------- -- Missing reference section? '0' on line 144 looks like a reference -- Missing reference section? 'N-1' on line 131 looks like a reference -- Missing reference section? '255' on line 131 looks like a reference -- Missing reference section? 'M-1' on line 144 looks like a reference -- Missing reference section? '14' on line 336 looks like a reference -- Missing reference section? '19' on line 377 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 17, 2019 7 Expires: May 2020 9 Bijective MAC for Constraint Nodes 10 draft-urien-core-bmac-01.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 compute generators................................... 6 86 3.2 Shifted permutation......................................... 7 87 3.3 Composition in Fq........................................... 8 88 3.4 Code example................................................ 8 89 3.4.1 Example 1 ............................................ 8 90 3.4.2 Example 2 ............................................ 9 91 4 bMAC protocol................................................... 10 92 5 IANA Considerations............................................. 10 93 6 Security Considerations......................................... 10 94 7 References...................................................... 10 95 7.1 Normative References....................................... 10 96 7.2 Informative References..................................... 10 97 8 Authors' Addresses.............................................. 10 98 Bijective MAC for Constraint Nodes November 2019 100 1 Overview 102 In this draft context, things are powered by micro controllers units 103 (MCU) comprising a set of memories such as static RAM (SRAM), FLASH 104 and EEPROM. The total memory size ranges from 10KB to a few 105 megabytes. 106 In this context code and data integrity is a major security issue 107 for the deployment of Internet of Things infrastructure. 108 The goal of the bijective MAC (bMAC) is to compute an integrity 109 value, which cannot be guessed by malicious software. 110 In classical keyed MACs, MAC is computing according to a fixed 111 order. 112 In the bijective MAC, the content of N addresses (A[0]...A[N-1]) is 113 hashed according to a hash function H and a permutation P (i.e. 114 bijective application in [0,N-1])so that : 116 bMAC(A, P) = H( A[P(0)] || A[P(1)] ... || A[P(N-1)] ) 118 The bijective MAC key is the permutation P. The number of 119 permutations for N addresses is N!, as an illustration 35! is 120 greater than 2**128. So the bMAC computation requires the knowledge 121 of the whole space memory; this is trivial for genuine software, but 122 could very difficult for corrupted software. 124 2 Bijective MAC 126 2.1 Memory space 128 The memory space is represented by an application A, working with N 129 addresses, whose content is a byte value. 131 | [0,N-1] -> [0,255] 132 A | 133 | x -> A[x] 135 Non volatile memories (FLASH, EEPROM) MUST be included in the memory 136 space. A subset of SRAM is included in the memory, whose structure 137 relies on operational constraints. 139 2.2 Permutation 141 For practical reasons, permutation MAY use a range of M values, 142 greater than the size N of the memory space. 144 | [0,M-1] -> [0,M-1] 145 P | 146 | x -> P(x) 148 For example, given a N memory space, and q a prime number so that 149 q>N+1, and g a generator for the group Z/qZ, the P permutation (with 150 M= q-1) can computed as : 152 Bijective MAC for Constraint Nodes November 2019 154 | [0,q-2] -> [0,q-2] 155 P | 156 | x -> g**(1+x)-1 158 2.3 bMAC computation 160 We consider a one way hash function H (such as SHA2 or SHA3) with 161 three procedures, H.reset, H.update, and H.final. 163 Given a space memory N, a permutation P with M values, the bMAC, 164 according to C like notation, is computed as: 166 H.reset() ; 167 for (i=0; i< M; i++) 168 { if (P(i) < N) 169 H.update(A[P[i]); 170 } 171 bMAC= H.final(); 173 2.4 Unused memory 175 Unused memory MAY be filled by pseudo random values, before 176 performing the bMAC computation. 178 2.5 Permutation entropy 180 A family of Pk permutations is a subset of M! permutations of M 181 elements, which is computed according to dedicated algorithms. 183 We note #Pk the number of elements of a Pk family. 185 The entropy is the integer e, such as 2**e is closed to #Pk: 187 2**e <= #Pk < 2**(e+1) 189 The entropy of a family may be increased by the composition of Pk 190 functions so that : 192 P(k1,k2,...,kn) = Pkn o ... o Pk2 o Pk1 194 2.6 Time-stamped bMAC 196 We assume that the bMAC computing time (T) ranges between the values 197 Tmin and Tmax: 199 Tmin <= T <= Tmax 201 We define the following values: 203 Bijective MAC for Constraint Nodes November 2019 205 Range = Tmax-Tmin+1 206 Delta = Tmin modulo Range 208 For a given computing time T we define the canonical computing time 209 cT as : 210 cT = (T-Delta)/Range 212 For every T value, cT has a fix value equal to the quotient of 213 Tmin/Range. 215 The main interest of the canonical time is that it could work as a 216 secret value, deduced from the bMAC computing but not stored in the 217 software memory image. 219 The time-stamped bMAC is computed from an exor operation between the 220 bMAC and the canonical time: 222 Time-stamped bMAC = bMAC exor cT 224 3. The Pq permutation family 226 We consider a N memory space, and q a prime number so that q > N. 228 Z/qZ is a monogenous group with n=phi(q-1) generators (g), phi being 229 the Euler number. Generators (g) in Z/qZ can be used to build a 230 permutation family Pq= = {Pg1, Pg2,.., Pgn}, so that: 232 | [1,q-1] -> [1,q-1] 233 Pg(x) | 234 | x -> g**x 236 Given a P permutation working in the [1,q-1] range (such as Pg), we 237 use the P*(P) permutation in order to enforce compatibility with the 238 memory space A(x) starting at the zero address : 240 | [0,q-2] -> [0,q-2] 241 P* | 242 | x -> P*(x) = P(1+x)-1 244 3.1 How to compute generators 246 Find a generator g. 248 There are phi(q-1) generators g**k, with k prime with q-1. 250 GCD(k,q-1)=1, GCD being the Greatest Common Divisor of two integers. 252 Bijective MAC for Constraint Nodes November 2019 254 Example 1 255 q=11, phi(10)= 4 256 10= 2x5, prime numbers with 10= {1,3,7,9} 258 k 1 2 3 4 5 6 7 8 9 10 259 x**k 1 260 2 4 8 5 10 9 7 3 6 1 261 3 9 5 4 1 262 4 5 9 3 1 263 5 3 4 9 1 264 6 3 7 9 10 5 8 4 2 1 265 7 5 2 3 10 4 6 9 8 1 266 8 9 6 4 10 3 2 5 7 1 267 9 4 3 5 1 268 10 1 270 2 is a generator 271 2**3 = 8 is a generator 272 2**7 = 7 is a generator 273 2**9 = 6 is a generator 275 Example 2. 276 Memory space N = 512B EEPROM + 8192B FLASH + 1024B SRAM = 9728B 277 Nearest prime number q = 9733 278 q-1 = 9732= 811 x 4 x 3 279 phi(9732) = 3240 280 2 is a generator 281 generators are numbers 2**k mod q, with k less than q-1, and k prime 282 with 811, 4 and 3. 284 Example 3. 285 Memory space N = 4096B EEPROM + 262144B FLASH + 1024B SRAM= 274432 286 prime number q = 278543 287 q-1= 278542 = 2 x 11**2 x 1151 288 phi(278542) = 126500 289 5 is a generator 290 generators are numbers, 5**k mod q, with k less than q-1, prime with 291 2, 11, and 1151 293 3.2 Shifted permutation 295 Given an integer s in the range [0, q-1], the shifted permutation 296 P(g,s) is defined as 298 | [1,q-1] -> [1,q-1] 299 P(g,s)(x) | 300 | x -> s.g**x 302 In other words P(g,s)(x) = s x Pg(x). 304 Bijective MAC for Constraint Nodes November 2019 306 Because s can be written in the form s = g**d, s.g = g**(x+d), which 307 leads to a right shift. 309 The number of shifted permutations is (q-1)*phi(q-1). 311 The benefit of shifted permutation is to increase, with a low cost 312 computation, the bMAC entropy. 314 3.3 Composition in Fq 316 Given a set of k ptuples {(g1,s1), (g2,s2),..., (gk,sk)} and 317 associated shifted permutations P(gi,si), a permutation P(q,k) is 318 computed according to the relation : 320 P(q,k) = P(gk,sk) o ... o P(g2,s2) o P(g1,s1) 322 3.4 Code example 324 The bMAC is computed with a permutation P= P(g2) o P(g1,s1) 325 The pseudo code is written in a C like way. 326 H is a SHA3-256 KECCAK hash function. 328 3.4.1 Example 1 330 In this example 32 bits integers are used. 331 The prime number q is 9733. 332 The address space is N= 9664. 333 With a 8 bits processor, 12MHz clock, the bMAC is computed in about 334 10s, i.e. 1ms per byte. 336 uint32-t x,y,bitn,v,gi[14]; 337 uint32-t PRIME, g1=a-generator, s1=a-value, g2=a-generator; 338 bool tohash; 340 PRIME =9733; 341 H.reset(); 343 gi[0]= g2; 344 for (int n=1;n<=13;n++) 345 gi[n] = (gi[n-1] * gi[n-1]) % PRIME; 347 x= s1; 349 for(int i=1;i>1; 359 } 360 v = (y-1); 361 // if address v exists, read the v address content A(v) 362 // tohash=true ; 363 if (tohash) H.update(A(v)); 364 } 366 H.dofinal(); 368 3.4.2 Example 2 370 In this example 64 bits and 32 bits integers are used. 371 The prime number q is 278543. 372 The address space is N= 271360. 373 With a 8 bits processor, 16MHz clock, the bMAC is computed in about 374 320s, i.e. 1.1 ms per byte. 376 uint32-t bitn,v; 377 uint64-t x,y,gi[19]; 378 uint32-t PRIME, g1=a-generator, s1=a-value, g2=a-generator; 379 bool tohash; 381 PRIME = 278543; 382 H.reset(); 384 gi[0]=(uint64-t)g2; 385 for (n=1;n<=18;n++) 386 { gi[n] = gi[n-1] * gi[n-1]; 387 gi[n] = gi[n] % PRIME; 388 } 390 x= s1; 392 for(i=1;i>1; 405 } 406 Bijective MAC for Constraint Nodes November 2019 408 v = (uint32-t)(y-1); 409 // if address v exists, read the v address content A(v) 410 // tohash=true ; 411 if (tohash) H.update(A(v)); 412 } 414 H.final(); 416 4 bMAC protocol 418 A bMAC protocol involves a bMAC requester and a bMAC provider. 420 The requester sends to the bMAC provider the parameters needed for 421 the P permutation. 423 The bMAC provider computes the bMAC according to the P permutation 424 and returns the result. 426 If the bMAC provider has access to internet, the requester 427 (typically a gateway) SHOULD control its internet access in order to 428 avoid side channel attack. 430 5 IANA Considerations 432 TODO 434 6 Security Considerations 436 TODO 438 7 References 440 7.1 Normative References 442 7.2 Informative References 444 8 Authors' Addresses 446 Pascal Urien 447 Telecom ParisTech 448 19 Place Marguerite Perey 449 91120 Palaiseau 450 France 452 Phone: NA 453 Email: Pascal.Urien@telecom-paristech.fr