idnits 2.17.1 draft-hallambaker-mesh-udf-11.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 : ---------------------------------------------------------------------------- ** The document seems to lack an Authors' Addresses Section. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == Line 2158 has weird spacing: '... suffix srv/m...' == Line 2453 has weird spacing: '... set of point...' == Line 2454 has weird spacing: '... degree in a...' == Line 2455 has weird spacing: '...o prime to...' == Using lowercase 'not' together with uppercase 'MUST', 'SHALL', 'SHOULD', or 'RECOMMENDED' is not an accepted usage according to RFC 2119. Please use uppercase 'NOT' together with RFC 2119 keywords (if that is what you mean). Found 'MUST not' in this paragraph: UDF Binary Data Sequence types are either fixed length or variable length. A variable length Binary Data Sequence MUST be truncated for presentation. Fixed length Binary Data Sequences MUST not be truncated. == Using lowercase 'not' together with uppercase 'MUST', 'SHALL', 'SHOULD', or 'RECOMMENDED' is not an accepted usage according to RFC 2119. Please use uppercase 'NOT' together with RFC 2119 keywords (if that is what you mean). Found 'MUST not' in this paragraph: Since PKIX certificates and CLRs contain security policy information, UDF fingerprints used to identify certificates or CRLs SHOULD be presented with a minimum of 200 bits of precision. PKIX applications MUST not accept UDF fingerprints specified with less than 200 bits of precision for purposes of identifying trust anchors. -- The document date (2 November 2020) is 1263 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- -- Looks like a reference, but probably isn't: '112' on line 1119 -- Looks like a reference, but probably isn't: '113' on line 1121 == Missing Reference: 'This' is mentioned on line 2248, but not defined -- Obsolete informational reference (is this intentional?): RFC 5785 (Obsoleted by RFC 8615) Summary: 1 error (**), 0 flaws (~~), 8 warnings (==), 4 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group P. M. Hallam-Baker 3 Internet-Draft ThresholdSecrets.com 4 Intended status: Informational 2 November 2020 5 Expires: 6 May 2021 7 Mathematical Mesh 3.0 Part II: Uniform Data Fingerprint. 8 draft-hallambaker-mesh-udf-11 10 Abstract 12 This document describes the naming and addressing schemes used in the 13 Mathematical Mesh. The means of generating Uniform Data Fingerprint 14 (UDF) values and their presentation as text sequences and as URIs are 15 described. 17 A UDF consists of a binary sequence, the initial eight bits of which 18 specify a type identifier code. Type identifier codes have been 19 selected so as to provide a useful mnemonic indicating their purpose 20 when presented in Base32 encoding. 22 Two categories of UDF are described. Data UDFs provide a compact 23 presentation of a fixed length binary data value in a format that is 24 convenient for data entry. A Data UDF may represent a cryptographic 25 key, a nonce value or a share of a secret. Fingerprint UDFs provide 26 a compact presentation of a Message Digest or Message Authentication 27 Code value. 29 A Strong Internet Name (SIN) consists of a DNS name which contains at 30 least one label that is a UDF fingerprint of a policy document 31 controlling interpretation of the name. SINs allow a direct trust 32 model to be applied to achieve end-to-end security in existing 33 Internet applications without the need for trusted third parties. 35 UDFs may be presented as URIs to form either names or locators for 36 use with the UDF location service. An Encrypted Authenticated 37 Resource Locator (EARL) is a UDF locator URI presenting a service 38 from which an encrypted resource may be obtained and a symmetric key 39 that may be used to decrypt the content. EARLs may be presented on 40 paper correspondence as a QR code to securely provide a machine- 41 readable version of the same content. This may be applied to 42 automate processes such as invoicing or to provide accessibility 43 services for the partially sighted. 45 [Note to Readers] 46 Discussion of this draft takes place on the MATHMESH mailing list 47 (mathmesh@ietf.org), which is archived at 48 https://mailarchive.ietf.org/arch/search/?email_list=mathmesh. 50 This document is also available online at 51 http://mathmesh.com/Documents/draft-hallambaker-mesh-udf.html. 53 Status of This Memo 55 This Internet-Draft is submitted in full conformance with the 56 provisions of BCP 78 and BCP 79. 58 Internet-Drafts are working documents of the Internet Engineering 59 Task Force (IETF). Note that other groups may also distribute 60 working documents as Internet-Drafts. The list of current Internet- 61 Drafts is at https://datatracker.ietf.org/drafts/current/. 63 Internet-Drafts are draft documents valid for a maximum of six months 64 and may be updated, replaced, or obsoleted by other documents at any 65 time. It is inappropriate to use Internet-Drafts as reference 66 material or to cite them other than as "work in progress." 68 This Internet-Draft will expire on 6 May 2021. 70 Copyright Notice 72 Copyright (c) 2020 IETF Trust and the persons identified as the 73 document authors. All rights reserved. 75 This document is subject to BCP 78 and the IETF Trust's Legal 76 Provisions Relating to IETF Documents (https://trustee.ietf.org/ 77 license-info) in effect on the date of publication of this document. 78 Please review these documents carefully, as they describe your rights 79 and restrictions with respect to this document. 81 Table of Contents 83 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 4 84 1.1. UDF Types . . . . . . . . . . . . . . . . . . . . . . . . 5 85 1.1.1. Cryptographic Keys and Nonces . . . . . . . . . . . . 5 86 1.1.2. Fingerprint type UDFS . . . . . . . . . . . . . . . . 6 87 1.2. Using UDFs in URIs . . . . . . . . . . . . . . . . . . . 7 88 1.2.1. Name Form . . . . . . . . . . . . . . . . . . . . . . 7 89 1.2.2. Locator Form . . . . . . . . . . . . . . . . . . . . 7 90 1.3. Secure Internet Names . . . . . . . . . . . . . . . . . . 9 91 2. Definitions . . . . . . . . . . . . . . . . . . . . . . . . . 10 92 2.1. Requirements Language . . . . . . . . . . . . . . . . . . 10 93 2.2. Defined Terms . . . . . . . . . . . . . . . . . . . . . . 10 94 2.3. Related Specifications . . . . . . . . . . . . . . . . . 11 95 2.4. Implementation Status . . . . . . . . . . . . . . . . . . 11 96 3. Architecture . . . . . . . . . . . . . . . . . . . . . . . . 11 97 3.1. Base32 Presentation . . . . . . . . . . . . . . . . . . . 12 98 3.1.1. Precision Improvement . . . . . . . . . . . . . . . . 12 99 3.2. Type Identifier . . . . . . . . . . . . . . . . . . . . . 12 100 3.3. Content Type Identifier . . . . . . . . . . . . . . . . . 13 101 3.4. Truncation . . . . . . . . . . . . . . . . . . . . . . . 14 102 3.4.1. Compressed presentation . . . . . . . . . . . . . . . 14 103 3.5. Presentation . . . . . . . . . . . . . . . . . . . . . . 15 104 3.6. Alternative Presentations . . . . . . . . . . . . . . . . 15 105 3.6.1. Word Lists . . . . . . . . . . . . . . . . . . . . . 16 106 3.6.2. Image List . . . . . . . . . . . . . . . . . . . . . 16 107 4. Fixed Length UDFs . . . . . . . . . . . . . . . . . . . . . . 16 108 4.1. Nonce Type . . . . . . . . . . . . . . . . . . . . . . . 16 109 4.2. OID Identified Sequence . . . . . . . . . . . . . . . . . 17 110 4.3. Encryption/Authentication Type . . . . . . . . . . . . . 18 111 4.4. Key Pair Derivation . . . . . . . . . . . . . . . . . . . 18 112 4.4.1. Extraction step . . . . . . . . . . . . . . . . . . . 21 113 4.4.2. Elliptic Curve Diffie Hellman Key Pairs type 1-4 . . 23 114 4.4.3. Elliptic Curve Diffie Hellman Key Pairs type 5-7 . . 24 115 4.4.4. RSA Key Pairs . . . . . . . . . . . . . . . . . . . . 26 116 4.4.5. Any Key Algorithm . . . . . . . . . . . . . . . . . . 28 117 4.5. Shamir Shared Secret . . . . . . . . . . . . . . . . . . 28 118 4.5.1. Secret Generation . . . . . . . . . . . . . . . . . . 29 119 4.5.2. Recovery . . . . . . . . . . . . . . . . . . . . . . 30 120 5. Variable Length UDFs . . . . . . . . . . . . . . . . . . . . 31 121 5.1. Content Digest . . . . . . . . . . . . . . . . . . . . . 32 122 5.1.1. Content Digest Value . . . . . . . . . . . . . . . . 32 123 5.1.2. Typed Content Digest Value . . . . . . . . . . . . . 33 124 5.1.3. Content Digest Compression . . . . . . . . . . . . . 33 125 5.1.4. Content Digest Presentation . . . . . . . . . . . . . 34 126 5.1.5. Example Encoding . . . . . . . . . . . . . . . . . . 34 127 5.1.6. Using SHA-2-512 Digest . . . . . . . . . . . . . . . 35 128 5.1.7. Using SHA-3-512 Digest . . . . . . . . . . . . . . . 35 129 5.1.8. Using SHA-2-512 Digest with Compression . . . . . . . 36 130 5.1.9. Using SHA-3-512 Digest with Compression . . . . . . . 37 131 5.2. Authenticator UDF . . . . . . . . . . . . . . . . . . . . 37 132 5.2.1. Authentication Content Digest Value . . . . . . . . . 38 133 5.2.2. Authentication Value . . . . . . . . . . . . . . . . 38 134 5.3. Content Type Values . . . . . . . . . . . . . . . . . . . 40 135 5.3.1. PKIX Certificates and Keys . . . . . . . . . . . . . 41 136 5.3.2. OpenPGP Key . . . . . . . . . . . . . . . . . . . . . 41 137 5.3.3. DNSSEC . . . . . . . . . . . . . . . . . . . . . . . 42 138 6. UDF URIs . . . . . . . . . . . . . . . . . . . . . . . . . . 42 139 6.1. Name form URI . . . . . . . . . . . . . . . . . . . . . . 42 140 6.2. Locator form URI . . . . . . . . . . . . . . . . . . . . 43 141 6.2.1. DNS Web service discovery . . . . . . . . . . . . . . 43 142 6.2.2. Content Identifier . . . . . . . . . . . . . . . . . 43 143 6.2.3. Target URI . . . . . . . . . . . . . . . . . . . . . 44 144 6.2.4. Postprocessing . . . . . . . . . . . . . . . . . . . 44 145 6.2.5. Decryption and Authentication . . . . . . . . . . . . 44 146 6.2.6. QR Presentation . . . . . . . . . . . . . . . . . . . 45 147 7. Strong Internet Names . . . . . . . . . . . . . . . . . . . . 45 148 8. Security Considerations . . . . . . . . . . . . . . . . . . . 45 149 8.1. Confidentiality . . . . . . . . . . . . . . . . . . . . . 45 150 8.2. Availability . . . . . . . . . . . . . . . . . . . . . . 45 151 8.3. Integrity . . . . . . . . . . . . . . . . . . . . . . . . 45 152 8.4. Work Factor and Precision . . . . . . . . . . . . . . . . 46 153 8.5. Semantic Substitution . . . . . . . . . . . . . . . . . . 47 154 8.6. QR Code Scanning . . . . . . . . . . . . . . . . . . . . 47 155 9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 48 156 9.1. Protocol Service Name . . . . . . . . . . . . . . . . . . 48 157 9.2. Well Known . . . . . . . . . . . . . . . . . . . . . . . 48 158 9.3. URI Registration . . . . . . . . . . . . . . . . . . . . 49 159 9.4. Media Types Registrations . . . . . . . . . . . . . . . . 49 160 9.4.1. Media Type: application/pkix-keyinfo . . . . . . . . 49 161 9.4.2. Media Type: application/udf . . . . . . . . . . . . . 50 162 9.5. Uniform Data Fingerprint Type Identifier Registry . . . . 51 163 9.5.1. The name of the registry . . . . . . . . . . . . . . 51 164 9.5.2. Required information for registrations . . . . . . . 51 165 9.5.3. Applicable registration policy . . . . . . . . . . . 52 166 9.5.4. Size, format, and syntax of registry entries . . . . 52 167 9.5.5. Initial assignments and reservations . . . . . . . . 52 168 10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 53 169 11. Appendix A: Prime Values for Secret Sharing . . . . . . . . . 53 170 12. Shamir Shared Secret Recovery Using Lagrange Interpolation . 54 171 13. Normative References . . . . . . . . . . . . . . . . . . . . 57 172 14. Informative References . . . . . . . . . . . . . . . . . . . 59 174 1. Introduction 176 A Uniform Data Fingerprint (UDF) is a generalized format for 177 presenting and interpreting short binary sequences representing 178 cryptographic keys or fingerprints of data of any specified type. 179 The UDF format provides a superset of the OpenPGP [RFC4880] 180 fingerprint encoding capability with greater encoding density and 181 readability. 183 This document describes the syntax and encoding of UDFs, the means of 184 constructing and comparing them and their use in other Internet 185 addressing schemes. 187 1.1. UDF Types 189 Two categories of UDF are described. Data UDFs provide a compact 190 presentation of a fixed length binary data value in a format that is 191 convenient for data entry. A Data UDF may represent a cryptographic 192 key or nonce value or a part share of a key generated using a secret 193 sharing mechanism. Fingerprint UDFs provide a compact presentation 194 of a Message Digest or Message Authentication Code value. 196 Both categories of UDF are encoded as a UDF binary sequence, the 197 first octet of which is a Type Identifier and the remaining octets 198 specify the binary value according to the type identifier and data 199 referenced. 201 UDFs are typically presented to the user as a Base32 encoded sequence 202 in groups of four characters separated by dashes. This format 203 provides a useful balance between compactness and readability. The 204 type identifier codes have been selected so as to provide a useful 205 mnemonic when presented in Base32 encoding. 207 The following are examples of UDF values: 209 Nonce: NAB6-GXIR-GXA5-AQJO-4CNH-LWOL-EOVQ 210 Secret: 7UHC-4YPF-LDY4-2F65-7DYN-UUPC-ZY 211 SHA-2 Digest:MB5S-R4AJ-3FBT-7NHO-T26Z-2E6Y-WFH4 212 SHA-3 Digest:KCM5-7VB6-IJXJ-WKHX-NZQF-OKGZ-EWVN 213 Public Key: OAYC-4MAH-AYBS-WZLQ-AUAA-GIYA-AQQP-MS4V-LBDA-DAZ4-QM2F-5 214 GG6-OAOK-LTLA-75DS-HCXF-BAJP-TCVF-KCL4-6LI 216 Like email addresses, UDFs are not a Uniform Resource Identifier 217 (URI) but may be expressed in URI form by adding the scheme 218 identifier (UDF) for use in contexts where an identifier in URI 219 syntax is required. A UDF URI MAY contain a domain name component 220 allowing it to be used as a locator 222 1.1.1. Cryptographic Keys and Nonces 224 A Nonce (N) UDF represents a short, fixed length randomly chosen 225 binary value. 227 Nonce UDFs are used within many Mesh protocols and data formats where 228 it is necessary to represent a nonce value in text form. 230 Nonce UDF: 231 NAB6-GXIR-GXA5-AQJO-4CNH-LWOL-EOVQ 233 An Encryption/Authentication (E) UDF has the same format as a Random 234 UDF but is identified as being intended to be used as a symmetric key 235 for encryption and/or authentication. 237 KeyValue: 238 0E 2E 61 E5 58 F1 CD 17 DD F8 F0 DA 51 E2 CE 240 Encryption/Authenticator UDF: 241 7UHC-4YPF-LDY4-2F65-7DYN-UUPC-ZY 243 A Share (S) UDF also represents a short, fixed length binary value 244 but only provides one share in secret sharing scheme. Recovery of 245 the binary value requires a sufficient number of shares. 247 Share UDFs are used in the Mesh to support key and data escrow 248 operations without the need to rely on trusted hardware. A share UDF 249 can be copied by hand or printed in human or machine-readable form 250 (e.g. QR code). 252 Key: 7UHC-4YPF-LDY4-2F65-7DYN-UUPC-ZY 253 Share 0: SAQF-HCGQ-JTQ5-5YGF-PT4S-QPXL-KOPE-U 254 Share 1: SAQ2-UA3S-G7PG-JT55-4IKF-PDH4-KVM7-S 255 Share 2: SARA-A7QU-ELNO-VPVW-I4XY-NWYN-K4KX-K 257 1.1.2. Fingerprint type UDFS 259 Fingerprint type UDFs contains a fingerprint value calculated over a 260 content data item and an IANA media type. 262 A Content Digest type UDF is a fingerprint type UDF in which the 263 fingerprint is formed using a cryptographic algorithm. Two digest 264 algorithms are currently supported, SHA-2-512 (M, for Merkle Damgard) 265 and SHA-3-512 (K, for Keccak). 267 The inclusion of the media type in the calculation of the UDF value 268 provides protection against semantic substitution attacks in which 269 content that has been found to be trustworthy when interpreted as one 270 content type is presented in a context in which it is interpreted as 271 a different content type in which it is unsafe. 273 SHA-2-512: MB5S-R4AJ-3FBT-7NHO-T26Z-2E6Y-WFH4 274 SHA-3-512: KCM5-7VB6-IJXJ-WKHX-NZQF-OKGZ-EWVN 276 An Authentication UDF (A) is formed in the same manner as a 277 fingerprint but using a Message Authentication Code algorithm and a 278 symmetric key. 280 Authentication UDFs are used to express commitments and to provide a 281 means of blinding fingerprint values within a protocol by means of a 282 nonce. 284 SHA-2-512: AABD-4PN3-QGA2-IJU5-RP7H-Z5AV-I3GK 286 1.2. Using UDFs in URIs 288 The UDF URI scheme allows use of a UDF in contexts where a URF is 289 expected. The UDF URI scheme has two forms, name and locator. 291 1.2.1. Name Form 293 Name form UDF URIs identify a data resource but do not provide a 294 means of discovery. The URI is simply the scheme ("udf") followed by 295 the UDF value: 297 udf:MB5S-R4AJ-3FBT-7NHO-T26Z-2E6Y-WFH4 299 1.2.2. Locator Form 301 Locator form UDF URIs identify a data resource and provide a hint 302 that MAY provide a means of discovery. If the content is not 303 available from the location indicated, content obtained from a 304 different source that matches the fingerprint MAY be used instead. 306 udf://example.com/MB5S-R4AJ-3FBT-7NHO-T26Z-2E6Y-WFH4 308 UDF locator form URIs presenting a fingerprint type UDF provide a 309 tight binding of the content to the locator. This allows the 310 resolved content to be verified and rejected if it has been modified. 312 UDF locator form URIs presenting an Encryptor/Authenticator type UDF 313 provide a mechanism for identification, discovery and decryption of 314 encrypted content. UDF locators of this type are known as Encrypted/ 315 Authenticated Resource Locators (EARLs). 317 Regardless of the type of the embedded UDF, UDF locator form URIs are 318 resolved by first performing DNS Web Service Discovery to identify 319 the Web Service Endpoint for the mmm-udf service at the specified 320 domain. 322 Resolution is completed by presenting the Content Digest Fingerprint 323 of the UDF value specified in the URI to the specified Web Service 324 Endpoint and performing a GET method request on the result. 326 For example, Alice subscribes to Example.com, a purveyor of cat and 327 kitten images. The company generates paper and electronic invoices 328 on a monthly basis. 330 To generate the paper invoice, Example.com first creates a new 331 encryption key: 333 EAWC-UVUH-SNRX-POAM-NSLK-REVC-OEDH-BV 335 One or more electronic forms of the invoice are encrypted under the 336 key EAWC-UVUH-SNRX-POAM-NSLK-REVC-OEDH-BV and placed on the 337 Example.com Web site so that the appropriate version is returned if 338 Alice scans the QR code. 340 The key is then converted to form an EARL for the example.com UDF 341 resolution service: 343 udf://example.com/EAWC-UVUH-SNRX-POAM-NSLK-REVC-OEDH-BV 345 The EARL is then rendered as a QR code: 347 (Artwork only available as svg: No external link available, see 348 draft-hallambaker-mesh-udf-11.html for artwork.) 350 Figure 1 352 A printable invoice containing the QR code is now generated and sent 353 to Alice. 355 When Alice receives the invoice, she can pay it by simply scanning 356 the invoice with a device that recognizes at least one of the invoice 357 formats supported by Example.com. 359 The UDF EARL locator shown above is resolved by first determining the 360 Web Service Endpoint for the mmm-udf service for the domain 361 example.com. 363 Discover ("example.com", "mmm-udf") = 364 https://example.com/.well-known/mmm-udf/ 366 Next the fingerprint of the source UDF is obtained. 368 UDF (EAWC-UVUH-SNRX-POAM-NSLK-REVC-OEDH-BV) = 369 MAVL-GC7A-HV5F-JBZQ-GME7-HWDF-5Z5A-CH6L-3XUP-U2TE-KLD2-Q4VE-MFNA-DZW4 371 Combining the Web Service Endpoint and the fingerprint of the source 372 UDF provides the URI from which the content is obtained using the 373 normal HTTP GET method: 375 https://example.com/.well-known/mmm-udf/MAVL-GC7A-HV5F-JBZQ-GME7- 376 HWDF-5Z5A-CH6L-3XUP-U2TE-KLD2-Q4VE-MFNA-DZW4 378 Having established that Alice can read postal mail sent to a physical 379 address and having delivered a secret to that address, this process 380 might be extended to provide a means of automating the process of 381 enrolment in electronic delivery of future invoices. 383 1.3. Secure Internet Names 385 A SIN is an Internet Identifier that contains a UDF fingerprint of a 386 security policy document that may be used to verify the 387 interpretation of the identifier. This permits traditional forms of 388 Internet address such as URIs and RFC822 email addresses to be used 389 to express a trusted address that is independent of any trusted third 390 party. 392 This document only describes the syntax and interpretation of the 393 identifiers themselves. The means by which the security policy 394 documents bound to an address govern interpretation of the name is 395 discussed separately in [draft-hallambaker-mesh-trust]. 397 For example, Example Inc holds the domain name example.com and has 398 deployed a private CA whose root of trust is a PKIX certificate with 399 the UDF fingerprint MB2GK-6DUF5-YGYYL-JNY5E-RWSHZ. 401 Alice is an employee of Example Inc., she uses three email addresses: 403 alice@example.com A regular email address (not a SIN). 405 alice@mm--mb2gk-6duf5-ygyyl-jny5e-rwshz.example.com A strong email 406 address that is backwards compatible. 408 alice@example.com.mm--mb2gk-6duf5-ygyyl-jny5e-rwshz A strong email 409 address that is backwards incompatible. 411 All three forms of the address are valid RFC822 addresses and may be 412 used in a legacy email client, stored in an address book application, 413 etc. But the ability of a legacy client to make use of the address 414 differs. Addresses of the first type may always be used. Addresses 415 of the second type may only be used if an appropriate MX record is 416 provisioned. Addresses of the third type will always fail unless the 417 resolver understands that it is a SIN requiring special processing. 419 These rules allow Bob to send email to Alice with either 'best 420 effort' security or mandatory security as the circumstances demand. 422 2. Definitions 424 This section presents the related specifications and standard, the 425 terms that are used as terms of art within the documents and the 426 terms used as requirements language. 428 2.1. Requirements Language 430 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 431 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 432 document are to be interpreted as described in [RFC2119]. 434 2.2. Defined Terms 436 Cryptographic Digest Function A hash function that has the 437 properties required for use as a cryptographic hash function. 438 These include collision resistance, first pre-image resistance and 439 second pre-image resistance. 441 Content Type An identifier indicating how a Data Value is to be 442 interpreted as specified in the IANA registry Media Types. 444 Commitment A cryptographic primitive that allows one to commit to a 445 chosen value while keeping it hidden to others, with the ability 446 to reveal the committed value later. 448 Data Value The binary octet stream that is the input to the digest 449 function used to calculate a digest value. 451 Data Object A Data Value and its associated Content Type 453 Digest Algorithm A synonym for Cryptographic Digest Function 455 Digest Value The output of a Cryptographic Digest Function 457 Data Digest Value The output of a Cryptographic Digest Function for 458 a given Data Value input. 460 Fingerprint A presentation of the digest value of a data value or 461 data object. 463 Fingerprint Presentation The representation of at least some part of 464 a fingerprint value in human or machine-readable form. 466 Fingerprint Improvement The practice of recording a higher precision 467 presentation of a fingerprint on successful validation. 469 Fingerprint Work Hardening The practice of generating a sequence of 470 fingerprints until one is found that matches criteria that permit 471 a compressed presentation form to be used. The compressed 472 fingerprint thus being shorter than but presenting the same work 473 factor as an uncompressed one. 475 Hash A function which takes an input and returns a fixed-size 476 output. Ideally, the output of a hash function is unbiased and 477 not correlated to the outputs returned to similar inputs in any 478 predictable fashion. 480 Precision The number of significant bits provided by a Fingerprint 481 Presentation. 483 Work Factor A measure of the computational effort required to 484 perform an attack against some security property. 486 2.3. Related Specifications 488 This specification makes use of Base32 [RFC4648] encoding, SHA-2 489 [SHA-2] and SHA-3 [SHA-3] digest functions in the derivation of basic 490 fingerprints. The derivation of keyed fingerprints additionally 491 requires the use of the HMAC [RFC2014] and HKDF [RFC5869] functions. 493 Resolution of UDF URI Locators makes use of DNS Web Service Discovery 494 [draft-hallambaker-web-service-discovery]. 496 2.4. Implementation Status 498 The implementation status of the reference code base is described in 499 the companion document [draft-hallambaker-mesh-developer]. 501 3. Architecture 503 A Uniform Data Fingerprint (UDF) is a presentation of a UDF Binary 504 Data Sequence. 506 This document specifies seven UDF Binary Data Sequence types and one 507 presentation. 509 The first octet of a UDF Binary Data Sequence identifies the UDF type 510 and is referred to as the Type identifier. 512 UDF Binary Data Sequence types are either fixed length or variable 513 length. A variable length Binary Data Sequence MUST be truncated for 514 presentation. Fixed length Binary Data Sequences MUST not be 515 truncated. 517 3.1. Base32 Presentation 519 The default UDF presentation is Base32 Presentation. 521 Variable length Binary Data Sequences are truncated to an integer 522 multiple of 20 bits that provides the desired precision before 523 conversion to Base32 form. 525 Fixed length Binary Data Sequences are converted to Base32 form 526 without truncation. 528 After conversion to Base32 form, dash '-' characters are inserted 529 between groups of 4 characters to aid reading. This representation 530 improves the accuracy of both data entry and verification. 532 3.1.1. Precision Improvement 534 Precision improvement is the practice of using a high precision UDF 535 (e.g. 260 bits) calculated from content data that has been validated 536 according to a lower precision UDF (e.g. 120 bits). 538 This allows a lower precision UDF to be used in a medium such as a 539 business card where space is constrained without compromising 540 subsequent uses. 542 Applications SHOULD make use of precision improvement wherever 543 possible. 545 3.2. Type Identifier 547 A Version Identifier consists of a single byte. 549 The byte codes have been chosen so that the first character of the 550 Base32 presentation of the UDF provides a mnemonic for its type. A 551 SHA-2 fingerprint UDF will always have M (for Merkle Damgard) as the 552 initial letter, a SHA-3 fingerprint UDF will always have K (for 553 Keccak) as the initial letter, and so on. 555 The following version identifiers are specified in this document: 557 +=========+=========+==========================================+ 558 | Type ID | Initial | Algorithm | 559 +=========+=========+==========================================+ 560 | 0 | A | HMAC-SHA-2-512 | 561 +---------+---------+------------------------------------------+ 562 | 32 | E | HKDF-AES-512 | 563 +---------+---------+------------------------------------------+ 564 | 80 | K | SHA-3-512 | 565 +---------+---------+------------------------------------------+ 566 | 81 | K | SHA-3-512 (20 bits compressed) | 567 +---------+---------+------------------------------------------+ 568 | 82 | K | SHA-3-512 (30 bits compressed) | 569 +---------+---------+------------------------------------------+ 570 | 83 | K | SHA-3-512 (40 bits compressed) | 571 +---------+---------+------------------------------------------+ 572 | 84 | K | SHA-3-512 (50 bits compressed) | 573 +---------+---------+------------------------------------------+ 574 | 96 | M | SHA-2-512 | 575 +---------+---------+------------------------------------------+ 576 | 97 | M | SHA-2-512 (20 bits compressed) | 577 +---------+---------+------------------------------------------+ 578 | 98 | M | SHA-2-512 (30 bits compressed) | 579 +---------+---------+------------------------------------------+ 580 | 99 | M | SHA-2-512 (40 bits compressed) | 581 +---------+---------+------------------------------------------+ 582 | 100 | M | SHA-2-512 (50 bits compressed) | 583 +---------+---------+------------------------------------------+ 584 | 104 | N | Nonce data | 585 +---------+---------+------------------------------------------+ 586 | 112 | O | OID distinguished sequence (DER encoded) | 587 +---------+---------+------------------------------------------+ 588 | 136 | R | Random generation seed | 589 +---------+---------+------------------------------------------+ 590 | 144 | S | Shamir Secret Sharing | 591 +---------+---------+------------------------------------------+ 592 | 200 | Z | Key pair derivation | 593 +---------+---------+------------------------------------------+ 595 Table 1 597 3.3. Content Type Identifier 599 A secure cryptographic digest algorithm provides a unique digest 600 value that is probabilistically unique for a particular byte sequence 601 but does not fix the context in which a byte sequence is interpreted. 602 While such ambiguity may be tolerated in a fingerprint format 603 designed for a single specific field of use, it is not acceptable in 604 a general-purpose format. 606 For example, the SSH and OpenPGP applications both make use of 607 fingerprints as identifiers for the public keys used but using 608 different digest algorithms and data formats for representing the 609 public key data. While no such vulnerability has been demonstrated 610 to date, it is certainly conceivable that a crafty attacker might 611 construct an SSH key in such a fashion that OpenPGP interprets the 612 data in an insecure fashion. If the number of applications making 613 use of fingerprint format that permits such substitutions is 614 sufficiently large, the probability of a semantic substitution 615 vulnerability being possible becomes unacceptably large. 617 A simple control that defeats such attacks is to incorporate a 618 content type identifier within the scope of the data input to the 619 hash function. 621 3.4. Truncation 623 Different applications of fingerprints demand different tradeoffs 624 between compactness of the representation and the number of 625 significant bits. A larger the number of significant bits reduces 626 the risk of collision but at a cost to convenience. 628 Modern cryptographic digest functions such as SHA-2 produce output 629 values of at least 256 bits in length. This is considerably larger 630 than most uses of fingerprints require and certainly greater than can 631 be represented in human readable form on a business card. 633 Since a strong cryptographic digest function produces an output value 634 in which every bit in the input value affects every bit in the output 635 value with equal probability, it follows that truncating the digest 636 value to produce a finger print is at least as strong as any other 637 mechanism if digest algorithm used is strong. 639 Using truncation to reduce the precision of the digest function has 640 the advantage that a lower precision fingerprint of some data content 641 is always a prefix of a higher prefix of the same content. This 642 allows higher precision fingerprints to be converted to a lower 643 precision without the need for special tools. 645 3.4.1. Compressed presentation 647 The Content Digest UDF types make use of work factor compression. 648 Additional type identifiers are used to indicate digest values with 649 20, 30, 40 or 50 trailing zero bits allowing a UDF fingerprint 650 offering the equivalent of up to 150 bits of precision to be 651 expressed in 20 characters instead of 30. 653 To use compressed UDF identifiers, it is necessary to search for 654 content that can be compressed. If the digest algorithm used is 655 secure, this means that by definition, the fastest means of search is 656 brute force. Thus, the reduction in fingerprint size is achieved by 657 transferring the work factor from the attacker to the defender. To 658 maintain a work factor of 2^120 with a 2^80 bits, it is necessary for 659 the content generator to perform a brute force search at a cost of 660 the order of 2^40 operations. 662 For example, the smallest allowable work factor for a UDF 663 presentation of a public key fingerprint is 92 bits. This would 664 normally require a presentation with 20 significant characters. 665 Reducing this to 16 characters requires a brute force search of 666 approximately 10^(6) attempts. Reducing this to 12 characters would 667 require 10^(12) attempts and to 10 characters, 10^(15) attempts. 669 Omission of support for higher levels of compression than 2^(50) is 670 intentional. 672 In addition to allowing use of shorter presentations, work factor 673 compression MAY be used as evidence of proof of work. 675 3.5. Presentation 677 The presentation of a fingerprint is the format in which it is 678 presented to either an application or the user. 680 Base32 encoding is used to produce the preferred text representation 681 of a UDF fingerprint. This encoding uses only the letters of the 682 Latin alphabet with numbers chosen to minimize the risk of ambiguity 683 between numbers and letters (2, 3, 4, 5, 6 and 7). 685 To enhance readability and improve data entry, characters are grouped 686 into groups of four. This means that each block of four characters 687 represents an increase in work factor of approximately one million 688 times. 690 3.6. Alternative Presentations 692 Applications that support UDF MUST support use of the Base32 693 presentation. Applications MAY support alternative presentations. 695 3.6.1. Word Lists 697 The use of a Word List to encode fingerprint values was introduced by 698 Patrick Juola and Philip Zimmerman for the PGPfone application. The 699 PGP Word List is designed to facilitate exchange and verification of 700 fingerprint values in a voice application. To minimize the risk of 701 misinterpretation, two-word lists of 256 values each are used to 702 encode alternative fingerprint bytes. The compact size of the lists 703 used allowed the compilers to curate them so as to maximize the 704 phonetic distance of the words selected. 706 The PGP Word List is designed to achieve a balance between ease of 707 entry and verification. Applications where only verification is 708 required may be better served by a much larger word list, permitting 709 shorter fingerprint encodings. 711 For example, a word list with 16384 entries permits 14 bits of the 712 fingerprint to be encoded at once, 65536 entries permit encoding of 713 16 bits. These encodings allow a 120-bit fingerprint to be encoded 714 in 9 and 8 words respectively. 716 3.6.2. Image List 718 An image list is used in the same manner as a word list affording 719 rapid visual verification of a fingerprint value. For obvious 720 reasons, this approach is not suited to data entry but is preferable 721 for comparison purposes. An image list of 1,048,576 images would 722 provide a 20-bit encoding allowing 120 bit precision fingerprints to 723 be displayed in six images. 725 4. Fixed Length UDFs 727 Fixed length UDFs are used to represent cryptographic keys, nonces 728 and secret shares and have a fixed length determined by their 729 function that cannot be truncated without loss of information. 731 All fixed length Binary Data Sequence values are an integer multiple 732 of eight bits. 734 4.1. Nonce Type 736 A Nonce Type UDF consists of the type identifier octet 104 followed 737 by the Binary Data Sequence value. 739 The Binary Data Sequence value is an integer number of octets that 740 SHOULD have been generated in accordance with processes and 741 procedures that ensure that it is sufficiently unpredictable for the 742 purposes of the protocol in which the value is to be used. 743 Requirements for such processes and procedures are described in 744 [RFC4086]. 746 Nonce Type UDFs are intended for use in contexts where it is 747 necessary for a randomly chosen value to be unpredictable but not 748 secret. For example, the challenge in a challenge/response 749 mechanism. 751 4.2. OID Identified Sequence 753 An OID Identified Sequence Type UDF consists of the type identifier 754 octet 108 followed by the Binary Data Sequence value. 756 The Binary Data Sequence value is an octet sequence that contains the 757 DER encoding of the following ASN.1 data: 759 OIDInfo ::= SEQUENCE { 760 algorithm AlgorithmIdentifier, 761 data BIT STRING } 763 AlgorithmIdentifier ::= SEQUENCE { 764 algorithm OBJECT IDENTIFIER, 765 parameters ANY DEFINED BY algorithm OPTIONAL } 767 OID Identified Sequences are intended to allow arbitrary data 768 sequences to be encoded in the UDF format without exhausting the 769 limited type identifier space. 771 In particular, OID Identified Sequences MAY be used to specify public 772 and private key values. 774 Given the following Ed25519 public key: 776 F6 4B 95 58 46 01 83 3C 83 34 5E 98 DE 70 1C A5 777 CD 60 FF 47 23 8A E5 08 12 F9 8A A5 50 97 CF 2D 779 The equivalent DER encoding is: 781 30 2E 30 07 06 03 2B 65 70 05 00 03 23 00 04 20 782 F6 4B 95 58 46 01 83 3C 83 34 5E 98 DE 70 1C A5 783 CD 60 FF 47 23 8A E5 08 12 F9 8A A5 50 97 CF 2D 785 To encode this key as a UDF OID sequence we prepend the value OID and 786 convert to Base32: 788 OID: OAYC-4MAH-AYBS-WZLQ-AUAA-GIYA-AQQP-MS4V-LBDA-DAZ4-QM2F-5 789 GG6-OAOK-LTLA-75DS-HCXF-BAJP-TCVF-KCL4-6LI 791 The corresponding UDF content digest value is more compact and allows 792 us to identify the key unambiguously but does not provide the value: 794 MCUR-EHK7-INHD-EZZJ-THWJ-XWNJ-6WO2 796 4.3. Encryption/Authentication Type 798 Encryption and Authenticator Type UDFs consists of the type 799 identifier specifying the algorithm to be used on the key data 800 followed by the Binary Data Sequence value. 802 The Binary Data Sequence value is an integer number of octets that 803 SHOULD have been generated in accordance with processes and 804 procedures that ensure that it is sufficiently unpredictable and 805 unguessable for the purposes of the protocol in which the value is to 806 be used. Requirements for such processes and procedures are 807 described in [RFC4086]. 809 Encryption and Authenticator Type UDFs are intended to be used as a 810 means of specifying secret cryptographic keying material. For 811 example, the input to a Key Derivation Function used to encrypt a 812 document. Accordingly, the identifier UDF corresponding to an 813 Encryption or Authenticator type UDF is a UDF fingerprint of the UDF 814 in Base32 presentation with content type 'application/udf'. 816 4.4. Key Pair Derivation 818 The key pair derivation type is used to specify a public key pair 819 value by means of a sufficiently random input to a deterministic key 820 generation function. 822 A key pair derivation Type UDF consists of the type identifier octet 823 200 followed by the Binary Data Sequence value. 825 The first two octets of the Binary Data Sequence value comprise the 826 Key Specifier which specifies the algorithm and key uses for which 827 the private key is to be derived. 829 * Bits 6-7 of the first octet specify the key use. 831 * Bits 0-5 of the first byte and bits 0-7 of the second specify the 832 key type in network byte order. 834 In the unlikely event that this code space is ever exhausted, 835 allocation of a new UDF type code will be required. 837 The following key uses are specified: 839 +======+================+ 840 | Code | Key Use | 841 +======+================+ 842 | 0 | Any | 843 +------+----------------+ 844 | 1 | Encryption | 845 +------+----------------+ 846 | 2 | Signature | 847 +------+----------------+ 848 | 3 | Authentication | 849 +------+----------------+ 851 Table 2 853 Two types of key type are defined: Explicit and Generic. 855 Explicit key types specify a public key cryptographic algorithm and 856 all the parameters required to generate a key pair. Generic key 857 types are used to specify a type of key but not the algorithm which 858 MUST be specified when the key is generated. 860 Derivation of key pairs for the following algorithms is specified in 861 this document: 863 +======+===========+==============================+ 864 | Code | Algorithm | Description | 865 +======+===========+==============================+ 866 | 0 | Any | Seed MAY be used to generate | 867 | | | keypairs for any algorithm | 868 +------+-----------+------------------------------+ 869 | 1 | X25519 | X25519 keypair as described | 870 | | | in RFC7748 | 871 +------+-----------+------------------------------+ 872 | 2 | X448 | X448 keypair as described in | 873 | | | RFC7748 | 874 +------+-----------+------------------------------+ 875 | 3 | Ed25519 | Ed25519 keypair as described | 876 | | | in RFC8032 | 877 +------+-----------+------------------------------+ 878 | 4 | Ed448 | Ed448 keypair as described | 879 | | | in RFC8032 | 880 +------+-----------+------------------------------+ 881 | 5 | P-256 | NIST curve P-256 | 882 +------+-----------+------------------------------+ 883 | 6 | P-384 | NIST curve P-384 | 884 +------+-----------+------------------------------+ 885 | 7 | P-521 | NIST curve P-521 | 886 +------+-----------+------------------------------+ 887 | 8 | RSA-2048 | 2048 bit RSA keypair | 888 +------+-----------+------------------------------+ 889 | 9 | RSA-3072 | 3072 bit RSA keypair | 890 +------+-----------+------------------------------+ 891 | 10 | RSA-4096 | 4096 bit RSA keypair | 892 +------+-----------+------------------------------+ 894 Table 3 896 The key parameter derivation function takes as inputs, the UDF seed 897 value "seed", the parameter identifier "param" and an optional string 898 specifying a key name "keyname". 900 KeyParam (seed, param, keyname) 902 The value param is an octet sequence determined by the actual key 903 type generated. The first two octets of parm are always equal to the 904 key identifier for the key algorithm and key usage being generated. 905 If the key derivation algorithm requires multiple inputs, additional 906 octets are specified for each of the different inputs required. 908 The HKDF function [RFC5869] is used to derive key pairs for all the 909 algorithms specified in this document. Derivation functions for 910 additional key algorithms MAY use a different function for this 911 purpose provided that it meets the applicable security requirements. 913 The HKDF function is specified as a two-step extract-expand process 914 with an optional non-secret value input at both steps. 916 4.4.1. Extraction step 918 The HKDF extraction step calculates a PRK value from a "salt" and 919 "IKM": 921 HKDF-Extract(salt, IKM) -> PRK 923 The IKM value is the binary presentation of the complete Binary Data 924 Sequence as originally specified. The salt value is null. 926 The output from the extraction step forms the input to the expand 927 step: 929 HKDF-Expand(PRK, info, L) -> OKM 931 The info parameter of the HKDF function is the concatenation of 932 "alg", "param" and the UTF8 binary representation of "keyname". 934 info = alg + param + keyname.UTF8() 936 An X25519 key may be derived as follows: 938 Fingerprint = 939 ZAAA-CDJ5-DHPA-DUUW-WIPQ-UXNC-DSAR-U7A 941 IKM = 943 00 01 0D 3D 19 DE 01 D2 96 B2 1F 0A 5D A2 1C 81 944 1A 7C 946 salt = 948 00 01 950 PRK = 952 DA 2E 80 6F 2D B1 54 56 7E 27 B4 91 49 0A 35 3A 953 5D 99 92 AA A2 2F 2D 2A 50 4B 13 5B 87 DF 63 67 954 62 92 67 9C B3 B8 10 47 31 52 A2 42 FA 04 84 39 955 7A 64 15 84 C0 6B 51 F7 19 4A 20 35 BA 2E D1 59 957 OKM = 959 E7 22 39 E1 AB 77 AC 9C B4 6A A0 12 27 68 9E 28 960 14 60 2F A8 76 08 38 5E D5 E6 5D E7 0C C8 42 E8 962 Key = 964 E7 22 39 E1 AB 77 AC 9C B4 6A A0 12 27 68 9E 28 965 14 60 2F A8 76 08 38 5E D5 E6 5D E7 0C C8 42 E8 967 Derivation of an X448 key: 969 Fingerprint = 970 ZAAA-FFQA-3LE5-SAHG-E6K6-HOTN-TVLB-K4A 972 Key = 974 AE 6A 6D 0B CC 48 C3 31 E7 55 0F 52 F9 96 83 C5 975 15 7C 8A 74 80 36 B7 E9 17 24 D7 DD A1 56 76 3C 976 15 00 68 B7 23 F5 DB 32 48 1B 72 C0 2E B0 22 45 977 A3 B8 80 67 B3 88 06 9F 979 Derivation of an Ed25519 key: 981 Fingerprint = 982 ZAAA-GZ5N-PSNF-7LMS-QJZN-3O2X-GJXV-X6I 984 Key = 986 3A 36 00 56 2E EC 2F 24 A7 8C 22 F3 A9 A2 EF 1B 987 6E AF 07 D4 99 28 53 A5 5B 0A CC EE 4C 3B 7D 30 989 Derivation of an Ed448 key: 991 Fingerprint = 992 ZAAA-ILZB-KTQV-YWUK-FO7E-MQVV-EWPR-UPA 994 Key = 996 DF 5A 89 B8 1D 56 92 41 32 D1 B2 C9 4F 74 69 E3 997 C9 E5 5F 23 33 A1 CE 22 54 08 EE 53 46 0F 9B 13 998 9D 54 95 2B F9 D9 77 2A FA 07 3C 9D 89 CC C5 0E 999 7E 86 7E 84 7C 58 5D 89 1001 4.4.2. Elliptic Curve Diffie Hellman Key Pairs type 1-4 1003 The generation of key pairs for X25519, X448, Ed25519 and Ed448 is 1004 specified in [RFC7748] and [RFC8032]. In each case, the public and 1005 private key parameters are generated from a string of random octets 1006 whose transformation to the secret scalar function is described in 1007 the document. 1009 Thus, info is the null string and the value L is specified as 1010 follows: 1012 +===========+=====+ 1013 | Algorithm | L | 1014 +===========+=====+ 1015 | X25519 | 256 | 1016 +-----------+-----+ 1017 | X448 | 448 | 1018 +-----------+-----+ 1019 | Ed25519 | 256 | 1020 +-----------+-----+ 1021 | Ed448 | 448 | 1022 +-----------+-----+ 1024 Table 4 1026 4.4.3. Elliptic Curve Diffie Hellman Key Pairs type 5-7 1028 The generation of key pairs for the curves P-256, P-384 and P-521 1029 described in [RFC5903] is not mandated by the specification. FIPS 1030 186-4 specifies two approaches. A modified form of the mechanism Key 1031 Pair Generation Using Extra Random Bits specified in B.4.1 is used as 1032 follows: 1034 The number of random bits L is given by the following table: 1036 +===========+=====+ 1037 | Algorithm | L | 1038 +===========+=====+ 1039 | P-256 | 320 | 1040 +-----------+-----+ 1041 | P-384 | 448 | 1042 +-----------+-----+ 1043 | p-521 | 592 | 1044 +-----------+-----+ 1046 Table 5 1048 Note that this rounds up the number of random bits required to the 1049 nearest integer multiple of 8. 1051 The OKM value is interpreted as an integer in Network Byte Order, 1052 that is the first byte contains the most significant bits, to yield 1053 the parameter "c". 1055 The parameter "c" is reduced modulo the value of the prime field "n" 1056 to yield the secret scalar value d: 1058 d = (c mod (n?1)) + 1. 1060 A P-256 key may be derived as follows: 1062 Fingerprint = 1063 ZAAA-LLBO-4A4E-LFMH-EJ73-XVFG-7PZ5-V7Y 1065 IKM = 1067 00 05 AC 2E E0 38 45 95 87 22 7F BB D4 A6 FB F3 1068 DA FF 1070 salt = 1072 00 05 1074 PRK = 1076 0F 48 0F 0C 93 30 AE EE 41 FD 8F A2 1C C2 C6 CA 1077 3A E1 4B 54 E7 83 C0 25 85 F0 CD 2A 65 3F 18 A7 1078 9F 2A 5A ED 6A E3 64 6A 05 7D 1A 1A B8 68 B3 F3 1079 4F A9 10 9A 05 E1 A4 9A 2C CC 40 43 36 8A 24 C0 1081 OKM = 1083 E2 00 EC 22 63 17 D5 E5 52 F9 CD B6 45 23 A9 8B 1084 EF 32 26 E0 24 A0 E7 2B 7F CB C2 0B CB FA 0F 5C 1085 59 D1 7C 4A D8 12 2E 4C 1087 Key = 823521039787465146191678159095729811571036184098859836027994 1088 10986678676075099 1090 Derivation of a P-384 key: 1092 Fingerprint = 1093 ZAAA-NPLI-G7Z3-WFD2-GBJ6-OONN-ELTO-MHA 1095 Key = 369049211431889063087900251703207474490953076630513949620729 1096 23012683284321458397574918591433311657724460124046828583 1098 Derivation of a P-521 key: 1100 Fingerprint = 1101 ZAAA-PQCC-YFVT-LRWP-7MUZ-GJV3-HLX2-JPQ 1103 Key = 634654264002940134552342747000178673315150389242882127875899 1104 96717989335708073735991026483008684752699986204269344550 1105 4370476919922072068801363203357706689700 1107 4.4.4. RSA Key Pairs 1109 Generation of RSA key pairs requires two parameters, p, q which are 1110 prime. 1112 The value of the param input used to calculate info is the value of 1113 the key identifier value with one of the following "tag" values 1114 concatenated to the end. 1116 +===========+=======+========================+ 1117 | Parameter | Tag | UTF8 equivalent string | 1118 +===========+=======+========================+ 1119 | p | [112] | "p" | 1120 +-----------+-------+------------------------+ 1121 | q | [113] | "q" | 1122 +-----------+-------+------------------------+ 1124 Table 6 1126 The value of L is the same for generating the OKM values from which q 1127 are derived and is determined by the algorithm identifier: 1129 +===========+======+ 1130 | Algorithm | L | 1131 +===========+======+ 1132 | RSA-2048 | 1024 | 1133 +-----------+------+ 1134 | RSA-3072 | 1536 | 1135 +-----------+------+ 1136 | RSA-4096 | 2048 | 1137 +-----------+------+ 1139 Table 7 1141 The RSA parameter p is the smallest prime integer that is greater 1142 than the OKM value corresponding to the info value "p" interpreted as 1143 an integer in Network Byte Order. 1145 The RSA parameter q is the smallest prime integer that is greater 1146 than the OKM value corresponding to the info value "q" interpreted as 1147 an integer in Network Byte Order. 1149 Note that this algorithm does not mandate a particular method of 1150 primality testing nor does it impose any additional testing on the 1151 values p or q. If an application requires the use of primes with 1152 conditions it will be necessary to attempt multiple key derivations 1153 with different Binary Data Sequence values until parameters with the 1154 desired properties are found. 1156 An RSA-2048 may be derived as follows: 1158 Fingerprint = 1159 ZAAA-RJ5I-OSMI-X2KH-MBHX-KUPB-OC54-NQI 1161 IKM = 1163 00 08 A7 A8 74 98 8B E9 47 60 4F 75 51 E1 70 BB 1164 C6 C1 1166 salt = 1168 00 08 1170 [Generation of the PRK as before] 1172 Info(p) = 1174 70 1176 OKM(p) = 1178 92 D4 DA FA C4 22 DB 17 B0 04 93 C6 F1 D2 7A AF 1179 34 6F 69 98 54 1A F5 F3 E3 ED DA 98 F5 64 EE 6A 1181 Info(q) = 1183 71 1185 OKM(q) = 1187 01 50 07 9F B3 53 70 5A 7E 95 63 BD 19 8D 52 59 1188 2F EE 38 E7 8F D4 46 D9 4C 55 E6 DD 39 CA DB 36 1190 Key P = 664137588122357253348380132353218815863396125741622195396345 1191 89986848279686793 1193 Key Q = 593713231506709718978311683387355253795918273379156509909895 1194 725618914057069 1196 4.4.5. Any Key Algorithm 1198 The Any key algorithm allows a single UDF value to be used to derive 1199 key pairs for multiple algorithms. The IKM value is the same for 1200 each key pair derived. The salt value is changed according to the 1201 algorithm for which the key is to be derived. 1203 Fingerprint = 1204 ZAAA-A6WP-XMGW-FUOF-2T5L-AHNL-FBPY-RSY 1206 To generate an RSA-2048 key 1208 salt = 1210 00 08 1212 Key P = 184377705562733023433840697873299239654937691662139401284561 1213 64676903354830137 1215 Key Q = 741016989403010251265552685128898155357242513700210607224783 1216 50575007811846521 1218 To generate an X25519 key 1220 salt = 1222 00 08 1224 Key = 1225 System.Byte[] 1227 4.5. Shamir Shared Secret 1229 The UDF format MAY be used to encode shares generated by a secret 1230 sharing mechanism. The only secret sharing mechanism currently 1231 supported is the Shamir Secret Sharing mechanism [Shamir79]. Each 1232 secret share represents a point represents a point _on (x, f(x))_, a 1233 polynomial in a modular field _p_. The secret being shared is an 1234 integer multiple of 32 bits represented by the polynomial value 1235 _f(0)_. 1237 A Shamir Shared Secret Type UDF consists of the type identifier octet 1238 144 followed by the Binary Data Sequence value describing the share 1239 value. 1241 The first octet of the Binary Data Sequence value specifies the 1242 threshold value and the x value of the particular share: 1244 * Bits 4-7 of the first byte specify the threshold value. 1246 * Bits 0-3 of the first byte specify the x value minus 1. 1248 The remaining octets specify the value _f(x)_ in network byte (big- 1249 endian) order with leading padding if necessary so that the share has 1250 the same number of bytes as the secret. 1252 The algorithm requires that the value _p_ be a prime larger than the 1253 integer representing the largest secret being shared. For 1254 compactness of representation we chose _p_ to be the smallest prime 1255 that is greater than 2_^(n)_ where _n_ is an integer multiple of 32. 1256 This approach leaves a small probability that a set of chosen 1257 polynomial parameters cause one or more share values be larger than 1258 2_^(n)_. Since it is the value of the secret rather than the 1259 polynomial parameters that is of important, such parameters MUST NOT 1260 be used. 1262 4.5.1. Secret Generation 1264 To share a secret of _L_ bits with a threshold of _n_ we use a _f(x)_ 1265 a polynomial of degree _n_ in the modular field _p_: 1267 f(x) = a_(0) + a_(1).x + a_(2).x^(2) + ... a_(n).x^(n) 1269 where: 1271 L Is the length of the secret in bits, an integer multiple of 32. 1273 n Is the threshold, the number of shares required to reconstitute 1274 the secret. 1276 a_(0) Is the integer representation of the secret to be shared. 1278 a_(1) ... a_(n) Are randomly chosen integers less than p 1280 p Is the smallest prime that is greater than 2^(L). 1282 For L=128, p = 2^(128)+51. 1284 The values of the key shares are the values _f_(1), _f_(2),..._f_(n). 1286 The most straightforward approach to generation of Shamir secrets is 1287 to generate the set of polynomial coefficients, a_(0), a_(1), ... 1288 a_(n) and use these to generate the share values _f_(1), 1289 _f_(2),..._f_(n). 1291 Note that if this approach is adopted, there is a small probability 1292 that one or more of the values _f_(1), _f_(2),..._f_(n) exceeds the 1293 range of values supported by the encoding. Should this occur, at 1294 least one of the polynomial coefficients MUST be replaced. 1296 An alternative means of generating the set of secrets is to select up 1297 to _n-1_ secret share values and use secret recovery to determine at 1298 least one additional share. If _n_ shares are selected, the shared 1299 secret becomes an output of rather than an input to the process. 1301 4.5.2. Recovery 1303 To recover the value of the shared secret, it is necessary to obtain 1304 sufficient shares to meet the threshold and recover the value _f(0)_ 1305 = a_(0). 1307 Applications MAY employ any approach that returns the correct result. 1308 The use of Lagrange basis polynomials is described in Appendix C. 1310 Alice decides to encrypt an important document and split the 1311 encryption key so that there are five key shares, three of which will 1312 be required to recover the key. 1314 Alice's master secret is 1315 25 18 66 60 51 71 C2 D0 1B D6 35 87 8C E9 36 DD 1317 This has the UDF representation: 1319 EUMG-MYCR-OHBN-AG6W-GWDY-Z2JW-3U 1321 The master secret is converted to an integer applying network byte 1322 order conventions. Since the master secret is 128 bits, it is 1323 guaranteed to be smaller than the modulus. The resulting value 1324 becomes the polynomial value a0. 1326 Since a threshold of three shares is required, we will need a second 1327 order polynomial. The co-efficients of the polynomial a1, a2 are 1328 random numbers smaller than the modulus: 1330 a0 = 49308127405535711391456941988672779997 1331 a1 = 179511727511453208422954989056409550439 1332 a2 = 70411201569169043952907800785616474236 1334 The master secret is the value f(0) = a0. The key shares are the 1335 values f(1), f(2)...f(5): 1337 f(1) = 299231056486157963767319731830698804672 1338 f(2) = 9411654863241377122248908380421354805 1339 f(3) = 200697023299601341846368293933145064917 1340 f(4) = 192522427953360931012928673625333511994 1341 f(5) = 325170235745458608085304654888754907543 1343 The first byte of each share specifies the recovery information 1344 (quorum, x value), the remaining bytes specify the share value in 1345 network byte order: 1347 f(1) = 1348 30 E1 1D CE 21 70 45 C4 F8 6B 63 18 4F 15 AC 05 1349 C0 1350 f(2) = 1351 31 07 14 9E 69 33 61 AF 2A 2E E9 0C F1 34 E9 F5 1352 35 1353 f(3) = 1354 32 96 FC D7 37 9A C5 81 65 66 68 13 6D EA A3 05 1355 D5 1356 f(4) = 1357 33 90 D6 78 8C A6 71 3B AA 11 E0 2B C5 36 D7 37 1358 3A 1359 f(5) = 1360 34 F4 A1 82 68 56 64 DD F8 31 51 55 F7 19 86 89 1361 97 1363 The UDF presentation of the key shares is thus: 1365 f(1) = SAYO-CHOO-EFYE-LRHY-NNRR-QTYV-VQC4-A 1366 f(2) = SAYQ-OFE6-NEZW-DLZK-F3UQ-Z4JU-5H2T-K 1367 f(3) = SAZJ-N7GX-G6NM-LALF-MZUB-G3PK-UMC5-K 1368 f(4) = SAZZ-BVTY-RSTH-CO5K-CHQC-XRJW-243T-U 1369 f(5) = SA2P-JIMC-NBLG-JXPY-GFIV-L5YZ-Q2EZ-O 1371 To recover the value f(0) from any three shares, we need to fit a 1372 polynomial curve to the three points and use it to calculate the 1373 value at x=0 using the Lagrange polynomial basis. 1375 5. Variable Length UDFs 1377 Variable length UDFs are used to represent fingerprint values 1378 calculated over a content type identifier and the cryptographic 1379 digest of a content data item. The fingerprint value MAY be 1380 specified at any integer multiple of 20 bits that provides a work 1381 factor sufficient for the intended purpose. 1383 Two types of fingerprint are specified: 1385 Digest fingerprints Are computed with the same cryptographic digest 1386 algorithm used to calculate the digest of the content data. 1388 Message Authentication Code fingerprints Are computed using a 1389 Message Authentication Code. 1391 For a given algorithm (and key, if requires), if two UDF fingerprints 1392 are of the same content data and content type, either the fingerprint 1393 values will be the same or the initial characters of one will be 1394 exactly equal to the other. 1396 5.1. Content Digest 1398 A Content Digest Type UDF consists of the type identifier octet 1399 followed by the Binary Data Sequence value. 1401 The type identifier specifies the digest algorithm used and the 1402 compression level. Two digest algorithms are currently specified 1403 with four compression levels for each making a total of eight 1404 possible type identifiers. 1406 The Content Digest UDF for given content data is generated by the 1407 steps of: 1409 0. Applying the digest algorithm to determine the Content Digest 1410 Value 1412 1. Applying the digest algorithm to determine the Typed Content 1413 Digest Value 1415 2. Determining the compression level from bytes 0-3 of the Typed 1416 Content Digest Value. 1418 3. Determining the Type Identifier octet from the Digest algorithm 1419 identifier and compression level. 1421 4. Truncating bytes 4-63 of the Typed Content Digest Value to 1422 determine the Binary Data Sequence value. 1424 5.1.1. Content Digest Value 1426 The Content Digest Value (CDV) is determined by applying the digest 1427 algorithm to the content data: 1429 CDV = H() 1431 Where 1432 H(x) is the cryptographic digest function 1434 is the binary data. 1436 5.1.2. Typed Content Digest Value 1438 The Typed Content Digest Value (TCDV) is determined by applying the 1439 digest algorithm to the content type identifier and the CDV: 1441 TCDV = H ( + ?:? + CDV) 1443 Where 1445 A + B represents concatenation of the binary sequences A and B. 1447 is the IANA Content Type of the data in UTF8 encoding 1449 The two-step approach to calculating the Type Content Digest Value 1450 allows an application to attempt to match a set of content data 1451 against multiple types without the need to recalculate the value of 1452 the content data digest. 1454 5.1.3. Content Digest Compression 1456 The compression factor is determined according to the number of 1457 trailing zero bits in the first 8 bytes of the Typed Content Digest 1458 Value as follows: 1460 19 or fewer trailing zero bits Compression factor = 0 1462 29 or fewer trailing zero bits Compression factor = 20 1464 39 or fewer trailing zero bits Compression factor = 30 1466 49 or fewer trailing zero bits Compression factor = 40 1468 50 or more trailing zero bits Compression factor = 50 1470 The least significant bits of each octet are regarded to be 1471 'trailing'. 1473 Applications MUST use compression when creating and comparing UDFs. 1474 Applications MAY support content generation techniques that search 1475 for UDF values that use a compressed representation. Presentation of 1476 a content digest value indicating use of compression MAY be used as 1477 an indicator of 'proof of work'. 1479 5.1.4. Content Digest Presentation 1481 The type identifier is determined by the algorithm and compression 1482 factor as follows: 1484 +=========+=========+===========+=============+ 1485 | Type ID | Initial | Algorithm | Compression | 1486 +=========+=========+===========+=============+ 1487 | 80 | K | SHA-3-512 | 0 | 1488 +---------+---------+-----------+-------------+ 1489 | 81 | K | SHA-3-512 | 20 | 1490 +---------+---------+-----------+-------------+ 1491 | 82 | K | SHA-3-512 | 30 | 1492 +---------+---------+-----------+-------------+ 1493 | 83 | K | SHA-3-512 | 40 | 1494 +---------+---------+-----------+-------------+ 1495 | 84 | K | SHA-3-512 | 50 | 1496 +---------+---------+-----------+-------------+ 1497 | 96 | M | SHA-2-512 | 0 | 1498 +---------+---------+-----------+-------------+ 1499 | 97 | M | SHA-2-512 | 20 | 1500 +---------+---------+-----------+-------------+ 1501 | 98 | M | SHA-2-512 | 30 | 1502 +---------+---------+-----------+-------------+ 1503 | 99 | M | SHA-2-512 | 40 | 1504 +---------+---------+-----------+-------------+ 1505 | 100 | M | SHA-2-512 | 50 | 1506 +---------+---------+-----------+-------------+ 1508 Table 8 1510 The Binary Data Sequence value is taken from the Typed Content Digest 1511 Value starting at the 9^(th) octet and as many additional bytes as 1512 are required to meet the presentation precision. 1514 5.1.5. Example Encoding 1516 In the following examples, is the UTF8 encoding of the 1517 string "text/plain" and is the UTF8 encoding of the string 1518 "UDF Data Value" 1520 Data = 1521 55 44 46 20 44 61 74 61 20 56 61 6C 75 65 1523 ContentType = 1524 74 65 78 74 2F 70 6C 61 69 6E 1526 5.1.6. Using SHA-2-512 Digest 1528 H() = 1529 48 DA 47 CC AB FE A4 5C 76 61 D3 21 BA 34 3E 58 1530 10 87 2A 03 B4 02 9D AB 84 7C CE D2 22 B6 9C AB 1531 02 38 D4 E9 1E 2F 6B 36 A0 9E ED 11 09 8A EA AC 1532 99 D9 E0 BD EA 47 93 15 BD 7A E9 E1 2E AD C4 15 1534 + ':' + H() = 1535 74 65 78 74 2F 70 6C 61 69 6E 3A 48 DA 47 CC AB 1536 FE A4 5C 76 61 D3 21 BA 34 3E 58 10 87 2A 03 B4 1537 02 9D AB 84 7C CE D2 22 B6 9C AB 02 38 D4 E9 1E 1538 2F 6B 36 A0 9E ED 11 09 8A EA AC 99 D9 E0 BD EA 1539 47 93 15 BD 7A E9 E1 2E AD C4 15 1541 H( + ':' + H()) = 1542 C6 AF B7 C0 FE BE 04 E5 AE 94 E3 7B AA 5F 1A 40 1543 5B A3 CE CC 97 4D 55 C0 9E 61 E4 B0 EF 9C AE F9 1544 EB 83 BB 9D 5F 0F 39 F6 5F AA 06 DC 67 2A 67 71 1545 4F FF 8F 83 C4 55 38 36 38 AE 42 7A 82 9C 85 BB 1547 The prefixed Binary Data Sequence is thus 1548 60 C6 AF B7 C0 FE BE 04 E5 AE 94 E3 7B AA 5F 1A 1549 40 5B A3 CE CC 97 4D 55 C0 9E 61 E4 B0 EF 9C AE 1550 F9 EB 83 BB 9D 5F 0F 39 F6 5F AA 06 DC 67 2A 67 1551 71 4F FF 8F 83 C4 55 38 36 38 AE 42 7A 82 9C 85 1553 The 125 bit fingerprint value is MDDK-7N6A-727A-JZNO-STRX-XKS7-DJAF 1555 This fingerprint MAY be specified with higher or lower precision as 1556 appropriate. 1558 100 bit precision MDDK-7N6A-727A-JZNO-STRX 1560 120 bit precision MDDK-7N6A-727A-JZNO-STRX-XKS7 1562 200 bit precision MDDK-7N6A-727A-JZNO-STRX-XKS7-DJAF-XI6O-ZSLU-2VOA 1564 260 bit precision MDDK-7N6A-727A-JZNO-STRX-XKS7-DJAF-XI6O-ZSLU-2VOA- 1565 TZQ6-JMHP-TSXP 1567 5.1.7. Using SHA-3-512 Digest 1568 H() = 1569 6D 2E CF E6 93 5A 0C FC F2 A9 1A 49 E0 0C D8 07 1570 A1 4E 70 AB 72 94 6E CC BB 47 48 F1 8E 41 49 95 1571 07 1D F3 6E 0D 0C 8B 60 39 C1 8E B4 0F 6E C8 08 1572 65 B4 C4 45 9B A2 7E 97 74 7B BE 68 BC A8 C2 17 1574 + ':' + H() = 1575 74 65 78 74 2F 70 6C 61 69 6E 3A 6D 2E CF E6 93 1576 5A 0C FC F2 A9 1A 49 E0 0C D8 07 A1 4E 70 AB 72 1577 94 6E CC BB 47 48 F1 8E 41 49 95 07 1D F3 6E 0D 1578 0C 8B 60 39 C1 8E B4 0F 6E C8 08 65 B4 C4 45 9B 1579 A2 7E 97 74 7B BE 68 BC A8 C2 17 1581 H( + ':' + H()) = 1582 8A 86 8A 06 1C 54 6E 7E 3F 75 5F 39 88 F9 FD 2F 1583 8E C8 45 93 1B 80 A8 2F 29 16 7B A3 BE 21 1F 8A 1584 75 61 88 A1 D5 7F 07 D5 9D 68 A4 2D 17 F4 4D 23 1585 F9 E4 0B B2 1A 8D B9 F5 8D FC EC BD 01 F4 37 7C 1587 The prefixed Binary Data Sequence is thus 1588 50 8A 86 8A 06 1C 54 6E 7E 3F 75 5F 39 88 F9 FD 1589 2F 8E C8 45 93 1B 80 A8 2F 29 16 7B A3 BE 21 1F 1590 8A 75 61 88 A1 D5 7F 07 D5 9D 68 A4 2D 17 F4 4D 1591 23 F9 E4 0B B2 1A 8D B9 F5 8D FC EC BD 01 F4 37 1593 The 125 bit fingerprint value is KCFI-NCQG-DRKG-47R7-OVPT-TCHZ-7UXY 1595 5.1.8. Using SHA-2-512 Digest with Compression 1597 The content data "UDF Compressed Document 4187123" produces a UDF 1598 Content Digest SHA-2-512 binary value with 20 trailing zeros and is 1599 therefore presented using compressed presentation: 1601 Data = " 1602 55 44 46 20 43 6F 6D 70 72 65 73 73 65 64 20 44 1603 6F 63 75 6D 65 6E 74 20 34 31 38 37 31 32 33" 1605 The UTF8 Content Digest is given as: 1607 H() = 1608 36 21 FA 2A C5 D8 62 5C 2D 0B 45 FB 65 93 FC 69 1609 C1 ED F7 00 AE 6F E3 3D 38 13 FE AB 76 AA 74 13 1610 6D 5A 2B 20 DE D6 A5 CF 6C 04 E6 56 3F F3 C0 C7 1611 C4 1D 3F 43 DD DC F1 A5 67 A7 E0 67 9A B0 C6 B7 1613 + ':' + H() = 1614 74 65 78 74 2F 70 6C 61 69 6E 3A 36 21 FA 2A C5 1615 D8 62 5C 2D 0B 45 FB 65 93 FC 69 C1 ED F7 00 AE 1616 6F E3 3D 38 13 FE AB 76 AA 74 13 6D 5A 2B 20 DE 1617 D6 A5 CF 6C 04 E6 56 3F F3 C0 C7 C4 1D 3F 43 DD 1618 DC F1 A5 67 A7 E0 67 9A B0 C6 B7 1620 H( + ':' + H()) = 1621 8E 14 D9 19 4E D6 02 12 C3 30 A7 BB 5F C7 17 6D 1622 AE 9A 56 7C A8 2A 23 1F 96 75 ED 53 10 EC E8 F2 1623 60 14 24 D0 C8 BC 55 3D C0 70 F7 5E 86 38 1A 0B 1624 CB 55 9C B2 87 81 27 FF 3C EC E2 F0 90 A0 00 00 1626 The prefixed Binary Data Sequence is thus 1627 61 8E 14 D9 19 4E D6 02 12 C3 30 A7 BB 5F C7 17 1628 6D AE 9A 56 7C A8 2A 23 1F 96 75 ED 53 10 EC E8 1629 F2 60 14 24 D0 C8 BC 55 3D C0 70 F7 5E 86 38 1A 1630 0B CB 55 9C B2 87 81 27 FF 3C EC E2 F0 90 A0 00 1632 The 125 bit fingerprint value is MGHB-JWIZ-J3LA-EEWD-GCT3-WX6H-C5W2 1634 5.1.9. Using SHA-3-512 Digest with Compression 1636 The content data "UDF Compressed Document 774665" produces a UDF 1637 Content Digest SHA-3-512 binary value with 20 trailing zeros and is 1638 therefore presented using compressed presentation: 1640 Data = 1641 55 44 46 20 43 6F 6D 70 72 65 73 73 65 64 20 44 1642 6F 63 75 6D 65 6E 74 20 37 37 34 36 36 35 1644 The UTF8 SHA-3-512 Content Digest is KEJI-Y225-BDUG-XX22-MXKE-5ITF- 1645 YVYM 1647 5.2. Authenticator UDF 1649 An authenticator Type UDF consists of the type identifier octet 1650 followed by the Binary Data Sequence value. 1652 The type identifier specifies the digest and Message Authentication 1653 Code algorithm. Two algorithm suites are currently specified. Use 1654 of compression is not supported. 1656 The Authenticator UDF for given content data and key is generated by 1657 the steps of: 1659 0. Applying the digest algorithm to determine the Content Digest 1660 Value 1662 1. Applying the MAC algorithm to determine the Authentication value 1664 2. Determining the Type Identifier octet from the Digest algorithm 1665 identifier and compression level. 1667 3. Truncating the Authentication value to determine the Binary Data 1668 Sequence value. 1670 The key used to calculate and Authenticator type UDF is always a 1671 UNICODE string. If use of a binary value as a key is required, the 1672 value MUST be converted to a string format first. For example, by 1673 conversion to an Encryption/Authentication type UDF. 1675 5.2.1. Authentication Content Digest Value 1677 The Content Digest Value (CDV) is determined in the exact same 1678 fashion as for a Content Digest UDF by applying the digest algorithm 1679 to the content data: 1681 CDV = H()) 1683 Where 1685 H(x) is the cryptographic digest function 1687 is the binary data. 1689 5.2.2. Authentication Value 1691 The Authentication Value (AV) is determined by applying the digest 1692 algorithm to the content type identifier and the CDV: 1694 AV = MAC (, ( + ?:? + CDV)) 1696 Where 1698 is the authentication key as specified below 1700 MAC( , ) is the result of applying the Message 1701 Authentication Code algorithm to with Key and data 1703 The value is calculated as follows: 1705 IKM = UTF8 (Key) 1706 PRK = MAC (UTF8 ("KeyedUDFMaster"), IKM) 1707 OKM = HKDF-Expand(PRK, UTF8 ("KeyedUDFExpand"), HashLen) 1709 Where the function UTF8(string) converts a string to the binary UTF8 1710 representation, HKDF-Expand is as defined in [RFC5869] and the 1711 function MAC(k,m) is the HMAC function formed from the specified hash 1712 H(m) as specified in [RFC2014]. 1714 Keyed UDFs are typically used in circumstances where user interaction 1715 requires a cryptographic commitment type functionality 1717 In the following example, is the UTF8 encoding of the 1718 string "text/plain" and is the UTF8 encoding of the string 1719 "Konrad is the traitor". The randomly chosen key is NDD7-6CMX-H2FW- 1720 ISAL-K4VB-DQ3E-PEDM. 1722 Data = 1723 4B 6F 6E 72 61 64 20 69 73 20 74 68 65 20 74 72 1724 61 69 74 6F 72 1726 ContentType = 1727 74 65 78 74 2F 70 6C 61 69 6E 1729 Key = 1730 4E 44 44 37 2D 36 43 4D 58 2D 48 32 46 57 2D 49 1731 53 41 4C 2D 4B 34 56 42 2D 44 51 33 45 2D 50 45 1732 44 4D 1734 Processing is performed in the same manner as an unkeyed fingerprint 1735 except that compression is never used: 1737 H() = 1738 93 FC DA F9 FA FD 1E 26 50 26 C3 C1 28 43 40 73 1739 D8 BC 3D 62 87 73 2B 73 B8 EC 93 B6 DE 80 FF DA 1740 70 0A D1 CE E8 F4 36 68 EF 4E 71 63 41 53 91 5C 1741 CE 8C 5C CE C7 9A 46 94 6A 35 79 F9 33 70 85 01 1743 + ':' + H() = 1744 74 65 78 74 2F 70 6C 61 69 6E 3A 93 FC DA F9 FA 1745 FD 1E 26 50 26 C3 C1 28 43 40 73 D8 BC 3D 62 87 1746 73 2B 73 B8 EC 93 B6 DE 80 FF DA 70 0A D1 CE E8 1747 F4 36 68 EF 4E 71 63 41 53 91 5C CE 8C 5C CE C7 1748 9A 46 94 6A 35 79 F9 33 70 85 01 1750 PRK(Key) = 1751 77 D3 0A 08 39 BD 9D C0 97 44 DA 33 15 0A 42 5E 1752 CD 17 80 03 B3 CF CC 89 7A C7 84 12 B4 51 5B 25 1753 DC 26 F5 E1 1B 20 F3 89 2E 9A 1A 7B 0E 73 23 39 1754 0E C3 4C EF 2D 40 DA 05 B4 70 C6 1C 82 C1 49 33 1756 HKDF(Key) = 1757 BF A9 B4 58 9C 1D 68 D7 9A B7 11 F6 C8 98 59 14 1758 20 D7 82 67 C5 84 22 E5 A0 F9 93 52 B1 C3 87 EB 1759 05 06 CB C4 E4 D6 E6 EE 1F F0 D4 7A 97 68 5E CE 1760 28 1C CA AF D8 B5 D1 24 4A 71 EC E3 AC B5 D2 04 1762 MAC(, + ':' + H()) = 1763 4C C3 7F D3 F9 9E 52 CF 07 90 74 53 84 65 95 BC 1764 1A 2B A5 D1 68 9D 05 6D 06 C5 CA BF 17 CB E0 49 1765 95 39 57 08 79 C4 E5 49 D3 3A 59 A3 32 05 45 A6 1766 30 26 25 AE 8A F4 47 C6 1F B5 33 7F AD 69 A6 30 1768 The prefixed Binary Data Sequence is thus 1769 00 4C C3 7F D3 F9 9E 52 CF 07 90 74 53 84 65 95 1770 BC 1A 2B A5 D1 68 9D 05 6D 06 C5 CA BF 17 CB E0 1771 49 95 39 57 08 79 C4 E5 49 D3 3A 59 A3 32 05 45 1772 A6 30 26 25 AE 8A F4 47 C6 1F B5 33 7F AD 69 A6 1774 The 125 bit fingerprint value is ABGM-G76T-7GPF-FTYH-SB2F-HBDF-SW6B 1776 5.3. Content Type Values 1778 While a UDF fingerprint MAY be used to identify any form of static 1779 data, the use of a UDF fingerprint to identify a public key signature 1780 key provides a level of indirection and thus the ability to identify 1781 dynamic data. The content types used to identify public keys are 1782 thus of particular interest. 1784 As described in the security considerations section, the use of 1785 fingerprints to identify a bare public key and the use of 1786 fingerprints to identify a public key and associated security policy 1787 information are quite different. 1789 5.3.1. PKIX Certificates and Keys 1791 UDF fingerprints MAY be used to identify PKIX certificates, CRLs and 1792 public keys in the ASN.1 encoding used in PKIX certificates. 1794 Since PKIX certificates and CLRs contain security policy information, 1795 UDF fingerprints used to identify certificates or CRLs SHOULD be 1796 presented with a minimum of 200 bits of precision. PKIX applications 1797 MUST not accept UDF fingerprints specified with less than 200 bits of 1798 precision for purposes of identifying trust anchors. 1800 PKIX certificates, keys and related content data are identified by 1801 the following content types: 1803 application/pkix-cert A PKIX Certificate 1805 application/pkix-crl A PKIX CRL 1807 application/pkix-keyinfo The SubjectPublicKeyInfo structure defined 1808 in the PKIX certificate specification encoded using DER encoding 1809 rules. 1811 The SubjectPublicKeyInfo structure is defined in [RFC5280] as 1812 follows: 1814 SubjectPublicKeyInfo ::= SEQUENCE { 1815 algorithm AlgorithmIdentifier, 1816 subjectPublicKey BIT STRING } 1818 This schema results in an identical DER encoding to the "OIDInfo" 1819 sequence specified in section XXX. The distinction between these 1820 productions is that the "OIDInfo" schema is intended to be used to 1821 encode arbitrary data while the application/pkix-keyinfo content type 1822 is only intended to be used to describe public keys. 1824 5.3.2. OpenPGP Key 1826 OpenPGPv5 keys and key set content data are identified by the 1827 following content type: 1829 application/pgp-keys An OpenPGP key set. 1831 5.3.3. DNSSEC 1833 DNSSEC record data consists of DNS records which are identified by 1834 the following content type: 1836 application/dns A DNS resource record in binary format 1838 6. UDF URIs 1840 The UDF URI scheme describes a means of constructing URIs from a UDF 1841 value. 1843 Two forms or UDF URI are specified, Name and Locator. In both cases 1844 the URI MUST specify the scheme type ""UDF"", and a UDF fingerprint 1845 and MAY specify a query identifier and/or a fragment identifier. 1847 By definition a Locator form URI contains an "authority" field which 1848 MUST be a DNS domain name. The use of IP address forms for this 1849 purpose is not permitted. 1851 Name Form URIs allow static content data to be identified without 1852 specifying the means by which the content data may be retrieved. 1853 Locator form URIs allow static content data or dynamic network 1854 resources to be identified and the means of retrieval. 1856 The syntax of a UDF URI is a subset of the generic URI syntax 1857 specified in [RFC3986]. The use of userinfo and port numbers is not 1858 supported and the path part of the uri is a UDF in base32 1859 presentation. 1861 URI = "UDF:" udf [ "?" query ] [ "" fragment ] 1863 udf = name-form / locator-form 1865 name-form = udf-value 1866 locator-form = "//" authority "/" udf-value 1868 authority = host 1869 host = reg-name 1871 6.1. Name form URI 1873 Name form UDF URIs provide a means of presenting a UDF value in a 1874 context in which a URI form of a name is required without providing a 1875 means of resolution. 1877 Adding the UDF scheme prefix to a UDF fingerprint does not change the 1878 semantics of the fingerprint itself. The semantics of the name 1879 result from the context in which it is used. 1881 For example, a UDF value of any type MAY be used to give a unique 1882 targetNamespace value in an XML Schema [XMLSchema] 1884 6.2. Locator form URI 1886 The locator form of an unkeyed UDF URI is resolved by the following 1887 steps: 1889 * Use DNS Web service discovery to determine the Web Service 1890 Endpoint. 1892 * Determine the content identifier from the source URI. 1894 * Append the content identifier to the Web Service Endpoint as a 1895 suffix to form the target URI. 1897 * Retrieve content from the Web Service Endpoint by means of a GET 1898 method. 1900 * Perform post processing as specified by the UDF type. 1902 6.2.1. DNS Web service discovery 1904 DNS Web Discovery is performed as specified in 1905 [draft-hallambaker-web-service-discovery] for the service "mmm-udf" 1906 and domain name specified in the URI. For a full description of the 1907 discovery mechanism, consult the referenced specification. 1909 The use of DNS Web Discovery permits service providers to make full 1910 use of the load balancing and service description capabilities 1911 afforded by use of DNS SRV and TXT records in accordance with the 1912 approach described in [RFC6763]. 1914 If no SRV or TXT records are specified, DNS Web Discovery specifies 1915 that the Web Service Endpoint be the Well Known Service [RFC5785] 1916 with the prefix "/.well-known/srv/mmm-udf." 1918 6.2.2. Content Identifier 1920 For all UDF types other than Secret Share, the Content Identifier 1921 value is the UDF SHA-2-512 Content Digest of the canonical form of 1922 the UDF specified in the source URI presented at twice the precision 1923 to a maximum of 440 bits. 1925 If the UDF is of type Secret Share, the shared secret MUST be 1926 recovered before the content identifier can be resolved. The shared 1927 secret is then expressed as a UDF of type Encryption/Authentication 1928 and the Content Identifier determined as for an Encryption/ 1929 Authentication type UDF. 1931 6.2.3. Target URI 1933 The target URI is formed by appending a slash separator '/' and the 1934 Content Identifier value to the Web Service Endpoint. 1936 Since the path portion of a URI is case sensitive, the UDF value MUST 1937 be specified in upper case and MUST include separator marks. 1939 6.2.4. Postprocessing 1941 After retrieving the content data, the resolver MUST perform post 1942 processing as indicated by the content type: 1944 Nonce No additional post processing is required. 1946 Content Digest The resolver MUST verify that the content returned 1947 matches the UDF fingerprint value. 1949 Authenticator The resolver MUST verify that the content returned 1950 matches the UDF fingerprint value. 1952 Encryption/Authentication The content data returned is decrypted and 1953 authenticated using the key specified in the UDF value as the 1954 initial keying material (see below). 1956 Secret Share (set) The content data returned is decrypted and 1957 authenticated using the shared secret as the initial keying 1958 material (see below). 1960 6.2.5. Decryption and Authentication 1962 The steps performed to decode cryptographically enhanced content data 1963 depends on the content type specified in the returned content. Two 1964 formats are currently supported: 1966 * DARE Envelope format as specified in [draft-hallambaker-mesh-dare] 1968 * Cryptographic Message Syntax (CMS) Symmetric Key Package as 1969 specified in [RFC6031] 1971 6.2.6. QR Presentation 1973 Encoding of a UDF URI as a QR code requires only the characters in 1974 alphanumeric encoding, thus achieving compactness with minimal 1975 overhead. 1977 7. Strong Internet Names 1979 A Strong Internet Name is an Internet address that is bound to a 1980 policy governing interpretation of that address by means of a Content 1981 Digest type UDF of the policy expressed as a UDF prefixed DNS label 1982 within the address itself. 1984 The Reserved LDH labels as defined in [RFC5890] that begin with the 1985 prefix "mm--" are reserved for use as Strong Internet Names. The 1986 characters following the prefix are a Content Digest type UDF in 1987 Base32 presentation. 1989 Since DNS labels are limited to 63 characters, the presentation of 1990 the SIN itself is limited to 59 characters and thus 240 bits of 1991 precision. 1993 8. Security Considerations 1995 This section describes security considerations arising from the use 1996 of UDF in general applications. 1998 Additional security considerations for use of UDFs in Mesh services 1999 and applications are described in the Mesh Security Considerations 2000 guide [draft-hallambaker-mesh-security]. 2002 8.1. Confidentiality 2004 Encrypted locator is a bearer token 2006 8.2. Availability 2008 Corruption of a part of a shared secret may prevent recovery 2010 8.3. Integrity 2012 Shared secret parts do not contain context information to specify 2013 which secret they relate to. 2015 8.4. Work Factor and Precision 2017 A given UDF data object has a single fingerprint value that may be 2018 presented at different precisions. The shortest legitimate precision 2019 with which a UDF fingerprint may be presented has 96 significant bits 2021 A UDF fingerprint presents the same work factor as any other 2022 cryptographic digest function. The difficulty of finding a second 2023 data item that matches a given fingerprint is 2^n and the difficulty 2024 or finding two data items that have the same fingerprint is 2^(n/2). 2025 Where n is the precision of the fingerprint. 2027 For the algorithms specified in this document, n = 512 and thus the 2028 work factor for finding collisions is 2^256, a value that is 2029 generally considered to be computationally infeasible. 2031 Since the use of 512 bit fingerprints is impractical in the type of 2032 applications where fingerprints are generally used, truncation is a 2033 practical necessity. The longer a fingerprint is, the less likely it 2034 is that a user will check every character. It is therefore important 2035 to consider carefully whether the security of an application depends 2036 on second pre-image resistance or collision resistance. 2038 In most fingerprint applications, such as the use of fingerprints to 2039 identify public keys, the fact that a malicious party might generate 2040 two keys that have the same fingerprint value is a minor concern. 2041 Combined with a flawed protocol architecture, such a vulnerability 2042 may permit an attacker to construct a document such that the 2043 signature will be accepted as valid by some parties but not by 2044 others. 2046 For example, Alice generates keypairs until two are generated that 2047 have the same 100 bit UDF presentation (typically 2^48 attempts). 2048 She registers one keypair with a merchant and the other with her 2049 bank. This allows Alice to create a payment instrument that will be 2050 accepted as valid by one and rejected by the other. 2052 The ability to generate of two PKIX certificates with the same 2053 fingerprint and different certificate attributes raises very 2054 different and more serious security concerns. For example, an 2055 attacker might generate two certificates with the same key and 2056 different use constraints. This might allow an attacker to present a 2057 highly constrained certificate that does not present a security risk 2058 to an application for purposes of gaining approval and an 2059 unconstrained certificate to request a malicious action. 2061 In general, any use of fingerprints to identify data that has 2062 security policy semantics requires the risk of collision attacks to 2063 be considered. For this reason, the use of short, 'user friendly' 2064 fingerprint presentations (Less than 200 bits) SHOULD only be used 2065 for public key values. 2067 8.5. Semantic Substitution 2069 Many applications record the fact that a data item is trusted, rather 2070 fewer record the circumstances in which the data item is trusted. 2071 This results in a semantic substitution vulnerability which an 2072 attacker may exploit by presenting the trusted data item in the wrong 2073 context. 2075 The UDF format provides protection against high level semantic 2076 substitution attacks by incorporating the content type into the input 2077 to the outermost fingerprint digest function. The work factor for 2078 generating a UDF fingerprint that is valid in both contexts is thus 2079 the same as the work factor for finding a second preimage in the 2080 digest function (2^512 for the specified digest algorithms). 2082 It is thus infeasible to generate a data item such that some 2083 applications will interpret it as a PKIX key and others will accept 2084 as an OpenPGP key. While attempting to parse a PKIX key as an 2085 OpenPGP key is virtually certain to fail to return the correct key 2086 parameters it cannot be assumed that the attempt is guaranteed to 2087 fail with an error message. 2089 The UDF format does not provide protection against semantic 2090 substitution attacks that do not affect the content type. 2092 8.6. QR Code Scanning 2094 The act of scanning a QR code SHOULD be considered equivalent to 2095 clicking on an unlabeled hypertext link. Since QR codes are scanned 2096 in many different contexts, the mere act of scanning a QR code MUST 2097 NOT be interpreted as constituting an affirmative acceptance of terms 2098 or conditions or as creating an electronic signature. 2100 If such semantics are required in the context of an application, 2101 these MUST be established by secondary user actions made subsequent 2102 to the scanning of the QR code. 2104 There is a risk that use of QR codes to automate processes such as 2105 payment will lead to abusive practices such as presentation of 2106 fraudulent invoices for goods not ordered or delivered. It is 2107 therefore important to ensure that such requests are subject to 2108 adequate accountability controls. 2110 9. IANA Considerations 2112 Registrations are requested in the following registries: 2114 * Service Name and Transport Protocol Port Number 2116 * well-known URI registry 2118 * Uniform Resource Identifier (URI) Schemes 2120 * Media Types 2122 In addition, the creation of the following registry is requested: 2123 Uniform Data Fingerprint Type Identifier Registry. 2125 9.1. Protocol Service Name 2127 The following registration is requested in the Service Name and 2128 Transport Protocol Port Number Registry in accordance with [RFC6355] 2130 Service Name (REQUIRED) mmm-udf 2132 Transport Protocol(s) (REQUIRED) TCP 2134 Assignee (REQUIRED) Phillip Hallam-Baker, phill@hallambaker.com 2136 Contact (REQUIRED) Phillip Hallam-Baker, phill@hallambaker.com 2138 Description (REQUIRED) mmm-udf is a Web Service protocol that 2139 resolves Mathematical Mesh Uniform Data Fingerprints (UDF) to 2140 resources. The mmm-udf service name is used in service discovery 2141 to identify a Web Service endpoint to perform resolution of a UDF 2142 presented in URI locator form. 2144 Reference (REQUIRED) [This document] 2146 Port Number (OPTIONAL) None 2148 Service Code (REQUIRED for DCCP only) None 2150 Known Unauthorized Uses (OPTIONAL) None 2152 Assignment Notes (OPTIONAL) None 2154 9.2. Well Known 2156 The following registration is requested in the well-known URI 2157 registry in accordance with [RFC5785] 2158 URI suffix srv/mmm-udf 2160 Change controller Phillip Hallam-Baker, phill@hallambaker.com 2162 Specification document(s): [This document] 2164 Related information 2166 [draft-hallambaker-web-service-discovery] 2168 9.3. URI Registration 2170 The following registration is requested in the Uniform Resource 2171 Identifier (URI) Schemes registry in accordance with [RFC7595] 2173 Scheme name: UDF 2175 Status: Provisional 2177 Applications/protocols that use this scheme name: Mathematical Mesh 2178 Service protocols (mmm) 2180 Contact: Phillip Hallam-Baker mailto:phill@hallambaker.com 2182 Change controller: Phillip Hallam-Baker 2184 References: [This document] 2186 9.4. Media Types Registrations 2188 9.4.1. Media Type: application/pkix-keyinfo 2190 Type name: application 2192 Subtype name: pkix-keyinfo 2194 Required parameters: None 2196 Optional parameters: None 2198 Encoding considerations: Binary 2200 Security considerations: Described in [This] 2202 Interoperability considerations: None 2204 Published specification: [This] 2205 Applications that use this media type: Uniform Data Fingerprint 2207 Fragment identifier considerations: None 2209 Additional information: Deprecated alias names for this type: None 2211 Magic number(s): None 2213 File extension(s): None 2215 Macintosh file type code(s): None 2217 Person & email address to contact for further information: Phillip 2218 Hallam-Baker @hallambaker.com> 2220 Intended usage: Content type identifier to be used in constructing 2221 UDF Content Digests and Authenticators and related cryptographic 2222 purposes. 2224 Restrictions on usage: None 2226 Author: Phillip Hallam-Baker 2228 Change controller: Phillip Hallam-Baker 2230 Provisional registration? (standards tree only): Yes 2232 9.4.2. Media Type: application/udf 2234 Type name: application 2236 Subtype name: udf 2238 Required parameters: None 2240 Optional parameters: None 2242 Encoding considerations: None 2244 Security considerations: Described in [This] 2246 Interoperability considerations: None 2248 Published specification: [This] 2250 Applications that use this media type: Uniform Data Fingerprint 2252 Fragment identifier considerations: None 2253 Additional information: Deprecated alias names for this type: None 2255 Magic number(s): None 2257 File extension(s): None 2259 Macintosh file type code(s): None 2261 Person & email address to contact for further information: Phillip 2262 Hallam-Baker @hallambaker.com> 2264 Intended usage: Content type identifier to be used in constructing 2265 UDF Content Digests and Authenticators and related cryptographic 2266 purposes. 2268 Restrictions on usage: None 2270 Author: Phillip Hallam-Baker 2272 Change controller: Phillip Hallam-Baker 2274 Provisional registration? (standards tree only): Yes 2276 9.5. Uniform Data Fingerprint Type Identifier Registry 2278 This document describes a new extensible data format employing fixed 2279 length version identifiers for UDF types. 2281 9.5.1. The name of the registry 2283 Uniform Data Fingerprint Type Identifier Registry 2285 9.5.2. Required information for registrations 2287 Registrants must specify the Type identifier code(s) requested, 2288 description and RFC number for the corresponding standards action 2289 document. 2291 The standards document must specify the means of generating and 2292 interpreting the UDF Data Sequence Value and the purpose(s) for which 2293 it is proposed. 2295 Since the initial letter of the Base32 presentation provides a 2296 mnemonic function in UDFs, the standards document must explain why 2297 the proposed Type Identifier and associated initial letter are 2298 appropriate. In cases where a new initial letter is to be created, 2299 there must be an explanation of why this is appropriate. If an 2300 existing initial letter is to be created, there must be an 2301 explanation of why this is appropriate and/or acceptable. 2303 9.5.3. Applicable registration policy 2305 Due to the intended field of use (human data entry), the code space 2306 is severely constrained. Accordingly, it is intended that code point 2307 registrations be as infrequent as possible. 2309 Registration of new digest algorithms is strongly discouraged and 2310 should not occur unless, (1) there is a known security vulnerability 2311 in one of the two schemes specified in the original assignment and 2312 (2) the proposed algorithm has been subjected to rigorous peer 2313 review, preferably in the form of an open, international competition 2314 and (3) the proposed algorithm has been adopted as a preferred 2315 algorithm for use in IETF protocols. 2317 Accordingly, the applicable registration policy is Standards Action. 2319 9.5.4. Size, format, and syntax of registry entries 2321 Each registry entry consists of a single byte code, 2323 9.5.5. Initial assignments and reservations 2325 The following entries should be added to the registry as initial 2326 assignments: 2328 Code Description Reference 2329 --- ------------------- --------- 2330 00 HMAC and SHA-2-512 [This document] 2331 32 HKDF-AES-512 [This document] 2332 80 SHA-3-512 [This document] 2333 81 SHA-3-512 with 20 trailing zeros [This document] 2334 82 SHA-3-512 with 30 trailing zeros [This document] 2335 82 SHA-3-512 with 40 trailing zeros [This document] 2336 83 SHA-3-512 with 50 trailing zeros [This document] 2337 96 SHA-2-512 [This document] 2338 97 SHA-2-512 with 20 trailing zeros [This document] 2339 98 SHA-2-512 with 30 trailing zeros [This document] 2340 99 SHA-2-512 with 40 trailing zeros [This document] 2341 100 SHA-2-512 with 50 trailing zeros [This document] 2342 104 Random nonce [This document] 2343 144 Shamir Secret Share [This document] 2345 10. Acknowledgements 2347 A list of people who have contributed to the design of the Mesh is 2348 presented in [draft-hallambaker-mesh-architecture]. 2350 Thanks are due to Viktor Dukhovni, Damian Weber and an anonymous 2351 member of the cryptography@metzdowd.com list for assisting in the 2352 compilation of the table of prime values. 2354 11. Appendix A: Prime Values for Secret Sharing 2356 The following are the prime values to be used for sharing secrets of 2357 up to 512 bits. 2359 If it is necessary to share larger secrets, the corresponding prime 2360 may be found by choosing a value (2^(32))^(n) that is larger than the 2361 secret to be encoded and determining the next largest number that is 2362 prime. 2364 +================+======================+ 2365 | Number of bits | Offset = Primen - 2n | 2366 +================+======================+ 2367 | 32 | 15 | 2368 +----------------+----------------------+ 2369 | 64 | 13 | 2370 +----------------+----------------------+ 2371 | 96 | 61 | 2372 +----------------+----------------------+ 2373 | 128 | 51 | 2374 +----------------+----------------------+ 2375 | 160 | 7 | 2376 +----------------+----------------------+ 2377 | 192 | 133 | 2378 +----------------+----------------------+ 2379 | 224 | 735 | 2380 +----------------+----------------------+ 2381 | 256 | 297 | 2382 +----------------+----------------------+ 2383 | 288 | 127 | 2384 +----------------+----------------------+ 2385 | 320 | 27 | 2386 +----------------+----------------------+ 2387 | 352 | 55 | 2388 +----------------+----------------------+ 2389 | 384 | 231 | 2390 +----------------+----------------------+ 2391 | 416 | 235 | 2392 +----------------+----------------------+ 2393 | 448 | 211 | 2394 +----------------+----------------------+ 2395 | 480 | 165 | 2396 +----------------+----------------------+ 2397 | 512 | 75 | 2398 +----------------+----------------------+ 2400 Table 9 2402 For example, the prime to be used to share a 128 bit value is 2^(128) 2403 + 51. 2405 12. Shamir Shared Secret Recovery Using Lagrange Interpolation 2407 The value of a Shamir Shared secret may be recovered using Lagrange 2408 basis polynomials. 2410 To share a secret with a threshold of _n_ shares and L bits we 2411 constructed _f(x)_ a polynomial of degree _n_ in the modular field 2412 _p_ where _p_ is the smallest prime greater than 2^(L): 2414 f(x) = a_(0) + a_(1).x + a_(2).x^(2) + ... a_(n).x^(n) 2416 The shared secret is the binary representation of the value a_(0) 2418 Given _n_ shares (_x_(0)_, _y_(0)_), (_x_(1)_, _y_(1)_), ... 2419 (_x_(n-1)_, _y_(n-1)_), The corresponding the Lagrange basis 2420 polynomials _l_(0)_, _l_(1)_, .. _l_(n-1)_ are given by: 2422 lm = ((x - x(m_(0))) / (x(m) - x(m_(0)))) . ((x - x(m_(1))) / (x(m) - 2423 x(m_(1)))) . ... . ((x - x(m_(n-2))) / (x(m) - x(m_(n-2)))) 2425 Where the values m_(0), m_(1), ... m_(n-2), are the integers 0, 1, .. 2426 _n_-1, excluding the value _m_. 2428 These can be used to compute _f(x)_ as follows: 2430 f(x) = y_(0)l_(0) + y_(1)l_(1) + ... y_(n-1)l_(n-1) 2432 Since it is only the value of _f(0)_ that we are interested in, we 2433 compute the Lagrange basis for the value _x_ = 0: 2435 lz_(m) = ((x(m_(1))) / (x(m) - x(m_(1)))) . ((x(m_(2))) / (x(m) - 2436 x(m_(2)))) 2438 Hence, 2440 a_(0) = f(0) = y_(0)lz_(0) + y_(1)lz_(1) + ... y_(n-1)l_(n-1) 2442 The following C# code recovers the values. 2444 using System; 2445 using System.Collections.Generic; 2446 using System.Numerics; 2448 namespace Examples { 2450 class Examples { 2452 /// 2453 /// Combine a set of points (x, f(x)) 2454 /// on a polynomial of degree in a 2455 /// discrete field modulo prime to 2456 /// recover the value f(0) using Lagrange basis polynomials. 2457 /// 2458 /// The values f(x). 2459 /// The values for x. 2460 /// The modulus. 2461 /// The polynomial degree. 2462 /// The value f(0). 2463 static BigInteger CombineNK( 2464 BigInteger[] fx, 2465 int[] x, 2466 BigInteger p, 2467 int n) { 2468 if (fx.Length < n) { 2469 throw new Exception("Insufficient shares"); 2470 } 2472 BigInteger accumulator = 0; 2473 for (var formula = 0; formula < n; formula++) { 2474 var value = fx[formula]; 2476 BigInteger numerator = 1, denominator = 1; 2477 for (var count = 0; count < n; count++) { 2478 if (formula == count) { 2479 continue; // If not the same value 2480 } 2482 var start = x[formula]; 2483 var next = x[count]; 2485 numerator = (numerator * -next) % p; 2486 denominator = (denominator * (start - next)) % p; 2487 } 2489 var InvDenominator = ModInverse(denominator, p); 2491 accumulator = Modulus((accumulator + 2492 (fx[formula] * numerator * InvDenominator)), p); 2493 } 2495 return accumulator; 2496 } 2498 /// 2499 /// Compute the modular multiplicative inverse of the value 2500 /// modulo 2501 /// 2502 /// The value to find the inverse of 2503 /// The modulus. 2504 /// 2505 static BigInteger ModInverse( 2506 BigInteger k, 2507 BigInteger p) { 2508 var m2 = p - 2; 2509 if (k < 0) { 2510 k = k + p; 2511 } 2513 return BigInteger.ModPow(k, m2, p); 2514 } 2516 /// 2517 /// Calculate the modulus of a number with correct handling 2518 /// for negative numbers. 2519 /// 2520 /// Value 2521 /// The modulus. 2522 /// x mod p 2523 public static BigInteger Modulus( 2524 BigInteger x, 2525 BigInteger p) { 2526 var Result = x % p; 2527 return Result.Sign >= 0 ? Result : Result + p; 2528 } 2529 } 2530 } 2532 13. Normative References 2534 [draft-hallambaker-mesh-architecture] 2535 Hallam-Baker, P., "Mathematical Mesh 3.0 Part I: 2536 Architecture Guide", Work in Progress, Internet-Draft, 2537 draft-hallambaker-mesh-architecture-14, 27 July 2020, 2538 . 2541 [draft-hallambaker-mesh-dare] 2542 Hallam-Baker, P., "Mathematical Mesh 3.0 Part III : Data 2543 At Rest Encryption (DARE)", Work in Progress, Internet- 2544 Draft, draft-hallambaker-mesh-dare-08, 27 July 2020, 2545 . 2548 [draft-hallambaker-mesh-security] 2549 Hallam-Baker, P., "Mathematical Mesh 3.0 Part VII: 2550 Security Considerations", Work in Progress, Internet- 2551 Draft, draft-hallambaker-mesh-security-05, 27 July 2020, 2552 . 2555 [draft-hallambaker-web-service-discovery] 2556 Hallam-Baker, P., "DNS Web Service Discovery", Work in 2557 Progress, Internet-Draft, draft-hallambaker-web-service- 2558 discovery-04, 27 July 2020, . 2561 [RFC2014] Weinrib, A. and J. Postel, "IRTF Research Group Guidelines 2562 and Procedures", BCP 8, RFC 2014, DOI 10.17487/RFC2014, 2563 October 1996, . 2565 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 2566 Requirement Levels", BCP 14, RFC 2119, 2567 DOI 10.17487/RFC2119, March 1997, 2568 . 2570 [RFC3986] Berners-Lee, T., Fielding, R., and L. Masinter, "Uniform 2571 Resource Identifier (URI): Generic Syntax", STD 66, 2572 RFC 3986, DOI 10.17487/RFC3986, January 2005, 2573 . 2575 [RFC4648] Josefsson, S., "The Base16, Base32, and Base64 Data 2576 Encodings", RFC 4648, DOI 10.17487/RFC4648, October 2006, 2577 . 2579 [RFC5280] Cooper, D., Santesson, S., Farrell, S., Boeyen, S., 2580 Housley, R., and W. Polk, "Internet X.509 Public Key 2581 Infrastructure Certificate and Certificate Revocation List 2582 (CRL) Profile", RFC 5280, DOI 10.17487/RFC5280, May 2008, 2583 . 2585 [RFC5869] Krawczyk, H. and P. Eronen, "HMAC-based Extract-and-Expand 2586 Key Derivation Function (HKDF)", RFC 5869, 2587 DOI 10.17487/RFC5869, May 2010, 2588 . 2590 [RFC5903] Fu, D. and J. Solinas, "Elliptic Curve Groups modulo a 2591 Prime (ECP Groups) for IKE and IKEv2", RFC 5903, 2592 DOI 10.17487/RFC5903, June 2010, 2593 . 2595 [RFC6031] Turner, S. and R. Housley, "Cryptographic Message Syntax 2596 (CMS) Symmetric Key Package Content Type", RFC 6031, 2597 DOI 10.17487/RFC6031, December 2010, 2598 . 2600 [RFC7748] Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves 2601 for Security", RFC 7748, DOI 10.17487/RFC7748, January 2602 2016, . 2604 [RFC8032] Josefsson, S. and I. Liusvaara, "Edwards-Curve Digital 2605 Signature Algorithm (EdDSA)", RFC 8032, 2606 DOI 10.17487/RFC8032, January 2017, 2607 . 2609 [SHA-2] NIST, "Secure Hash Standard", August 2015. 2611 [SHA-3] Dworkin, M. J., "SHA-3 Standard: Permutation-Based Hash 2612 and Extendable-Output Functions", August 2015. 2614 14. Informative References 2616 [draft-hallambaker-mesh-developer] 2617 Hallam-Baker, P., "Mathematical Mesh: Reference 2618 Implementation", Work in Progress, Internet-Draft, draft- 2619 hallambaker-mesh-developer-10, 27 July 2020, 2620 . 2623 [draft-hallambaker-mesh-trust] 2624 Hallam-Baker, P., "Mathematical Mesh 3.0 Part VI: The 2625 Trust Mesh", Work in Progress, Internet-Draft, draft- 2626 hallambaker-mesh-trust-06, 27 July 2020, 2627 . 2630 [RFC4086] Eastlake 3rd, D., Schiller, J., and S. Crocker, 2631 "Randomness Requirements for Security", BCP 106, RFC 4086, 2632 DOI 10.17487/RFC4086, June 2005, 2633 . 2635 [RFC4880] Callas, J., Donnerhacke, L., Finney, H., Shaw, D., and R. 2636 Thayer, "OpenPGP Message Format", RFC 4880, 2637 DOI 10.17487/RFC4880, November 2007, 2638 . 2640 [RFC5785] Nottingham, M. and E. Hammer-Lahav, "Defining Well-Known 2641 Uniform Resource Identifiers (URIs)", RFC 5785, 2642 DOI 10.17487/RFC5785, April 2010, 2643 . 2645 [RFC5890] Klensin, J., "Internationalized Domain Names for 2646 Applications (IDNA): Definitions and Document Framework", 2647 RFC 5890, DOI 10.17487/RFC5890, August 2010, 2648 . 2650 [RFC6355] Narten, T. and J. Johnson, "Definition of the UUID-Based 2651 DHCPv6 Unique Identifier (DUID-UUID)", RFC 6355, 2652 DOI 10.17487/RFC6355, August 2011, 2653 . 2655 [RFC6763] Cheshire, S. and M. Krochmal, "DNS-Based Service 2656 Discovery", RFC 6763, DOI 10.17487/RFC6763, February 2013, 2657 . 2659 [RFC7595] Thaler, D., Hansen, T., and T. Hardie, "Guidelines and 2660 Registration Procedures for URI Schemes", BCP 35, 2661 RFC 7595, DOI 10.17487/RFC7595, June 2015, 2662 . 2664 [Shamir79] Shamir, A., "How to share a secret.", 1979. 2666 [XMLSchema] 2667 Gao, S., Sperberg-McQueen, C. M., Thompson, H. S., 2668 Mendelsohn, N., Beech, D., and M. Maloney, "W3C XML Schema 2669 Definition Language (XSD) 1.1 Part 1: Structures", 5 April 2670 2012.