Decentralized Autonomic Data (DAD) and ? the three R’s of Key Management A White Paper from Rebooting the Web of Trust VI by Samuel M. Smith Ph.D. with Vishal Gupta

ABSTRACT This paper proposes a new class of data. ealled decentralized autonomic data (DAD). The term decentralized ‘means that the governance of the data may not reside with a single party. A related concept is that the trust in the data provenance is diffuse in nature. Central to the approach is leveraging the emerging DID (decentralized identifier) standard. The term autonomic means self-managing or self-regulating, In the context of data, we crytlu he maning of el managing o et xptogphie e o maiianng i provnanen it ks the. Aot g, < aorfing n e scwtog, Tlod threy st s o rplegaphle eyt gt foprovkt ot of st fr do gy 0 et h (et ovr ransormadon of data, e.g. provenance. Thus key management must be a first order property of DADs. This includes key reproduction, rotation, and recovery. The pre-rotation and hybrid recovery methods presented herein are Tho motving s f DAD i 0 provid provenaac o strsaming da that gt and procscd itimted e ith docnrained snsermanco.Sienin: ot ar tpialy et o v et n agregata foform highr e ontructs. Aplicaon o anlytis and nimentadon of At web o internet of things (ToT) applications. Of particular interest s the use of DADs in self-sovereign reputation systems. A DAD seeks to maintain a provenance chain for data undergoing various processing stages that follows it trat sty prineies i e . ko n oo, Streaming data applications may impose significant performance demands on the processing of the associated i, Comsenly one o gl 1 1 it el o providin th atanomi rapic, T

nap .

a2 o Named Sponsors for the Reboofing the Web of Trust VI Design Workshop

oyanis DesenaldnononicData .

‘means finding minimally sufficient means for managing keys and cryptographic integrity. Importantly this paper provides detailed descriptions of the minimally sufficient means for key reproduction, rotation, and recovery for DID leveraged DADS. OVERVIEW A decontralized autanomie data (DAD) item is assaciated with a decentralized idontificr, (DID). This paper docs not.provided a detailed definition of DIDs but docs deseribe how DIDs are used by a DAD. The DID syntax specification is a modification of standard URL syntax per REC 3986 As such, it benofits from familiaricy, which s a boon to adoption. Onc of the features of a DID is that it i a slf ccrtifying identifier in that a DID includes cither a public key or a fingerprint of & public key from a cryptographic public/private ke pair. Therehy a signature ereated with the private key can be verified using the public key provided by the DID. Tho inclusion of the public part of a cyplographic key pair in the DID give the DID other desirable propertics. These include miversal uniquencss and pseuodnynmity. Because a cryptographic key pair is generated from large random mumber there is an infintessimal chance that any two DIDs are the same (collision resistance). Another way to deseribe a DID s that it is a cryplonyin, a cryptographically derived pseudonym. Associated with a DID is a DID Document (DDO). The DDO provides meta-data about the DID that can be used o manago the DID as well as discover services affiliatod with the DID. Typically the DDO is meant to be provided by some service. The DID/DDO model is not & good maich for streaming data especially if a new DID/DDO pair would need to be crcated for cach new DAD item. But a DID/DDO is a good match when usod as the root or master identifier from which an identificr for the DAD is derived. This derived identifier is called a derived DID or DDID. Thus only one DID/DDO paring s required to manage a large number of DADs where each DAD may have a unique DDID. The syntax for a DDID is identical for a DID. The difference is that only one DDO with meta-data is needed for the root, DI and all the DAD items earry any additional DAD-specific ‘meta-data, this making them self-contained (autonomic). DID Syntax A DID or DDID has the following roquired syntax

did:method: 1dstring The method is some short string that namespaces the DID and provides for unique behavior in the associated method specification. In this paper we will use the method dad. The idstring rmust be

universally unique. The idstring can have multiple colon *" separated ports, thus allowing for namespacing. In this document the frst part of the idstring is linked to the public member of a cryplographic Key pair that is defined by the method. In this paper we will use 44-character Base64 URL-File safe encoding as per REC-4645, with one trailing pad byte of the 32-byte public verification key for an EADSA (Ed23519) signing Key pair. Unless otherwise specified Base6d in this document refers to the URL-File safe version of Base64. The URL-File safe version of Base64 encoding replaces plus *+" with minus *” and slash "1 with underscore *_" As an example a DID using this formiat would be as follows; 04/26/18 Decentralized AutonomicData 2

did:dad:Xq5YqaL6L4BpFOuTIURLOJRAU2_RxFROALA3wWYn148= Au example DID with namespuced idstring follows:

did:dad:Xq5YqaL6L4BpEOu7IVALOJRAU2_RxFEOALA3wYn148=blue A DID may have optional parts including a. path, query, or fragment. These use the same syntax as a URL, that i, the path is delimited with slashes, /, the query with a question mark, %, and the fragment with a pound sign,

. When the path part is provided then the query applies to the resource referenced by the path and the

fragument refers to an element in the document referenced by the path. An example follows did:dad:X5Y qaL6LASpRRTIULLOJRAU2_RxFPOALA3wYn148—/mom?who—me /}luc In contrast, when the path part is missing but either the query or fragment part is provided then the query and/or fragment parts have special meaning. A query without a path means tho the query is an operation on cither the DID itsclf or the DID document (DDO). Likewise when a fragment is provided then tho fragment is referencing an clemet of the DDO. An example of a DID without a path but with a query follows:

did:dad:Xq5YqaL6L48p£Ou7IURLOIRAU2_RAFPOALA3wYn148="whomme As will be described later, a query part on a DID expression without & path part will enable the generation of DDIDs {derived DIDs). MINIMAL DAD A minimal DAD (decentralized antonomic data) item is a data item that contains a DID or DDID that helps miquely identify that data item or afiliated data stream. Tn this paper JSON is used to represent serialized DAD itoms but other formats could be used instcad. An example minimal trivial DAD s provided below. Tt is trivial becanse there is no data payload

i

"id": "did:dad:Xq5YqaL6L4BPEO£uTIURLOJRAU2_RxFPOALA3wYn148="

) To ensure datw integity (i that the data has not been tampered with) a signature that is verifiable as being generated by the private key associated with the public key in the id field value is appended to the DAD item. This signature verifies that the DAD item was created by the holder of the associated private key The DAD item s both self-ientifing and selfcertifying because the identifier value given by the id feld is included in the signed data and is verifisble against the private key associated with the public key obtained from the associated DID in the id field. In the example below s a trivial DAD with an appended signature. The signature is separated from the JSON serialization with characters that may ot appear in the JSON.

i 04/26/18 Decentralisod AutonomicData 3

