| Thread Links | Date Links | ||||
|---|---|---|---|---|---|
| Thread Prev | Thread Next | Thread Index | Date Prev | Date Next | Date Index |
|
Hi Jay and Dan,
I saw this discussion thread and would like to share some of my thoughts about hybrid PQPAKE. Hope this makes things clearer.
1. How quantum computers break SAE and Cpace
Take SAE as an example. We will construct an offline dictionary attack for SAE using QC.
Suppose P is the result of hash-to-eleent: P = H2E(pwd). The attacker observes the SAE exchange messages, including: commit messages: s_A, s_B, E_A, E_B where s_A = r_A+ m_A, s_B = r_B + m_B, E_A = - m_A ⋅ P, E_B = - m_B ⋅P (I'm using the notations from Fig 1 of https://eprint.iacr.org/2019/383.pdf) Confirm messages: c_A = HMAC(kck, transcript), c_B = HMAC(kck, transcript)
Construct the following algorithm, where we treat the quantum computer as an oracle to compute discrete logarithm: Input: pwd' (a guess of password) P = H2E(pwd') use QC to compute m_A, m_B from E_A, E_B and P r_B = s_B - m_B ss = r_B ⋅ (s_A ⋅ P + E_A) derive kck from ss compare c_A with HMAC(kck, transcript), if match, then pwd' is the correct password
Using the above algorithm repeatedly over a password database constitutes a offline dictionary attack.
2. An attack to the composition of non-PQC PAKE and bare PQC key exchange
Draft 26/0005r0 adds an extra ML-KEM exchange in commit messages. To attack this protocol, we upgrade the adversary from a passive observer to an active one.
The basic idea is that, since the KEM exchange is not authenticated, the KEM exchange can be tampered and become transparent to adversary, thus does not provide extra security (even if the KEM transcript is augmented to the confirm message generation).
Consider this case: the adversary plays in the middle between legitimate STA and AP. The adversary interacts as follows:
receive commit message from STA: s_A, E_A, pk (pk',sk')= Keygen() send commit message to AP: s_A, E_A, pk' receive commit message from AP: s_B, E_B, ct' (ct, KEMss) = Encaps(pk) send commit message to STA: s_B, E_B, ct HMAC(kck, SAE_transcript [|KEM_transcript]) where kck is derived from SAEss and KEMss
Then adversary runs the following algorithm offline
Input: pwd' (a guess of password) P' = H2E(pwd') uses QC to compute m_A from E_A and P' r_A = s_A - m_A SAEss = r_B ⋅ (s_A ⋅ P' + E_A) derive kck from SAEss and KEMss compare c_A with HMAC(kck, SAE_transcript [|KEM_transcript]), if match, then pwd' is the correct password 3. Why this attack does not work for CPaceOQUAKE
CPaceOQUAKE is a sequential composition of two PAKE protocols, as opposed to the composition of a PAKE and a key exchange. Because the extra KEM exchange is also authenticate by the password, the above attack does not work any more (tampering OQUAKE messages forces adversary to guess one pwd).
Best, Jiawei From: Harkins, Dan <00003862fd143b8a-dmarc-request@xxxxxxxxxxxxxxxxx>
Sent: Tuesday, January 13, 2026 11:08:55 PM To: STDS-802-11-TGBT@xxxxxxxxxxxxxxxxx Subject: Re: [STDS-802-11-TGBT] 2026/4r0 PQC PAKE design in details No Jay, it doesn’t work. The issue is not confirming it, the issue is authentication. Notice how in CPaceOQUAKE they didn’t just add an ML-KEM secret to the CPace authenticated secret? No, they didn’t do that. They ran an additional PAKE, in this case OQUAKE. So there are two password authenticated key exchanges, one classical
(CPace) and one PQ (OQUAKE) that each generated *authenticated secrets* which are then combined. What you’re doing is a single password authenticated key exchange (SAE) and just appending an unauthenticated ML-KEM shared secret. If the classical crypto algorithm is successfully attacked by a quantum computer what you’re left with
is an unauthenticated ML-KEM secret. No, it doesn’t work. Dan. -- “the object of life is not to be on the side of the majority, but to escape finding oneself in the ranks of the insane.” – Marcus Aurelius From:
"yang.zhijie@xxxxxxxxxx" <yang.zhijie@xxxxxxxxxx> Hi Dan, Regarding the following question, ML-KEM public key and ciphertext are added into the first 2 messages, which is clarified in my slide, and the relevant text is in the PDT as well. I think we can add something in the last two confirm messages to verify the ML-KEMss and relevant parameter. like confirm = CN(SAE-KCK, send-confirm, commit-scalar, COMMIT-ELEMENT, peer-commit-scalar, PEER-COMMIT-ELEMENT,[public
key], [cipher text] ) Does it work? Thanks Best Regards Jay Yang (杨志杰)
Original From: Harkins,Dan <daniel.harkins@xxxxxxx> To: 杨志杰10343608;STDS-802-11-TGBT@xxxxxxxxxxxxxxxxx
<STDS-802-11-TGBT@xxxxxxxxxxxxxxxxx>; Date: 2026年01月13日
15:09 Subject: Re: [STDS-802-11-TGBT] 2026/4r0 PQC PAKE design in details Sorry, I meant to say, since ML-KEMss is not part of the first 2 messages how do you authenticate ML-KEMss? You still have not explained how ML-KEMss is authenticated. Dan. -- “the object of life is not to be on the side of the majority, but to escape finding oneself in the ranks of the insane.” – Marcus Aurelius From:
Daniel Harkins <daniel.harkins@xxxxxxx> Jay, How does a quantum computer obtain the password? I explained how it determined k (running Shor’s algorithm to compute a discrete logarithm). So tell me, how it obtains the password? Finally, you say, “can we authenticate both of them [DHss and ML-KEMss] based on the last two SAE confirm message.” That’s what I’m asking you. Since the ML-KEMss is not part of the last two SAE confirm messages, how do those messages
authenticate ML-KEMss? Dan. -- “the object of life is not to be on the side of the majority, but to escape finding oneself in the ranks of the insane.” – Marcus Aurelius From:
Jay Yang <yang.zhijie@xxxxxxxxxx> Hi Dan, Thanks for your valuable comment and response in time. If we apply your following comments to CPACEOQUAKE protocol, the same issue will happened in CPACEOQUAKE as well, because the QC can crack ISK derived in CPACE procedure, and then obtain
the password, CPACEOQUAKE protocol will game over finally. That's what I'm thinking you're correct on the OWE case as the QC don't need to guess the password, but there will be some different for DH-based PAKE solution, as QC has nothing to
know on the password at the very beginning, it has to use the guessed password and verify it in the later procedure. Actually, ML-KEMss is just one example to stir the PMK derivation in SAE to make it PQC security, we can use any PQC solution to stir the PMK
derivation,like PPK defined by RFC8784. For your following up question, the PMK /KCK is derived from combination of SAEss ||ML-KEMss, can we authenticate both of them based on the last two SAE confirm message exchange, or
if you think something missing, I can add based on your suggestion. Welcome your further comments. Thanks Best Regards Jay Yang (杨志杰)
Original From: Harkins ,Dan <00003862fd143b8a-dmarc-request@xxxxxxxxxxxxxxxxx> To: STDS-802-11-TGBT@xxxxxxxxxxxxxxxxx <STDS-802-11-TGBT@xxxxxxxxxxxxxxxxx>; Date: 2026年01月13日
13:15 Subject: Re: [STDS-802-11-TGBT] 2026/4r0 PQC PAKE design in details The quantum computer does Shor’s algorithm and determines a discrete logarithm in polynomial time which compromises the CDH which voids the security of the SAE -derived secret, k. That’s how. So why don’t you answer this question for me: In your proposal how is ML-KEMss authenticated? And I’m sorry but your article is from medium.com and behind a paywall so it’s not the most credible of sources and I can’t read it on top of that. I don’t know David Montgomery* but I’d ask him the same question. How is the “post-quantum
parts” authenticated? Unless you can tell me that then it’s not secure, as you allege. Dan. -- “the object of life is not to be on the side of the majority, but to escape finding oneself in the ranks of the insane.” – Marcus Aurelius From:
"yang.zhijie@xxxxxxxxxx" <yang.zhijie@xxxxxxxxxx> Hi Dan, Thanks for your comments during the call just now. If I recalled correctly, you said the quantum computer(QC) can crack the SAEss (K), could you elaborate how to make it based on the first two commit message exchange? In my mind, once
we concatenate SAEss and ML-KEMss as IETF TLS did before PMK derivation, it's impossible for the QC to only crack the SAEss . Please correct me if I make any mistake. The ideas in my contribution is quite similar to the following: please see the link as bellow. The another comment was relevant to transcript, I can add it during PMK derivation. Due to the time constraint, I don't have time to take other comments, we can discuss them in this
reflector. PQC in WPA3/WPA4 Handshakes: WPA3’s SAE is based on finite-field or elliptic curve
cryptography (it’s a password-authenticated key exchange using discrete log problems). To be quantum-safe, one idea is to perform a hybrid key exchange: combine the traditional SAE (to ward
off classical attackers) with a parallel PQC key exchange (like exchanging Kyber public keys within the handshake). This way, even if a quantum adversary records the exchange, they would need to break both the classical and the post-quantum parts to get the
key (which is conjectured to be infeasible). Efforts in other domains, such as TLS 1.3, have already defined hybrid key exchanges (e.g., combining ECDH with Kyber ). Wireless
Network Security in 2025 and Beyond | by David Montgomery | Medium Thanks Best Regards Jay Yang (杨志杰) To unsubscribe from the STDS-802-11-TGBT list, click the following link:
https://listserv.ieee.org/cgi-bin/wa?SUBED1=STDS-802-11-TGBT&A=1 To unsubscribe from the STDS-802-11-TGBT list, click the following link:
https://listserv.ieee.org/cgi-bin/wa?SUBED1=STDS-802-11-TGBT&A=1 To unsubscribe from the STDS-802-11-TGBT list, click the following link: https://listserv.ieee.org/cgi-bin/wa?SUBED1=STDS-802-11-TGBT&A=1 To unsubscribe from the STDS-802-11-TGBT list, click the following link: https://listserv.ieee.org/cgi-bin/wa?SUBED1=STDS-802-11-TGBT&A=1 |