SeedQuest . Didery Samuel M. Smith Ph.D. Internet Identity Workshop 2018.10.24 sam@samuelsmith.org
Motivation Decentralized Autonomic Data and the Three R’s of Key Management RWOT Spring 2018 https://github.com/WebOfTrustinfo/rebooting-the-web-of-trust- spring2018/blob/master/final-documents/DecentralizedAutonomicData.pdf Maintain a provenance chain for data flows that follows diffuse trust perimeter-less security principles Minimally Sufficient Means SeedQuest https://github.com/reputage/seedQuest Didery https://github.com/reputage/didery
DAD: Decentralized Autonomic Data Provenance for decentralized streaming data applications including transformations Decentralized: governance of the data may not reside with a single party, trust in the data provenance is diffuse, DID based.
Autonomic: self-managing or self-regulating. Self-managing includes cryptographic techniques for maintaining data provenance that make the data self-identifying, self-certifying, and self-securing. Autonomic implies the use of cryptographic signatures to provide a root of trust for data integrity and to maintain that trust over transformation of that data Key management is thus first order property of DAD items. 3 R’s Reproduction, Rotation, and Recovery
Recovery Methods
Physical
Shift exploit surface from network security to physical security
Good backup method
Memory burden is recall of physical location of physical backup Secret Sharing
Requires multi-party interactive infra-structure
Recovery burden placed on third parties ‘Mnemonic
Memory burden is lessened by using elaborative encoding techniques that humans are good at Hybrid
Minimally sufficient means
Memory Recovery Human memory incompatible with long strings of random numbers. Humans ill equipped for task of directly recalling cryptographic keys. Want a “seduction” mnemonic. Seduce users into effortless rehearsal Leverage human innate ability to recall complex spatial temporal visual auditory paths with little or no rehearsal = elaborative encoding, rich encoding. One time rehearsal. Memorable experiences. Dramatic, exiting, interesting, entertaining.
information-theoretic security:
crypto-system that cannot be broken algorithmically even if the adversary has nearly unlimited computing power including quantum computing. It must be broken by brute force if at all. Brute force means that in order to guarantee success the adversary must search every combination of key or seed.
perfect security:
special case of information-theoretic security where cipher text provides no information about the key
Practical Perfect Security
Secret Sharing or Secret Splitting:
Simple N of N
Threshold M of N One-time Pad:
Pad = string of random characters used to encode/decode message. Pad is as long as message.
Can be performed manually
Brute Force Cryptographic Strength Systems with perfect security the critically parameter is the number of bits of entropy needed to resist any brute force attack Entropy in bits per Shannon information theory number of bits = log,(number of random possibilities)
Convention is that 128 bits is sufficient =228 possibilities or random choices 1 million super computers each performing 1 quadrillion trials per second will take 8,589,934,592 years for brute force exploit
One-time pad Perfect security Book cypher Hiding in plain sight Recovery task means no need to exchange one-time pad = self-contained Complication with private key rotation history. Recover multiple keys Modify to recovery of seed for CSPRNG that deterministically generates a one-time pad. Strength bounded by seed entropy. Rotation history much much shorter than CSPRNG period
mnemonic = device or technique to aid human memory
memory task = recall 128-bit random number as a key or seed
need to recover set of private keys andjor private key rotation history not just a single private key
use a 128-bit random number as a seed (CSPRNG) to a crypto-system that hides and recovers the whole rotation history, such as, one-time pad.
Cryptographic strength governed by seed
elaborative encoding: use additional sensory cues to enhance recall, such as, story, path, spatial relationships, auditory, visual, color, fantastical juxtaposition
Example: method of loci or memory palace.
DiceWare randomly select words from 7776 word list log2(7776) = 12.9 bits per word 128 bits = 10 words in order Non-trivial memory load. Requires rehearsal.
Recovery Process Mneumonic to recall a single seed Seed used with CSPRNG to generate one-time pad One-time pad used to encrypt all the private keys Because method employs near perfect security the encrypted private keys may be stored in the open. Depends on value of data controlled by keys Recovery task is to recover seed, use seed to reproduce one-time pad, use pad to decrypt keys
SeedQuest —— Virtual world role play game that generates seed through playing Maximize elaborative encoding to Minimize mnemonic load
Entropy 16 sites = 24 = 4 bits of entropy per site selection Each site interior has 32 spots = 25 = 5 bits of entropy per spot Each spot has 4 actions = 22= 2 bits of entropy per task Each spot-action (task) choice = 5 + 2 = 7 bits of entropy Sequence of 4 tasks gives 4*7 = 28 bits of entropy Sequence of 4 sites each with 4 tasks = 4%(4 +28) = 128 bits of entropy Comparable to the easiest level in a game like Legend of Zelda Are you smarter than a ten year old?
SeedQuest Two Game Play Modes: Rehearsal Random seed selects path and tasks in sequence Recovery Play game to recall path and tasks in sequence
' - s frrr i - — = e ENCRIPT KEY USEDEMO SEED e -y "- e
. Y ) o
Rotation Rotation = Revoke and Replace Revoke only = Revoke and replace with null key Replace only = security vulnerability In general revocation and be implemented as special case of rotation
Why Rotate? Public key vulnerable to attack due to time exposure Continued use of private key increases vulnerability to exploit Challenge is rotation after suspected exploit, exposure, or capture of private key. Rotation operation that is signed by exploited private key is problematic. Seek minimally sufficient means. Using another key for rotation adds complexity and in a sense is just displacing the rotation problem without solving it.
Pre-Rotation Likelihood of exploit is a function of exposure to probing or continued monitoring. Narrowly restricting the the opportunity for exploit in time, place and method, such as, one time only, minimizes the vulnerability to exploit. Exploiter has to either predict the one-time event or has to continuously universally monitor all events. Create and declare the next “rotated” key (pre-rotated key) at the one-time only inception event for the original key. The private key of the pre-rotated key is then stored securely and is not exposed until a rotation event is needed. The rotation event is now another one-time event determined by the key owner Exploit of the original key cannot change the pre-rotated key or spoof a rotation event. Rotation is self-contained
Pre-Rotation Requirements Inception event is one-time only. Contains two public keys signed by original key. Rotation event contains three public keys. Original, Pre-rotated, next pre- rotated. Signed by original and pre-rotated. Private: pair-wise interaction requires recipient maintain log database of inception and rotation events. Can detect any replay attacks or attempts to spoof inception event. Public: redundant, immutable, persistent, time-stamped log database of rotation event history for a given original (inception) key on replicant servers
Inception Event { 54" "did:dad: Q27 ThNONZS 88T ThepSH-4HABLSAsHONLVALGFE=" “"changed" : "2080-01-01T08:00:00+00:08", “ensuen": SYqaL6LASpFORTIUNLOIRAU2_RXFPOALA3MYN1dS~" i Arvnirin U72]90KHgz99 oK BPSKHnYGuVER_3rpS_22034L985THr NI 1GOPbUT 11 CUpOSC LF_KCBSGCVRYOFRZAPIAQ-= Rotation Event { "54" "did:dad: Q27 ThNONZSa88VT TkepSH-HABLSAsHONLVALGFE-" “changed" : "2000-01-01T08:00:00+00:08", “GrSten™: "Qt27FTHMONZSaBETTkepGH- AHABLSASHONLVAIGFE=", “Signer”: "XqSYqaL6L4SpFOFu7IUNLETRaU2_RXFPOALA3MYN1ds-" “ensuer: *AZ7ANLD0- 101027 HSpQSGroAVKAF 2R TZNIKCor aY=" } Armewn JC3DMASGuyPGHFE K GVOBKDE0134UKZy TIYUHGoNY i REAEHS028P SHyUS-ULfHa 1 b IPURZVPTGIOA-= ARmrin 104 pItZ2 JgaCRSELIIpAnay Q0FAPHULTHIG7UKQZ21 172PebYFVICEKCABMGHOONATO - aJuGxIo2DA-=
Listed Pre-rotation Structure
Rotation Event { "id": "did:dad:Qt27¢THHONZSaB8Vr Tkep6H- GHABLTSASHONLVNIGFE=" , "changed" : "2000-01-01T00:00:00+60:00" , “signer”: 2, '[‘signsrs": "Qt27FThHONZS BBV Tkep6H-4HABLN5ASHONLVNIGFE=", "Xq5YqaL 6L48pFoFu7 IURLEIRAU2_RXFPOAL43WYn1aB=", “dZ74MLZXD~1QH0A73WIPQIGrOAVXGF 12RTZWLKCBraY=" “35yVH2woCpOVPFSDSZ0bU_OxNe2ZgxKjTQI6LL IMnA=" ] } Ar\n\rin AeYbSHOTOPMANACET 05 SDB1AUSQAFNHSUGWLTGPVNIQQOYKBYrPPXAOLC115SHC IDSBKFF FB10tDq8XG1zaCg== Arin\rin 09y JUKHHNIZF 10QDIK 6Vt 6 FPOXEXL 182 _4D-753CCYMUOHANGNVEYar_GHw_25CrHBAAZIAE SmL3thLmuseDW==
Multi-signature Pre-rotation
Didery Service with two functions: One Time Pad Encrypted Blob Storage DID Pre-Rotation Histories Server: Python Web Client Javascript (npm) Command Line Client, Python (pip)