"id": "did:dad:Xq5YqaL6L4BPEO£u7IURLOTRAU2_RAFROALAIWYn148=" } \r\m\r\n 47299aKHgz09£0KEPSkHnyqWvEE_3rpS_22034L998THEMI TIGOPbVULILoupoScE1E_KCASEVRYOFR ZAPnAQ== An example DAD with payload follows: { "id": "did:dad:Xq5YqaL6LABPEO£uTIURLOTRAT2_RAFPOALAIWYn1A8=" , naatar: [ "name": "John Smith', “nation"; =pEA" ] ¥ \zr\n\z\n 47239aKHgz09£0KEpSkHnyqwyEE_3rpS_22034L99sTHEMI TIGQPBVULI L cupoS e 1E_KCBSecVRYOFR zAPaRQ== While the simple DADS given in the examples above are minimally selfidentifying and self-certifying, they do not provide support for other self management properties such as key management. In other words, because each DID (Decentralized Identifer) references a public signing key with its associated private key, it needs to be managed as a ey not just as an identifier, The following sections wil introduce the core key-management properties und the associated meta-data that a DAT) needs in order to support thos propertics. KEY MANAGEMENT ‘The three main key management operations ae: * Reproduction * Rotation * Recovery 01/26/18 Decentralizod AutonomicData. 4

We call these the essential throe R's of key management.

Key Reproduction

Key reproduction is all about managing the creation of new or derived keys. Lach new DID requires a new public/private key pair. The private keys must be kept in a secured location. One reason to create unique public/private ke pairs for each pair-wise relationship is to minimize the risk of exposure to exploits from the repeated use of a given key pair. Another reason to croate unique key pairs for cach inforaction between partis is a3 a means for maintaining privacy through pseudonymity. This is discussed in more detail below. Minimizing the mumber of private keys that, must be secnrely prescrved for a given number of public keys simplifies management and reduces both expense and risk of exposure. To reiterate, there are two key-storage issues, one is storing public Keys and the other is securely storing private keys. An exploit that captures a. store of public keys may mean Toss of privacy beeause the expoiter can now correlate activity associated with those public keys. An exploit that, eaptures a store of private keys means that, the exploiter many now be able to use those private keys to take control of any associated resonrces. Consequently, one wants to avoid storing private keys as much as possible Privacy and Confidentiolity

One desirable feature of a DAD is that it be privcy preserving, A simplified definition of privacy is that if two parties are participating in an exchiange of data in s given context. then the parties should not be Tinked to other interactions with other parties in other contexts. A simplified definition of confidentiality is that the content of the data exchanged is not disclosed to a third party. Confidentiality is usually obtained by encrypting the data. This paper does not specifically cover encryption but in general the mechanisms for munaging encryption keys are very similar to those for managing signing keys.

An exchange can be private but not confidential, confidential but not private, both, or neither. A minimally sufficent means for preserving privacy s 1o use a DID as a pseudonymons identifier of each party to the exchange, A pseudongnm is a manufactured alias (e.g. identifir) that is under the control of its ereator and that. is used to identify u given interaction but is not linkable to other interactions by its owner, The ability of a third party to correlute an entity's beluvior across contexts is reduced when the entity uses a unique

DID for each context, Although there are more sophisticated methods for preserving privcy such as zero-knowledge proofs, the gosl here is to use methods that are compatible with the performance demands of streaming data.

As mentioned above, the problom with usin unique pserdonymsjerypionyms for cach exchange is that a large ‘mumber of sueh identificrs may need to be maintained. Fortunately hierachically dorived keychains provide a way to manage these cryponyms with u reasonsble level of effort.

Hicrachical Deterministic Key Generation

A3 previously mentioned, reproduction has (o do with the generation of new keys. One way lo accomplish this is with a deterministic procedure for generating new public/private keys pairs where the private keys may be reproduced securely from some public information without having to be stored. A hierarchically deterministic (HD) key-generation algorithm does this by using a master or root private key and then generating new key pairs using a deterministic key-derivation algorithm. A derived key is expressed as a branch in u tree of parent,/child Keye. lach public key includes the path o its location in the tree. The private ke for a given public key in the rce can be seenrly regenerated nsing the root. private key and the key path, also called a chain code. Only one 04/26/18 Decentralisod AutonomicData 5

private key, the root, necds to be stored. The BIP-32 specification, for example, uses an indexed path representation for its HD chain code, such as, “0/1/2/07. The BIP-32 algorithm needs a master or root key pair and a chain code for each derived key. Then only the master key pair needs o be saved and only the master private key needs to be kept securely secret. The other private keys can be reproduced on the fiy given the key generation algorithm and the chain code. An extended public key wonild include the chain corde in its representation so that the associated private key can be derived by the holder of the master private key any time tho cxtended public key is presented. This is the procedure for hardened keys. The query part of the DID syntux may be used to represent an 1D chain code or HD key path for an HD key that is derived from a root DID. This provides an economical way to specify derived DIDs (DDIDs) that are used to identify DADS. An example follows:

did:dad:Xq5YqaL6L48pEOfuTIURLORAU2_RAFROALA3wYn148="chain=0\1\2 This expression above discloses the root public DID as well as the key derivation path or chain via the query par. For the sake of brevity this will be call an extended DID. The actual derived DDID is create by applying the HD algorithm such as:

did:dad:Qt27£ThHONZSa88V Tkep6H- 4HABEES4SHONL VW 6FE= Thus a database of DDIDs could be indexed by DDID expressions with cach value being the extended DID. Looking up the extendod DID allows the holder to reereate on the fiy the associated privaic key for the DDID withont; ever having to store the private key. This might look like the following:

i

"did:dad:Qt27£ThHONZsaB8VETkep6H-4HABEr54SHONI VW GFE=" :

"did: dad:Xq5YqaL6L4BpEO£uT IURLOJRAU2_RXFPOALA3wYn148=2chain=0\1\2" ,

) Or given that the sume DID method is used throughout:

t

"Qt27£ThHONZsa88VCTkep6H-4HAS tr54SHONL VWL 6FE=" :

"Xq5¥qaL6L48pEOfuTIURLOTRAUZ_RXFPOALA IwYnl48=2chain=0\1\2"

) 01/26/18 Decentralisod AutonomicData 6

The namespacing of the DID idstring also provides information that could be nsed to help formulate an HD path to generate a DDID. The following example shows two different DDIDs using the same public key and the same ehain code but with a different extended idsiring, did:dad:Xq5YqaL6L4BpEOLuTIURLOIRAU2_RXFROALA3wYn148= blue?chain=0/1 did:dad:Xq5YqaL6L4BpFOLuTIURLOJRAU2_RxFROALA3wYn148=: red2chain=0/1 Some refinements to this approach may be useful. One is the grenularity of DDID allocation. & unique DDID could be used for each unique DAD or & urique DDID could be used for each unique destination party that is receiving a data stream. In this case each DAD would need an additional identifir to disambiguate each DAD sent to the same party. This can be provided with an additional field or by using the DID path part to provide sequence number, This is shown in the following example: did:dad:QE27£ThHoNZ 288V Tkep6H- 4HABEE5 4SHONL V1 6FE=/10057 The associated DAD is as follows € "id": "did:dad:Qt27£ThWONZSa88VETkep6H- 4RABLE54SHONLVRL6FE=/10057" , naatan: i temp": 50, “time": "12:15:35" ) ) \r\n\r\n u7239aKHgz09 £0KEpSkMnyquyE:_3rpS_z2034L99sTHEMI TIGQPEVUT T cupoeeTE_KCBSecVRYOFR zAPnAQ== Change Detection Stale DAD items must ofien be detectable to provent replay attacks. A later re-transmission of an old copy of the DAD itom must not: supereode a newer copy. Using a sequence number or some other identifier could provide change detection. Another way to provide chauge detection is for the DAD item 1o include & changed field whose value is monotonically increasing and changes every time the data is changed. The souce of the data can enforce that the changed field value is monotonically increasing. Typical approaches include a monotonically increasing date-time stamp or sequence mumber. Any older data. items resent. or replayed would have older date-time stamps 04/26/18 Decentralized AutonomicData 7

