Randomized Half-Ideal Cipher on Groups: Applications to UC-PAKE Eurocrypt 2023
This paper introduces Half Ideal Cipher for group domains, a concept weaker than an Ideal Cipher, with applications in secure protocols such as UC-PAKE. It discusses the construction of HIC, its role in replacing IC in various protocols, and the significance of using Ideal Cipher on group domains.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Randomized Half-Ideal Cipher on Groups with applications to UC (a)PAKE Eurocrypt 2023 Bruno Freitas Dos Santos Yanqi Gu Stanislaw Jarecki 1/18
This paper: Half Ideal Cipher for group domains (includes bitstrings!) I. Half Ideal Cipher (HIC) is a weakening of an Ideal Cipher (IC): 1. 2. when honest party encrypts, it needs to pad message with m = O(sec.par.) random bits when adversary encrypts, only m bits of the ciphertext are random II. HIC can replace IC in many protocols (all protocols below use HIC for password encryption): 1. 2. 3. EKE + NIKE EKE + anonymous KEM KHAPE [GJK 21] (same should hold for OKAPE [FGJK 22]) = UC PAKE = UC PAKE = UC aPAKE (asymmetric PAKE) III. We realize HIC for group domain G if there exists RO hash onto G (encryption/decryption cost one RO hash onto G) Talk Outline: 1. why Ideal Cipher on groups is useful for (a)PAKE s 2. previous implementations of IC on groups 3. our HIC construction and the HIC model 4. why HIC suffices as IC replacement in applications
Use of Ideal Cipher for groups (1): Encrypted Key Exchange [BM92,BPR00,BMP00, ,MRR20] EKE [BM92]: Key Exchange (KE) Password-Authenticated Key Exchange (PAKE) Idea: use passwords to encrypt KE messages (Example: KE = Diffie-Hellman KE) ?? ?? ??= ??.?(?? ,? = ??) ??= ??.?(??,? = ??) ? = ??.?(?? ,??) ? = ??.?(??,??) Alice = H[ ?? ?] Bob Hashed-DH: K = H DH ?,? [BPR00]: DH-KE + EKE = PAKE if encryption = Ideal Cipher on group g Simplified: [BPR00] key derivation includes other info $ g ? ??,? collision-resilience each C commits to one pw (with straight- line extraction) s.t. C is computed in forward direction on pw IC.E $ g ? ??,? reduction can embed KE challenge in any ciphertext decryption IC.D domain of DH-KE is a group need an Ideal Cipher on a group! [IC keeps table of (M,C) pairs for each pw]
Use of Ideal Cipher for groups (2): OKAPE aPAKE [FGJK22] [Jablon97, ,GMR06, ,BP13, ,Shoup20,GJK21,...] OKAPE [FGJK22] (like KHAPE [GJK21]): password-encrypt public keys in AKE asymmetric PAKE (aPAKE) ?? ? ?? Server s password file: ( ??,? ) = (? ?? ,?? ) ? ? ?? ?? ??= ??.?( ??,? = ??) ? = ??.?( ??,??) ? = ??, keyconf = ????(1) Alice Bob = H[ ?? ?, ?? ?] half-3DH : K = H DH ?,? ,DH ? ,? [FGJK22]: OKAPE = UC aPAKE if encryption = Ideal Cipher on group g
How to implement Ideal Cipher for groups? Standard cipher fails: If E = block cipher on n-bit strings s.t. g {0,1}n and ? = E ??,??. Problem: offline attack can eliminate ?? if M = D(?? ,?) does not encode an element of group g 1. Black-Rogaway [BR02]: If c =| g |/2n is not too small then use E(pw, ) in a loop starting from s0= ??, setting si= ? ??,?? 1, until you find siwhich is an element in g . Expected time = 1/c. Problem: timing information reveals information on pw! 2. 3. Use (randomized) quasi-bijective invertible encoding of group elements as bitstrings, e.g. Elligator2 [BHKL13] or Elligator2[Tib14]), then IC-encrypt the bitstring encoding. Problems: curve-specific, not on full domain (Elligator2), expanding, non-constant-time (Elligator2) Feistel with one wire = g (xor replaced by group operation) gives IC on extended group {0,1}nx g Problem: cost (needs 8 rounds of Feistel [DP07,CPS08,HKT11,DKT16,DS16] 4 hash-onto-curve ops) 4. McQuoid, Rosulek, Roy [MRR20]: 2-round Feistel ( 1 hash-on-curve) has sufficient key-committing / randomizing properties ( POPF: Programmable Once Public Function ) for EKE security Problems: game-based properties, hard to use, do not capture non-malleability (2F has malleable features) 5. Our observation: 2-Feistel + small modification = (UC) Half-Ideal Cipher (HIC), easier (and safer) to use
modified 2-Feistel (m2F) = Half-Ideal Cipher (HIC) 2-Feistel on group g modified 2-Feistel : group g operation H : hash onto group g g {0,1}n {0,1}n g r M r M g g H(pw, ) Cipher on extended domain D = {0,1}n x g H(pw, ) plaintext = (r,M) ciphertext = (s,T) H (pw, ) IC < H (pw, ) g T {0,1}n g s T {0,1}n s Claim: m2F compiles (1) RO hash H onto G and (2) IC on {0,1}ninto UC Half-Ideal Cipher (HIC) on {0,1}n x G same efficiency and generality as 2-Feistel: just one hash onto g , works whenever RO hash onto g HIC IC: collision-resilient, non-malleable, (straight-line) ciphertext-to-(pw,plaintext) extraction from IC.E calls, reductions can (straight-line) embed $ plaintexts in decryptions on IC.D calls why Half-Ideal Cipher? on (H)IC.E calls s-part of ciphertext is random but T-part can be arbitrarily chosen
modified 2-Feistel (m2F) = Half-Ideal Cipher (HIC) Half-Ideal Cipher on D = {0,1}nx g : UC model modified 2-Feistel Recall: g {0,1}n r M $ {0,1}nx g ?? , ? = (?,?) ? = ?,? HIC.E g H(pw, ) $ {0,1}nx g ? = (?,?) ?? , ? = ?,? HIC.D H (pw, ) IC < HIC keeps table of (m,c) pairs for each pw, $ choice is up to table[pw] = permutation g T {0,1}n s Claim: m2F compiles (1) RO hash H onto G and (2) IC on {0,1}ninto UC Half-Ideal Cipher (HIC) on {0,1}n x G same efficiency and generality as 2-Feistel: just one hash onto g , works whenever RO hash onto g HIC IC: collision-resilient, non-malleable, (straight-line) ciphertext-to-(pw,plaintext) extraction from IC.E calls, reductions can (straight-line) embed $ plaintexts in decryptions on IC.D calls why Half-Ideal Cipher? on (H)IC.E calls s-part of ciphertext is random but T-part can be arbitrarily chosen
modified 2-Feistel (m2F) = Half-Ideal Cipher (HIC) Half-Ideal Cipher on D = {0,1}nx g : UC model modified 2-Feistel g {0,1}n r M $ for s {0,1}n ?? , ? = (?,?) , ? ? = ?,? HIC.E g H(pw, ) $ {0,1}nx g ? = (?,?) ?? , ? = ?,? HIC.D H (pw, ) IC < HIC keeps table of (m,c) pairs for each pw, $ choice is up to table[pw] = permutation g T {0,1}n s Claim: m2F compiles (1) RO hash H onto G and (2) IC on {0,1}ninto UC Half-Ideal Cipher (HIC) on {0,1}n x G same efficiency and generality as 2-Feistel: just one hash onto g , works whenever RO hash onto g HIC IC: collision-resilient, non-malleable, (straight-line) ciphertext-to-(pw,plaintext) extraction from IC.E calls, reductions can (straight-line) embed $ plaintexts in decryptions on IC.D calls why Half-Ideal Cipher? on (H)IC.E calls s-part of ciphertext is random but T-part can be arbitrarily chosen
modified 2-Feistel (m2F) = Half-Ideal Cipher (HIC) Half-Ideal Cipher on D = {0,1}nx g : UC model modified 2-Feistel g {0,1}n r M $ for s {0,1}n ?? , ? = (?,?) , ? ? = ?,? HIC.E g H(pw, ) $ {0,1}nx g ? = (?,?) ?? , ? = ?,? HIC.D H (pw, ) IC < HIC keeps table of (m,c) pairs for each pw, $ choice is up to table[pw] = permutation k {0,1} g T {0,1}n s m2F realizes UC HIC m2F is indifferentiable from HIC: simulator SIM monitors H,H ,IC queries, answers H,H at random except: IC.E(k,r) query: SIM finds (pw,T) s.t. k=H (pw,T), sets IC.E(k,r):=s for s=HIC.E(pw,(r,M)) where M=T/H(pw,r) IC.D(k,s) query: SIM finds (pw,T) s.t. k=H (pw,T), sets IC.D(k,s):=r and H(pw,s):=M for (r,M)=HIC.D(pw,(s,T)) Simulation faulty if there are collisions in H outputs k or IC.D outputs r are not new: need = n = 2 x sec.par.
modified 2-Feistel (m2F) = Half-Ideal Cipher (HIC) Half-Ideal Cipher on D = {0,1}nx g : UC model modified 2-Feistel g {0,1}n r M $ for s {0,1}n ?? , ? = (?,?) , ? ? = ?,? HIC.E g H(pw, ) $ {0,1}nx g ? = (?,?) ?? , ? = ?,? HIC.D H (pw, ) IC < HIC keeps table of (m,c) pairs for each pw, $ choice is up to table[pw] = permutation k {0,1} g T {0,1}n s Note on HIC functionality in proceedings / eprint : The above E and D interfaces are called AdvEnc and AdvDec , for adversarial interfaces The functionality also has honest parties interfaces Enc and Dec which: do not expose randomness r to the environment on Enc interface honest party specifies only M, and functionality picks both (s,T) at $ (as in IC) Enc/Dec are almost wrappers over AdvEnc/AdvDec interfaces [$ free (s,T) $ free T followed by $ free s]
Using Half-Ideal Cipher (1): Encrypted Key Exchange (the EKE version in the proceedings needs 2 fixes) Simplified: omitted UC PAKE session identifiers sid and party identities A , B : must add to IC key or key derivation hash The EKE version in the proceedings: $ $ ?,? e.g. ? = ?? ??.??? ?,? ??.??? e.g. ? = ?? ??= ???.???(?) ??= ???.???(?) ?? ??= ???.???(?) ??= ???.???(?) = ???.???(? = ?2) ?? Adv (pw) ? = ???.???(??) ? = ???.???(??) ??= ??.? ?,? or $ ??= ??.? ? ,? = ?? [if ??.? = ??] 2 ? = ??.? ?,? Theorem: EKE + HIC = UC PAKE In proceedings we claim KE needs only passive security: not true (credit to [BGHJ]!) Fix: KE needs one-time active security, i.e. each ?,? = ??used once to B (active attack on B): Why? Assume Adv. knows pw, forwards ??to A (passive attack on A) and sends ?? Even if Adv. learns B s outputs K?= ??.? ? ,? then A s output K?= ??.? ?,? should be secure but K?is not secure given K?if ??.? = ??: if ? = ?2then ??= ?? Fix: use KE with one-time active security, e.g. ??.? = ?? ???? (CDH + ROM) ( [BPR00] version of EKE) 2
Using Half-Ideal Cipher (1): Encrypted Key Exchange (the EKE version in the proceedings needs 2 fixes): fix #2 Simplified: omitted UC PAKE session identifiers sid and party identities A , B : must add to IC key or key derivation hash The EKE version in the proceedings: $ $ ?,? e.g. ? = ?? ??.??? ?,? ??.??? e.g. ? = ?? ??= ???.???(?) ??= ???.???(?) ?? = ???.???(?;$) ??= ???.???(?) ??= ???.???(?) ?? Adv (pw) ? = ???.???(??) ? = ???.???(??) ??= ??.? ?,? or $ ??= ??.? ?,? = ?? ? = ??.? ?,? Theorem: EKE + HIC = UC PAKE True if (E,D) = IC on g If (E,D) = (H)IC on {0,1}nx g there is a subtle bug: Lesson to learn: (H)IC on {0,1}nx g differs from IC on g : For fixed key, new ciphertext does not imply new plaintext! to B (active attack on B) Assume again Adv. knows pw, forwards ??to A (passive attack on A) and sends ?? but now ?? If ? = ??.? ?,? then ??= ??: passive attack conditioned on ?? = ?? : disallowed by UC PAKE rules Fix: make ? = ?(??,??,??.? ?,? ) for RO hash H, then ??and ??become independent random = ???.???(?;$), i.e. ?? is a fresh re-encryption of same DH contribution ? which A sent in ??
Using Half-Ideal Cipher (2): EKE + anonymous KEM (EKE-KEM in the proceedings needs same fix) Simplified: omitted UC PAKE session identifiers sid and party identities A , B : must add to IC key or key derivation hash $ ?,? ???.?? ??= ???.???(?) ? = ???.???(??) ?,? ???.???(?) = ? ?,? re-encrypts same ? in ??then Same error: If ?? passive conditional on ?? = ?? attack Fix: add ??to key confirmation / derivation hash $ (?, ) output ? = ?(?) ? = ???.dec ?,? output ? = ? ? if = ? ?,? (else output K $) Recent work on eprint: GeT a CAKE: Generic Transformations from KEM to PAKE [BCPRR23] Almost identical compiler from anonymous KEM to PAKE, assuming IC encryption Includes ciphertext ??in key confirmation/derivation hashes But also includes password pw: Is it necessary?
Conclusions & some follow-up questions Conclusions: Introduced Half-Ideal Cipher : Relaxation of Ideal Cipher Good enough for EKE-like PAKE / aPAKE protocols Easy to construct for group domains (given RO hash onto the domain) Works for bitstrings too IC domain extender LWE-based PAKE Some Questions: The m2F circuit needs an Ideal Cipher on bitstrings of length n = 2 x sec.par. Can IC on 256 bits be constructed from e.g. AES-128? IC extenders [CDMS10,GL15] seem to have ?2/2?security loss, so can they start from an Ideal Cipher on blocks of length n=128? Is EKE (and other PAKE/aPAKE applications) secure for Enc = 2Feistel? Post-Quantum security of KEM PAKE compiler with Enc=m2F or Enc=2F? 14/18