or lower soquence numbers and would thus be dotectable as stale Below s an example of an non-trivial data item that has a changed field for chnge detection. i "id": "did:dad:Qt27£ThWoNZSa88VETkep6H- 4HABLE54SHONLVWL6FE=/10057" , "changed" : "2000-01-01T00:00:00400:00" “data”: « “temp": 50, “time: "12:15:35" 3 ) \r\n\r\n u7239aKHgz99£0REpSkMnyqwvEx_3rpS_z2034L99sTHMI IIGRPEVULJ1cupo6 cE1f_KCBSecVRYOFR ZAPRAG== Change detection prevents replay attacks in the following mauner. A second party reccives DAD updates that are each signed by the associated private key. Bach update has a monitonically increasing changed field. The source signer controls the contents of the data wrapped by the signature, Therefore the signer controls any changed feld, A consistent signer will use & monotonically increasing changed value whenever the data wrapped by the signature is changed. Thus a malicious third party cannot replay earlier instances of the DAD wrapped by a valid signature to the orginal second party because the second party knows to discard any receptions that have older changed felds than the latest one they have already received. On the Fiy DDIDS in DADs One important use case for DDIDs in DADs is to identify data that is received from a source that is not providing identifying information with the data. The receiver then creates an associated DID and DDIDs fo identify the data. At some later point the receiver may be able to link this data with some other identifying information or the soureo may “claim” this data by supplying identifying information. Tn this case the DDIDs are privaie to the receiver but. can later bo used to credibly provenance the internal s of the data. This may be extremely beneficial when shared amongst the entitios in the processing chain as a way to manage the entailed proliferation of keys that may all bo claimed later as a hicrarchial group. The DIDs and associated derivation operations for DDIDS may be shared amongst & group of more-or-less trusted entities that are involved in the processing chain. 04/26/18 Decentralisod AutonomicData 8

Public Derivation

Another important used case for DDIDS in DADS is to avoid storing even the DDID with its derivation chain This may be an issue when a client. wishes o conmunicate with & potenially very large number of public services. Each public service would be & new pairing with a unique DDID. If the derivation algorithm for an HD-Key DDID could use the public key o public DID of the public service to generate the DDID then the client need not store the actual DDID but can secover the DDID by using the public DID of the server to re-derive the associated DDID. ‘This can be done by creating & hush of the root DID private key and the remote server public DID to create the seed nsed to generate the DDID for the DAD. This also means that the DDIDs or chain codes do ot have to be included in the keys preserved by a key-recovery systern.

Key Rotation

“The simplest approach 1o key rotation is 0 revoke and replace the ey in one operation, Iu some cases revocation without replacenent is warranted. But this is the same es revoking and then replacing with & null key. Key rotation without revocation usually poses a security risk 50 it is not needed. Hence we simplify key management 1o include revocation as a subset. of rotation.

Koy rotation is necessary becanse keys used for sigaing (andor encryption) may suffer increased risk of becoming compromised die to contined use over time, may be vulnerable to brite force attack merly due to advances in computing technology over time, or may become compromised due to misuse or a specific exploit. Periodically rotating the key bounds the risk of compromise resulting from exposure over time. The more difficult problem to solve is secure roation aficr a specific exploit may have already oceurrod. Tn this cas, the roceiving party may seciexe a valid signed rotation operation from the exploiter prior to the orignal halding entity sonding a valid xotation operution. The receiver may erroneously accept o rolation operation that transfers control of the data to the exploiler. A subsequent rotation operstion from the original holder would ither create a conflit or & race condition for the receiver.

Althongh there are several ways to solve the early Totation exploit problem described above, the goal is to find the ‘minimally sufficiont moans for preventing that exploit that is compatible with the domands of streaming data applications for which DADs are well suited.

Basic Prerotation

A complication with DADs is that thero a

re two types of keys being nsed: th koys for the root DIDs and the keys for the derived DIDS (DDIDS). Generating a derived key paie requires wsing the privae root key. The process for pre-rotating the raot, DID is described fist, followed by tho additional measures for DDID pr-rofation.

“The upproach presented hexe s to pre-rotate the DID key and declare the pre-rofation at the inception of the DID. This pre-rotation is declared at initalization. This may be done with &n inception event. A later rotation Operation event creates the next pre-rotated key thus propogating a new set of current key und pre-rotated key. Shown below is an example inception-event, data structuro with a signing key in the signer ficd and a pre-rotated next signing key in the ensur fld. The signature is gencrated using the signer key

Example inception event:

0426718 Decentralized AutonomicData o

€ “id": "did:dad:Qt27£ThWONZsa88VLTkep6H-4HABLr54SHONLVALEFE=", “changed" : "2000-01-01T00:00:00+00:00", “signer": "Qt27fThWONEZsa88VxrTkep6H-4HAStrSASHONIVWLEFE=", "ensuer": "Xq5YqaL6LABpEOfu7IURLOJRAU2_RxFPOALA3wYnl48=" ) \r\a\r\n u7239aKHgz 99 £0KBpSkMnyqwvEx_3rpS_z2034L99sTHIMI IJGQPbVUI ] cupoGc1£_KCBSecVRYOFR ZAPAAQ== A useful convention would be that if a signer field is not provided then the signer is given by the id field. i “id": "did:dad:Qt27£ThWONZSaB8VETkep6H- AHABLI54SHONLVWLEFES", “changed" : "2000-01-01T00:00:00+00:00", “ensuer": "Xq5YqaL6Ld8pfOfu7IURLOJRaU2_RxFPOALA3wynlds=" ) \r\n\r\n u7239aKHgz 99 £0KBpSkMnyqwvEE_3rpS_22034LI9STHEMI T IGQPHVUTI1CUpOSCETE_KCRSECVRYOFR 2APAAQ== When rotation occnrs sometime later, the rotation operation atomically indicates that the key in the signer field is 0 be replaced with the pre-declared rotation key in the ensuer field and also declares the next rotation key to be placed in the ensucr fiold. One way o keep track of this is to provide three keys in the rotation event, the former signer in & new erster field, the former ensuer in the signer field and a new pre-rotated key in the ensuer field. The rotation operation has wwo signatures. The first signature is created with the former signer key (now erster field). The second signature with the former ensuer key (now signer field). This establishes provenanc of the rotation aperatian. Example rotation event: € "id": "did:dad:Qt27£ThWONZSa88VrTkep6H-4HAB Lr54sHONLYWLEFE=", 0472618 Decentralizod AutonomicData, 0

"changed" : "2000-01-01T00:00:00400:00" "erstez": "Qt27fThWoNZsa8BV:Tkep6H-4RABLrSASHONLVWIEFE=", "signer": "XqSYqaL6LABPEOfu7IULOJRaU2_RxFPOALA3WYn148=", “ensuez": "dZ74MLEXD-1QHoa7IW9pQIGEOAVXGFi2RIZHIKCOZaY=" ) \r\a\r\n 3632 XMASGuyPGRFES Xr GVOBMKD £d0J34UKZYTT YOMohoMY 1. REAGHS 028 PSHY UB- U1wfWaTlibIPURZVRTGI DA—= \r\a\r\n e£TU43p1MEZz I gaHCE5qL S Tpmmay 6QOF VAP nHn 6 TUKQE? 1 £172PebYFVmCEK cd0wWeHQONaTO~ ajwoxJezna—= Instead of three fields in the structure a list or tuple of three fields could be used where the order corresponds to [erster, signer, ensuer] In order o verify provenance over multiple rotation operations, the receiver needs to be able to replay the history of rotation operations. The pre-rotation approach has some nsoful foatures. For many exploits, the likelihood of exploit is a fimction of exposure to continued monitoring or probing. Narrowly resticting the opportunity for exploits in terms of time, place, and method, especially if the time and place is a one-timo cvent, makes exploits extremely diffionlt. The exploiter las 10 either predict the time and place of the event or has Lo have continuous niversal monitoring of all events. By declaring the pre-rotation at the inception event, of the associated DAD, the window for exploits is as narrow as possible. Pre-rotation does not require any additional keys or special purpose eys for rotation. This ‘makes the approach self-contained. Because the rotation-operation event requires Lwo signaiures, one using the current key und the other using the pre-rotated key, an exploiter would have to exploit both keys. This is extremely difficult because the only times the private side of the pre-rotated key is used are (1) at its creation in oxder to make the uscociated public key, and (2) at the later signing of the rotation operation event. This ‘minimizes the times and places to a narrow sample Bisted Rotation Key Structure Another approach to declaring rotation events is to provide the full rotation history in the rofation operation and/or to use a list structure for providing the keys. In many cases, rotations are a rare event, so the mumber of enrics in the rotation history wonld be small. Tn the assoriated data structure a list of all the signers both former and future fo date is provided in the signers field. The current signer is indicated by an index into the list in the signer field. The list index is 7ero based. The pre-rotated next signee or ensuer is the following entry in the

signers list. A rotation event then changes the signer field index, which implies that the former signer (crster) is the 04/26/18 Decentralisod AutonomicData n

previous ontry and the next pre-totated signer (ensuer) is the subsoquent cntry after the signer index. This is shown in the following examples Ixumple pre-rotated inception event with list structure for signing keys [ "4d": "did:dad:Qt2TETRHONZsaB8VETkep6H- AHAB S ASHONIVH] GFE=" , “changed” : "2000-01-01700:00:00+00:00", "signes": 0, "signers": t QE2T£THHONZ s aBBVTkep6H- 4HABEX54SHONI VWL 6FE=" , "Xq5¥qaL6L48p£O£uTIVRL0TRAU2_RAFROALA3WYALAB=" , 1 ) \r\n\r\n 33 ZXMAS GuyPGHFES xrGVOBMKD £0 73 UKZy TT YUMohoMYi rREAGHS028 PSHYUB- UlwEHaJlibIPUNZVPTGIDA= “The signature above is with ey at index = signez = 0. Example rotation cvent, with lst structure for signing keys: « "5d": "did:dad:Qt27ETRHONZsa88V: Tkep6H- ARAB tr54SHONLVRGFE=" , "changed" : "2000-01-01700:00:00+00:00", "signer": 1, "signers": r "Qt27£ThWONZS 288V Thep6H-ARAS S 4SHONLVWLEFE=" , 0426718 Decentralized AutonomicData 12

"XqSYqaL6LABpEO£uTIVRLORAU2_RAFROALAIWYA148=" , "4274MLZXD~ 100 IHIPQIGEOAVXGF§ ZRTZHLKCOZaY=" 1 ) \r\n\r\n 3C3ZX0AS GuyPGRFEsx£GVOBNKD td0J3 4UKZy TTYTohoMY 4 rREAGHS 028 PSHYUB~ UlwiHaJlibIPUNZVPTGIDA= \r\n\r\n @£1U43p1MEZ2jgacE5gL) Jpmmay 6QOFVAPMHULnENG 1UKQZ2 ] £17ZPebYFVICEKcdOWeRQONATO~ a3wgxJe20h= Tho frst signature is with key al index = signer - 1 = 0. The second signature i with key of index = signer = 1 A subsoquent rotation wonld add another key to the signers list and increment, the signer index as follows « "id": "did:dad:QE2TETRHONZsaB8V=Tkep6H- AHAB 5 4SHONLVRLGFE=" , "changed" : "2000-01-01700:00:00400:00", "signer": 2, "signers": r Q27 £THHONZsaB8V L Tkep G- 4HABE 5 4SHONL VL 6FE=" , "Xg5YqaL6LABPEO£uTIVRLOIRAUZ_RAFROALAIWYN148=" , "d274MLIXD~10HoaT n9PQIGTOAYRGFE ZRTZHLKCOaY=" , *38yVH2WOCPOVPE0SDZ0by_OxNe22gxK;TQ961LIMAAS" 1 ) \r\n\r\n 01/26/18 Decentralizod AutonomicData 13

ReYbsHotOpndWACgToS DB AuSQAENH5UGwi IGPVNIQQOYKBY rPPxAoT c11 SSHCIDSEKEFG£E1 0EDGEX Gizacg== \r\n\r\n 09y JuKHHNJZF 4 0QDIK6VptEEROXgXL382_4D- 783CCYmuOWARENVEYaf_Gifw_25CrHBARZRAEST] 3 thLmus 0Dw== Multicsignature Pre-rotation. The list structure enables the declaration of sevral pro-rotations in advance by providing several future pre- rotation keys in the inception event. A rotation event then could inchude several rotations at once. Each rotation event. would requirc a signature per cach of the multiple rotations in the event thus allowing for multi-signature inception and rotations. If cach key is from a different entity, then the rotation would require multiple enfitics to agree. Thus a DAD could be multi-signature and support multi-signature rotations. In this case the signer field would be a list of indices into the signers list. This approach could be further extended 1o support an M-of-N. signature scheme whero any M-of-N signatures are required (o incept or rotate where M < N, and M, N are integers. The total number of keys in the list is a multiple of N. The following examples provide an inception and rotation event for a two signature pre-rotation. A namespaced key with a colon-separated idstring, us per the DID syntac, could be used o allow for signers using a different DID method or for namespacing within » given DID method. Example of a pre-rotated two-signature inception event with list structure for signing keys whero “bluc” indicates one source and “red” indicates another source: i "3d": "did:dad:Qt27£ThWONZSa88VrTkep6H- 4HASLrS4SHONLYWLEFE=", “changed" : "2000-01-01T00:00:00+00:00", “signer™: [0,1], "signers": i "QE27EThHONZSa88VrTkep6H-4BABLr54SHONLVNLGFE=blua" "Xq5YqaL6L48p£0£uTIURLOIRAU2_RxFPOALA3IWYn148=:red" , "d274MLZXD-1QHoa73W9pROGEOAVXGF 1 2RTZHIKCOZaY= blue" "38yVH2woCPOVRFOSDIZ0bu_OxNe2ZgxK3TQO61L1MnA= : red" 1 0472618 Decentralized AutonomicData. 1"

3 \r\n\r\n AeYbsHotOpnARACGTo55D81AuSQAENHSU Gwi [GPVNIQQOYKBY PPXxRoTC14 SSHCIDSBKEFGE 10D GizaCg== \r\n\r\n 09y JuKRNIZF4.0QDIKEVPLE£POXgKL}8z_4D- 783CCYmuOWAR 6NVt Yaf_GHw_25CzHBAAZBAESmL 3 thimus0Dw== The signatures above are generated with the keys at indices 0 and 1 in the signers list respectively Exammple of & two-signature rotation event with list structure for signing keys where “blu¢’ indicates one source and “red? indicates another source: € "id": "did:dad:Qt27£ThHoNZSa88V L Tkep6H- 4HAB LTS 4SHONLVRL6FE=", "changed" : "2000-01-01T00:00:00400:00" “signez": [2,3], “signers": t “QL27£THHONZSa88VETkep6H-4HAS tr54SHONL VI 6FE=blue" , "Xq5YqaL6L4BpEO£u7IURLOJRAU2_RxFPOALA3wYn148=: red" , "4ZTAMLEXD-10Ho0a73WIpQIGLOAVXAFA ZRTZHIKCOzaY=blue" , "3syVH2woCPOVFOSDIZ0bu_OxNe2ZgxK TQ961L1MnA= : red" “ZTkep6H-4HABLz54SHONL VWL 6FEQL2T £ThWONZ5a88V=blue" , "71URLOJRAU2_RxFPOALA3wYn148Xq5YqaL6LABpEOFu=:red" , 1 ) \r\a\r\n ‘AeYbsHotOpmARACGTo58D8 1 AUSOAERH5U 6w IGPVNIQQOYKBY rPPxRoTC] 4 5SHCIDSBKFFGE a1 0EDEXG 04/26/18 Decentralized AutonomicData 15

izacg=

\r\n\r\n

09y 5UKHHNIZF 00DIK6VPEE £ROXgK1 382_4D~

783CCYmuOWAR 6NV tYaf_GHw_25CzHBAAZBAEST] 3 thimus0Dw==

\r\n\r\n

GPVNIQQOYKBYrPPxAoIC1 i SSHCIDSSKFFG£810tDq8XGi zaCqheYbsHotOpmdWACGToS sD8 1 AuSQALRHS

Ubwit=

\r\a\r\n

8z_ap-

783CCYmuOWAR6NVtYaf_GHw_25CrHBAAZAEsm] 3 thimus0Dwody JukHENIZFS 0QDIKEVPEEE0XgRL] The signatures above are generated with the keys at indices 0 through 3 in the signers list respectively. Coltetive Signatures This multi-signature scheme sulfers from the siguificant inerease in the length of the attached signature block. One way to ameliorate this “bloat” is to use collective multi-signatures, A colleetive signature has the property that its Tength is not a multiple of the number of signatures it holds. Typically the maximum length of a collective signature is about double the length of a non-collective signature and does not increase significantly as more signatures are added to the collective, There is a draft IETF standard for collective signatures CoSi that might be useful for multi-signature rotation., Some useful references are here project, peper, slides. Collective signatures are a type of Schnorr multi-signature or Schnorr threshold signature DDID Precotation The complication for DDIDs (Derived DIDs) is that cach DAD stream for cach pairing of sender and recciver may have a unique DDID. Rotation of the oot DID also requires rofating the DDIDs. The same pre-rotation approach, however, can be used for the DDIDs. At the inception event the root key and pre-rofation root keys are ercated. These keys are then used o ereated a sot of DDIDS and pre-rotated derived keys using the root and pre- rotated root. keys respectively. This does not. significantly change the exploit vulnerability as the incoption event is still one ovent. Althongh the pro-rotated root DID key is used fo eroate a set of pre-rotated derived keys, it doos not signicantly inerease its exposure. Each rotation event then involves rotating the root DID key and all the DDID keys. The important. consideration s that the number of DDIDs in the sel. must be determined in advance in order 1o create all the pre-rotated derived keys at one time. This can be managed by ereating extra DDIDs and pre-rotated derived keys at the inception event. Only the public hall of each of the key pairs need to be stored. In contrast, creating additional DDIDs with pre-rotated keys at a later time requires using the pro-rotated root private key. This inereases the exposure of

that private key to cxploits and makes it loss secure for pro-rofation When the set of pro-rotated DDIDs is consnmed, a rotation-operation cvent may be triggered, thereby rofating the existing DDIDs and then allowing additional DDIDs 1o be created. 04/26/18 Decentralisod AutonomicData 16

Alternatively if the pre-rotated set of DDIDs is consnmed then a nese DDID tree may be created with a nique new pre-rotated root key. This would create a hicrachy of groups of pre-rotated DDIDs and derived keys. Moreover, when the re-establishment and re-initialization of a DAD stream is not a high-cost or high-risk endeavor then instead of pre-rotating the DDIDs, ouly pre-rotate the root DID and just elose down the current DAD stream and re-establish with new DDID created by the pre-rotated key as part of the rotation even. Finally if the exposure of the oot DID is insignificant compared the exposure of the DDIDs then another approach to DDID pre-rotation eold bo employed. This requires a trade-off betsvoen convenicnce and privacy. A &ronp of receivers conld all have knowledge of the root publie DID key and its pre-rotated public DID key for their unique DDIDs. This means that the members of the group could leak correlation information about the group via the shared root DID. Howover each member of the group could still maintain seeurily via its uniquo DDID. Tn this case the root private DID is used to derive both the inception DDID and the pre-rotated derived Key of each member. The individual members could then undergo DDID key rotation bt only using the root, DID not its pre-rotated key. In the rare event that the oot DID needs to be rotated then each of the DDID members performs a double rotation witkin a rotation event. The first rotation rotates to the pre-rotated key generated using the original root, DID, the second rotation is to a new set of derived and pre-rotated derived keys, each generated using the new pre-rotated root key. The first derived ey in the pair is the new signer key, the second is the mew prerotated signer key. A receiver must have knowledge of the root DID and pre-rotated root key in order to verify that the second rotation is not a forgery. This approach enables the organization and managment of DDIDs in heirarchical groups where the members of cach group kuow about their group-root DID but that group- 100t DID could be a DDID of a higher level group and 50 on. Lower level groups only know about thier group zoot DID, but mot any sibling groups so it can't leak information about sibling or parent groups only child gronps. Replagabitity

The constraint on prerotation s that the receiving party be able to replay the rotation events to ensure that it did ot miss a rotation. This replay allows the receiver to verify the provenance

chain of rotations. The question then is what are minimally sufficient, means for enabling this replay capability?

There are two use cases for providing this replay capability. The first case is for online one-Lo-one or pairwise interactions and the other case is for offline one-Lo-one or equivalently one-to-many or public interactions.

In the one-to-one case, there is the sender of & DAD stream and the reciever of the stream. The initiation of the stream wonld involve exchanging keys for pairwise communication and would also incinde the establishment of the DDID used for the DAD items sent, The first DAD sent would include the DDID for the DAD as will as the pre-rotated DDID. This is the inception event. The rocciver then merely noeds to maintain a rnning log of DAD itoms that contain rotation cvents. As long as reliable communications are used botween the sender and recciver, then the receiver can ensure that it has obscrved all rofation cvents by keeping its log and no imposter can later send an undetectable forged inception or rotation event. If the reciever loses its history then it must re-cstablish its communications channel and re-initialize. Alternatively the sender could maintain a copy of the inception and rotation event. history and then provide it to the receiver upon request. The receiver would cache this history for specdier lookup. An imposter attempting to send an carler forged incoption event would be nsuceossful becaise only the first inception event is considered valid

04/26/18 Decentralized AutonomicData "

In the ane-to-many, public, or offine case, the rotation history i maintained by a service. While a dccontralized distribited consensus blockehain ledger conld provide this service it is not the minimally snffciont moans of providing this capabilit. The minimally suficient means is a redundant imutable event log of nception and rotation events indexed by the DDID associated with the DAD for the given DAD stream. The constraint is that, a sulicient. majority of the log hosts must be non-fauly at any point in time. This includos Byzantine fanls. Is is also assumed that. the sender communicates with the hosts using a reliable end-to-end signed protocol. The sender broadeasts the inception event to all the redundant hosts that provide copies of the log, These hosts are called Replicants. Then either the Replicants respond to the sender with s confirmation that the event is written to their o or the sender reads the log to verify. The eveut history is indexed by the DDID, Buch Replicant timestumps aud signs each entry in each event history. Each Replicant ouly llows one and ouly one inception event per event, history. Attempts by imposters to forge an carlier inception event would be denicd by hongst Replicants. The sender can then verify that a suficient majority of the Replicants have captured each event and have consistent event histories, Subsequent rotation events are redundantly appended to the DDID indexed log in the same way. The receiver can then broadcast query to the Replicants and verity via their responses that & suffcient majority of the Replicants have the same DDID indexed event og. This canbles both offine and one-to-many event streams.

“This approach is more scalable than using » distributed consensus ledger becauso the Replicants do ot need to communicate with each other. The inter-host agreement of the members of a distributed consensus pool is nsually the limiting factor in scalablity. Morever a given receiver could be completely responsible for providing the immitable log service for its own data stream with the sender. Each receiver conld choose to implement o iffeent; lovel of reliability. Loss of the event log means that the sender and receiver have to re-initialize und re- establish the DAD stream. Alternatively the sender conld be responsible for providing a sat of Replicants and male the ovent log available to the recciver upon reqest.

Key Recovery

Key recovery is about providing a secure way of recovering a lost private key. The

important consideration here is that the recovery mechanism be compatible with stzesmming data applications us per DADs. Keys recovery tends to be & rare occurrence so performance demands muay be less constraining, Nonetheloss, finding the minimally sufficient means for key rocavery s still the goal. Moreover, to be secnre the private key needs to be kept sccrct, Because cryptographic keys are long strings of numbers they are extremely hard to remember, this means that typically private keys are stored some place besides a person’s memory and are therefore subject to being lost or stolen.

I i i required or at leust desirable that the DAD stream not be reinitialized due 10 the los of the rotation-event history then key-recovery mechanisin would also need (0 provide recovery of the key-rotation history. T'o restate, it s not enongh to just recover the original zoot DID but every rotated root DID must be recovered as well. Given that eypically rotations happen rarely, the rotation-event history should be small in size and not pose a storagesize problem for recovery. Thus key recovery for DADs needs to at least recover the original root key and any rotations.

DDIDS can be regenerated from the xoot DID given the HD-derivation code. In the case where the the DDID stream may ol be easily reestablished but must resume given the latest rotated DDID then the HD chain code st also be preservd and recovered. If e nunber of DDIDs is very large then the storage requirements for 042618 Decentralizod AutonomicData 18

chain codes may also be large relative to the storage requirament for key recovery. The DID root prblic key and DDID derivation chain codes do not expose the privae keys. However, althongh disclosing the root public key and chain code for a DDID is not a security risk, it could be a privacy risk. A third parly could correlate data streams from the associated DDIDs should the root. public key used by multiple DDIDS be exposed. One way to address this is to encrypi.the chain codes with an encryption key derived from the root signing key. The chain codes can then be stored outside of the core recovery system. The worst case exploit then is a loss of privacy should the encryption be broken but not a loss of control of the resources owned by the private key

When the DDID for communicating with a public service is derived from the public key of a server then the client does not need to preserve and recover the HD chain code. Instead it can regencrate the DDID using a hash of the root. private DID and the public DID of the server. A complication oceurs when the rao, private key has been rotated and the sorver was not. made aware of the rotation. The elient can still recover the eurrent root, DID used by the server using a trial and error approach by going through the list of rotated root, DIDs, generating the associated DDID or derived key, verifying if the server will aceopt it, and if not incromenting to the next rotatod root. Eventually the elient vill discover the last rotated DDID or derived ey recoguized by the serve. As a result the client can recover the appropriate DDID or derived key for a given service without having to preserve auything but the history of rotated root DIDs. This approach may provide meaniugful storage savings when the ‘number of external services is large.

Crptagraphic Strengih

Injormation Thearetic Security and Perfect Security

With respoct to DAD, key recovery deals with the recovery of the private half of signing and for encryption keys in public/privato key pairs. Given that once an adversary has the private key, seourity is complotely broken, the eryplosystems used to backup and recover private keys nowds to he as secure as is practically possible. The highest level of crypto-graphic secruity s called information-theorelic security. A eryptosysten that hus this level of security canniol be broken algorithimiclly even if the adversary has nearly unlimited computing power including quantum computing, T4 must be broken by brute

force if at all. Brute force means that in order Lo guaranice success the adversary must search every combination of key or seed. A special case of information-theoretie security is called perfect sccuricy. Perfect security means that the cipher text provides no information about the Key. There are two well-known cryptosystems that can exhibit perfect sercurity. One is sccret sharing or splitting (see also s). The other s a one-time pad (see also oto). Correct implementation of either for a combination of these two upproaches is appropriate for private-key recovery.

Sufficient Cryptographic Strength fo Withatand o Drute-force Atiack

For cryptosystems with perfect security, the fundamental parameter is the mumber of bits of entropy needed to resist amy practical brute force attack. In other words, when a large random number is wsed as a seed /key to @ eryplosystem that has perfect. security, the question o be answered is how large does the random number need to be to withsiand a brute force attack? Tn Shannon information theory the entropy of a messago is measured in bits. The randomness of a mumber or message can measured by the mumbor of bits of entropy in the mumber. A cryplographic quality random wumber will have s many bits of entropy as the number of bits in the number. Assuming conventional non-quantum computers, the convention wisdom is that, for systems with information theoretic or perfect security, the seed fkey needs Lo have on the order of 128 bits (16 bytes) to practically withstand any brute force attack. For other cryptosystems that do not have perfect security the size of the 04/26/18 Decentralisod AutonomicData 19

secd ey may need to be much larger.

Theoretically, quantum computers, using Grover's Algoritiim might be able to brute force a 2" random number with only 2°* trials. Thus once quantum computers exists the size of N might need to increase from 128 to 236, An Nobit long base-2 random number has 2¥ difforent possible values. Given that. with perfoot security no other information s available to an attacker, the attacker may neod to try every possible value before finding the correct one. Thus the number of attempts tha, the attacker would have 10 test may be as much as 2" . Given available computing power, one can estimate if 128 is s large enought N to make brute force attack impractical. Let's suppose that the adversary has access to supercomputers, Current supercomputers can perform on the order of one quadrillion operations per second. Individual CPU cores can only perform about 4 billion operatons per second but a supercomputer will employ many corcs in parallel. A quadrillion is approximately 27 = 1,125,800,006,842,624. Suppose somchow an adversary had a million (2% = 1,048 576) super computers to employ in parallel. The adversary could then try 2* * 2 = 2 values per second (assuming that each try only took one operation). There are about 3600 * 21 * 365 — 313,336,000 — 275550 _g0 = 92 soconds in a year, Thus this set of a million super computers could try 2% _ 9% values per year. For a 128-bit random number this means that the adversary would need on the order of 2% % — 2% — 589,934,592 years to find the right value. This assumes that the value of breaking the cryplosystem is worth the expense of that nuuch computing power Consequently, a eryptosystem with perfect security and 128 bits of cryptographic strength is practically impossible to breals,

Recovery Methods

Fundamentally key recovery involves shifting the burden of remembering a cryptographic key made of long random string of mumbers to some other fask that is less onerous.

Physicat Security

One approach to recovery is to shift the burden of recovery from remembering a private key o keys to protocting Physical copics of the keys. This s callod physical socnrity. Recovery first involves creating a hard copy of the Key(s) sich as a printed picce of paper or a.“hard” clectronic wallet and then hiding the hard copy. The memory task now becomes remembering where the hard copy was hidden. The sccurity of the approach is now based on the physical security of the hidden location (under the bed, in

the safety deposit box, in a hole in the hackyard). The assumption is that remembering where something is hidden is sssumed to be relatively reliable. Most importan. is that physical security is not vulncrable to remote attacks over the intornet nor computational attacks where the attacker can employ resources and time o break u ey, The attacker must have physical access and may be physically st risk. A weakness of this approach is that recovery may lake time. Moreover if the person with the knowlede of the key location is ineapacitated then recovery may be impossible unless the location of hard copy or another hard copy s shared with someonc else, thus exposing a vulnerability. One way to address this is to se & legal mechanism such as power of attorney, a will, or another guardian who is authorized to reveal the hurd copy given predefined circumstances. This can be ameliorated by using tamper-resistent envelopes and physical aceess logs to increase the risk of discovery. In any event physical recovery is useful as a backup to non- physical security recovery methods but may be too incouvenient as the primary form of recovery for the mansgers 04/26/18 Decentralized AutonomicData 20

of streaming data. applications. Tn general physical sccurity may bo a good backup for any of the other recovery. methods.

Mnemonics

A mnemonic is & device or technique o aid human memory. The memory task in this ease is (0 remember a 128- bit random number s o key or seed. This is rther complicated for DAD recovery as it is not sufficient to just secover a single private key but instead requires the recovery of the whole key rotation history. One way to accomplish this is Lo use 125-bit randoms mumber as a seed to & system that hides and zecovers the whole rotation bistory. This will be discussed in more detail below. One well- known muemonic is to use u phrase of random words from a word list. The user can create a story or imaginery visualation of a situation in which the words are all represented. An example would be the words, blue cat house cat pudding. Visualizing and rehcarsing a fantastic situation that includes objects and actions corresponding to the words makes is much casier to remember.

"The DiceWazc(see also 1k und o) approacls consists of a word lish of 7776 words that are selected ut random (using dice). The user must. remenuber the words and their order Lo form a phrase that can be used 10 generate random nurnber, The EFF has produced modified versions of the word list (EFT word Jist) that have beneficial propertics. Given a total of 7776 words, then each randomly selected word i one of 7776 choices, which provides log,(7776) = 12.9 bits of entropy per word. To get & 125 bits of entroy the phrase would need to include ten words. This is pretty long for a mnemonic bt not impractical as long as the user i willing to do some rehearsal More problematic i recovering not just one key but multiple keys from a key rotation history.

Secret shoring

Another approach is to shit the task of recavery to other partics. This oan be done securely using a secrel sharing or “splitting” approach. The secrct information s split into what are sometimes called shards. Each shard is then shared with another party called shard holder. Luter the shards are collected and combined to reproduce the secret. The shard holders must either keep the shard secret or if they are going Lo store it online they need to enciypt the shard and must then remember their encryption key. As mentioned above, secret shaing may have perfect security. This means that storing encrypted copies of the shards online may sill be perfectly seeure as long as an adversay cannot correlate

the shards as belonging to the same secret information. If correlation does oceur then the security is mited to the type of encryption and might be more vulnerable to exploits

In order to recover the secret information tho nser must interact with the shard holders to got them to provide their shard; that i, the recovery i imuli-party interactive. The user then conibines the shards o reconstitute the sharad secrct. This interaction may take time and may not be reliable. A useful variation on this approac is called threshold o Shanie sharing where only a subset of al the shards is needed 1o reconsiitute the secre. For cxample an M of N threshold secret sharing (M < N) algorithm would share shards with N partics. Any combination of a subset of M parties can reconstitute the secret, This allows some of the parties to ot be available or to lose their shard aud stll have sucessful recovery. Typically, to maintain secreey the N paties do not know of esch other.

Although the security properties of Secret, sharing make it an atiractive approach for key recovery, seerct, sharing can e complicated, especially bocause it requircs interaetion with multiple parties. The scerot owner must recall 042618 Decentralizod AutonomicData 2

who the N parties are o af least M non-fanlty partics. Tn an organizational setting, however, there may be a designated group of individuals who know about and hold the shards and have a policy for circumstances under which they can share the shards.

one-time Pad

As mentioned previously, the oxc-Lin O] (see also oto) may exhibit perfect security. The OTP is o venerable cyphersystem that has the advantage that it can be used manually without a computer. Besically & long string of random characters forms the pad. Somoone can use the pad w0 encrypt a plain-tex! message. The procedure is to combine each plain-test eharacter in order with the corresponding character from the pad. The combination is typically performed using modulo addition of the two characters but can be performed with a bitwise XOR. Because characters from the pad may only be used once, the pad must be at leust a6 long as the plain-text message, The one time use of » randorn string of characters from the pad is what gives the system its perfect security property. If two parties wish to exchange multiple messages, then the pad nust be at least as long as the sum of the length of all the messages. The main disadvantage of a one-time pad is that the two parties ‘must each obtain & copy of the same pad. This is less of a disadvantage for key recovery because the the encrypted message (keys) does not need to be exchanged with another for decryption but are decrypted by the self-same party so only one copy of the pad is needed.

Suppose for example, a OTP is used to encrypt the key or key history. Given that the adversary docs not have access to the OTP then the eneryption has perfect seereey which means that. the only viable attack is via brute foree. 17 the enerypied key or key history s at Ioast 128 bits long then brute forco is practicaly impossible Consequently the OTP encrypted key history could be safely stored in a public immutable database. The remaining problem is management of the OTP. Using an OTP 1o encrypt the ke history just creates a new problenn, that, of securing the OTP itself. But the main advantage of a OTP over secret, sharing deseribed above for ey recovery is that a OTP approach is non-multi-party interactive. It can be self-contained which is advantageous in data streaming applications.

One common but weaker variant of the OTP is the book eyper. Tn this variant the OTP is a book. Becanse the characters in a book are not a random string there is some degree of correlation

between characters that makes it Tess than perfectly sccure. Thus two parties who each have a copy of the same book (same edition) can use the eharacters in the book as the OTP to encrypt. messages without ever having to exchange copies of the book. Essentially using book as OTP s an cxample of hiding the OTP in plain sight. An adversary would have to guess that a book was being used as a one-time pad and then figure ont which book. For key rocovery, the key owner merely needs to remember which book and edition. Should the book used by the key owner be lost, the key owner can get another copy from a bookstore.

The book cypher is an interesting example due to the combination of simplicity, the use of existing but readily available sonrces of information, and the ability to hide the OTP as book in plain sight. This has the advantage that the only the titlo and edition of a book need to be remembered thus making light demand on human ‘memory. The primary disadvantage of the book cypher is that the text is not random and its difficult to caleulate how many bits of entropy are lost for a given book.

Hybrid Key Recovery Method

One of the main atiractions of using a one-time pad (OTP) for key recovery, in contras to socrot sharing, is that 04/26/18 Decentralized AutonomicData 2

it is non-multi-party interactive. A hybrid approach that makes a beneficial trade-off is to nse 2 mnemonic merely to generate a scod for a eryplographic strength psucdorandom number generator (CSPRNG). The scod is then used via the CSPRNG to generate a OTP that is then used o encrypt the key-rotation history. The cryplographic strength of the OTP is now governed by the length of the sed not the length of the pad. But key- rotation histories arc relatively short compared to the period of CSPRNG so a strong enough seod (128 bits of entrophy) would still be sufficient. for this task.

The PRNG algorithm must be of cryptogeaphic quality otherwise it conld bocome a sonrce of vuilncrability. A recent; advancement;in CSPRNG algorithms is a chaotic itcration psuedorandom mmber generators (CIPRNG: These are of cryptographic quality have extremely high statistical randomness. They pass both the NIST and DicHard tests for PRNG with periods on the order of 10° apt. The basic concept. is a chatic finite state machine clin. Unfortunately there do not yel appear (o be any open source implementations of (Lis algorithra. A more practial CSPRNG that, could be used 10 generate a OTP from a seed is the libsodium zandombytes_buf_deterministic function. This uses ChaCha20 under the hood.

The advantage of this hybrid approach is that the key recovery memory task is now limited to merely recovering the seed that wonld then be used to reproduce the OTP that would then be used in turn to decrypt the key history. This approach does not xequire multi-party interaction like scorct sharing as the seed is dircetly recovered by the owmer via a mnemonic device, not from others. This hybrid approach still benefits from the propertics of the OTP for encryption so that the key-rotation history can be cnerypied and stored online for recovery.

What remains then is the selection of a muemonic for generating the seed. It may be difficult for a single ‘memonic to provide & random source of seed material ot the required strength of 128 bits. Concatenating severel sources of mnemonically derived sced material, however, conld produce the roquired strength. This is akin to the DiceWare approach to passphrase generation. One problem with concatenation of seed material is that the order of concatenation must also be remembered. One way to avoid having to remember the order when combining multiple sources of seed material is to use the simple version of sccret splitting, In this form of secret splitt

ing, the secrei.is divided into shards and each shard is XORed togother to recover the soeret. Tn this case the secret is the sed and each shard contributes a cortain amount of entropy to the final sced. This allows & mnemonic for cach shard that may have much less than the required 128 bils of entropy but the combination of shards could have the required entropy and the order of the shards is not important. A non-ordored combination loscs some cryplographic strength because the number of possibilties is no longer merely the multiple of the independant possibilities from each shard (permutations) but is instead the number of combinations of the shards,

Suppose that there are four shards that each contribute 35 bits of entropy o in other words each shard is randomly choson from 2% possibilities. Then the combined number of possibilitics is 2 taken four at a time. The exact. formula. for the combination of N things taken K at a time is given by: N1/ (K1# (8-K) 1) Computing factorials for very largo numbers is a computationally intensive task. For the sake of analysis an approximation is sufficient. A lower bound on the nnmber of combinations of N things taken K af a time is (N/K)* (see bonnds) The bits of cryptographic strength of the combination of four shards cach with 35 bits is where N = 2° and K — 4. Using the approximation gives the mumber of possiblities to be at least (27/2%)! = 2%=2'% This corresponds 10 132 bits of entropy, which is greater than the required 128

04/26/18 Decentralisod AutonomicData 2

Tho ane romaining challenge then is to find good mnemonically recoverablo sources of random seed material. One feature that makes the The book cypher was attractive bocans it took advantago of information that was highly available but hidden in plain sight and whose source was easy Lo remember (a book title). The problem with books is that the content is not highly random so it in itsell is not a good source of seed material. In other words, the challenge is to ind sources of information for secd material that have much higher degree entropy than a book but are still aasy to romermbor. More specifcally this means finding sources of highly random soed material that ave highly available (thus do not requive sdditional infrastructure to buckup) but are aso essentially bidden in plain sight and easy to recall via a mnemonic device. What follows are several viable sources of mnemonically recoverable sources of random seed material.

Diceare eed Recovery

“The DiceWare approach can be repurposed to provide a mmemonic source of soed material, These can be used to recover the seed for the onetime pad used to encrypt the key-rotation history. Ten randomly seected words from DiceWare-compatiblo wordlist conld b used to genorate the seel for the one-timo pad. Ten randamly sclected words in ondor provide tho roquired 128 bits of entropy (recall that each DiccWare word provides 12. bits of cntropy). The order of the words is important. Fach word wonld be hashed using SHA-2 or Blake to generate a 16-byte string. Tho seed is created by concatenating tho hashes in the defined order. Once tho seed for the OTP is generated, the rest of the recovery method follows the process described above for generating the OTP using a CSPRNG and then using that to enerypt,/decrypt the key rotation history. The mnemonic load for this method is the recall the order of ten words from the DiceWare or EFF wordlist. This has a large mnemonic load 5o it would require some rehearsal and might not be very practical. Tn addition to the mnemonc at least a physical backup of the ten words should also be created. The physical backup of the ten words could be split into parts to make it more secure. If practical, a multi-party threshold secret sharing backup could also be created.

Github Secd Recovery

Github.com stores versioned code repositories. The associated git utility automatically caleulates a 160 it (20 byte) SHA-1 hash of each commit to a repository. These hashes are easily readable from t

he GitHub.com web site. Several Github commit hashes can be used to create the seed to generate the OTP for encrypting the key Totation istory. Tn order to tocover a conmmit hash ono must romembar the projoet and repository name, and the date of the commit. T thero are mulkiple commits on the same date then on must also remember which cornmit, like the last o the irst. This is not an onerons memory task bt not a rivial one.

“There are over 80 millon GitHub reposicoris. A sessonable estmmate of the average mumber of commits per repository is over 1000, This means that there are about 80,000,000 * 1,000 — 80,000,000,000 — 2% possibilities o choose from. 1f repoitory,commit is selected randoruly then the mumber of bits of entropy represented by @ singlo choice is about 36. To get 128 bits of security one wonld need to randormly sclect four repository,/comnits. A permutation of 4 gives 4(36) — 144 bits of entropy. Remembering the order of the four repositories adds another memory task. TF instead the fur chains were combinod using the simple varsion of seret. splitting daseribed abave, whore cach shard is XORed togothor to recover tho socret, then the numbor of random possibiltes s roduced t0 the mimber of combinations of $0,000,000,000 toms taken four at a time. As previonsly described, the lower bound on the number of combinations of N things taken K at a time is (N/K)™. In this case K = 4and N = 2% This gives tho mumber of possibilites to be (2%/2%)' — 2/"21%. This corresponds to 136 bits of entropy which is still greator than tho roquired 125

01726718 DecentralizedAutonomicData 2

The GitHub.com based recovery mechanism can be summarized as follows: Randomly choose four GitHub.com Tepository commits. For each commit, the pairing of a project name, repository name and commit date must be remembered and for backed up using a hardware backnp. Generate a seed by XORing together the 20-byte commit SHA-1 commit hash from each of the four repositories. Use this seed with a deterministic CSPRNG to gonerato a one-time pad of length at loast as long as the key rofation history. Enerypt. the key rotation history by bitwise XORing cach byte in the history with the corresponding byte from the one-time pad. Securcly discard the oue-time pad. Store the encrypted key-rotation istory in a bighly available database. This encrypted istory should be inpervious to attack 5o it can be stored online. When recovery is required, remember the four

project frepositorycommil-date pairings or restore from a hardware backup. Use the pairings to lookup the SHA 1 commit hashes from GitHub.com for each. Then recreate the sced by XORing the four commit hashes. Use the seed and the same CRPRNG to regenerate the one-time pad. Retrieve the key history from the database, Use the one-time par to bitwise XOR each byte of the saved encrypted key bistory to unencrypt it. The key bistory is now recovered.

The memory load is fonr triples of a project name, a repository name, and a date, or twelve itoms total, but the order of the triples is not, important. Given that typically cach GitHiub project has small number of repositorics, ‘merely remembering the projoct should make remembering the repository much easier by going to the projoct. page and looking at the choices for repositorics. The date is the hardest memory task. There are soveral well Known mnemonic techniques for remembering dates. Tn addition 1o the mnemonic, a physical backup of the hashes should also be creatod. The physical hackup could e split into four parts to make it more seeure. IF practical & threshold multi-party scerete sharing system cold provide additional backup.

FlckR.com Seed Recovery

The FlickR.com-based recovery mechanismn is similar to the Github.com bused one, There are over 10 billion primary photos on FlickR. Each primary photo may come in multiple resolutions. A given photo is displyed on the FlickR.com web page using a low-resolution copy. This displayed version can be scraped from the page, The Flickr.com website does not provide hashes of the images, so one would have to scrape or do

wnload an image and then caleulate the hash after the fact. A viable approach would be to use SHA-2 from the OpenSSL library or Blake from the libsodium library. Ten billion is about 2% which corresponds to about 33 bits of entropy when randomly selected. Four randomly selected images are needed to get the required 128 bits of entropy, that s, 4 * 33 = 132, If we combine the hashes from four images by XORing (ic. simplo sccrot splitting) then the number of choices becomes the combinations of 10 billion things taken fonr af a time. As doscribed above, the lower bonnd on the number of combinations of ¥ things taken K at a time is (N/K)™. This gives the mumber of possibilities to be (2%/2%)* — 2"'_9L This corresponds to 124 bits of entropy which s close enough to the required 125, (2 — 16, which is not meaningfully weaker as it wonld still take 500,000,000 years to break). The procedure for recovery is essentially the same as the GitHub example above, once the hashes for each photo have been generated.

The muemonic task is remernbering four images. Humans are very good at rementbering images given o selection, The hard nnenonic task is searching on FIickR for & given image using tags. It takes sbout four or five tags to get the lst of images to under 100 for a given tag set. The mnemonic task is then to remember four sels of four to five tags each, where the Lags are not in any order. Remembering which photo is helped by the fact tha the tag set typically corresponds to features of the photo. Moreover, imuges provide an opportunity to hide them in plain sight. In sddition Lo the mnemonic, a physical backup of the hashes should also be created. The physical backup could be spli into four parts to make it more secure. If practical a threshiold multi-party secret shuriag system 04/26/18 Decentralized AutonomicData 2%