0
$\begingroup$

https://www.microsoft.com/en-us/research/blog/password-monitor-safeguarding-passwords-in-microsoft-edge/

In this they mention

The server then evaluates a matching function on the encrypted credential, obtaining a result (True or False) encrypted under the same client key. The matching function operation looks like this: computeMatch(Enc(k), D).

How exactly do they perform it? As far as I can understand client data would be encrypted by their own private key and database will be encrypted using server's private key. So since keys mismatch they wouldn't be able to perform HME computations right? What am I missing here?

Improve this question
$\endgroup$
2
  • $\begingroup$ @kelalaka thanks I somewhat understand that answer but not sure how to implement that using SEAL or HELib to compare to integers. Can you provide me with basic idea on how to achieve it? $\endgroup$
    – Naveen S
    Mar 11, 2021 at 13:39
  • $\begingroup$ Most probably, there is no "key mismatch" because the database is not encrypted. $\endgroup$
    – Hilder Vitor Lima Pereira
    Apr 11, 2021 at 5:55

1 Answer 1

Reset to default
1
$\begingroup$

Let the client have public and private keys $k_{pub}, k_{prv}$ of a secure FHE (Fully Homomorphic Encryption). Now clients want to check that their password $pwd$ is on the breach list or not.

As stated on the MS site, to prevent the user from querying dictionary attacks on the server, they use hash $H$ of the form Oblivious Pseudo-Random Function (OPRF). The client calculates $h(pwd)$ then uses their public key and encrypts as $ = E(k_{pub},h(pwd))$. Now the client sends the $(c,k_{pub})$ to the server.

Now, the server, for each breached password $p_i$ calculates $c_i = E(h(p_i), k_{pub})$. Using the FHE equality circuit $C$ they compare each breached password's hash and the user's to get the result. Note that this result is encrypted and only the client can decrypt it. Now instead of sending each value to the user, they execute OR operation on the result to get only one value $v$.

The value $v$ sent back to the user and the user decrypt the single bit $b \stackrel{?}{=} D(k_{prv},v)$. If the $b=0$ mean not in the breach list, if $b=1$ mean it is on the breach list.

###Client
c = FHE_encrypt(k_pub, h(pwd)
send c to the server

###server
### Encrypt each password on the list
for each p in breachedList

    c[i] = FHE_Encrypt(k_pub, p)

###Calcualte the equality of the ciphertext
for i in sizeof breachedList 

    eq[i] = FHE_Equality_Circuit(k_pub, c[i], c)

v = E(k_prv, 0)

###Combine the results to reduce the bandwidth
###Not to reduce the dep a binary tree calculation must be preferred.
for i in sizeof breachedList 

    v = FHE_OR_Circuit(k_pub, v, eq[i])

return v

###
Client
b = FHE_Decrypt(k_prv,v)
if b = 1
   print ( "Change your password immediaately, it is on the breach list")
else
   print ( "Your password is not on the breach list")
Improve this answer
$\endgroup$
5
  • $\begingroup$ Regarding the FHE_Equality_Circuit I am not that familiar with circuit related things how can I replicate it in code using SEAL or HELib for integers/floating point numbers. $\endgroup$
    – Naveen S
    Mar 11, 2021 at 14:38
  • $\begingroup$ Are you familiar with SEAL or HELib? If so then, the circuit linked on the comment must be enough for you, also, in the linked answer there are articles that you can find in more detail. I wrote this answer since the last part is not included in that answer, combining the result to return encryption of a single bit. $\endgroup$
    – kelalaka
    Mar 11, 2021 at 15:13
  • $\begingroup$ That answer is too complicated for me as I am purely computer based cryptography background and no knowledge in circuits. I am stuck in converting the bit based circuit to code could you maybe provide a simple example. The step where you mention multiply the bits how exactly would I do that Homomorphically? $\endgroup$
    – Naveen S
    Mar 11, 2021 at 17:22
  • $\begingroup$ The circuit is used to define the function in your sense ( adder function, sort function, etc.), nothing is magical there. I think I've already provided enough circuits in the linked answer. Yes, this requires a circuit design in the special sense that you have mainly two operations ( but you can generate the rest), and not able to direct equality makes the problem. Did you implemented any function? $\endgroup$
    – kelalaka
    Mar 11, 2021 at 18:01
  • $\begingroup$ "Now, the server, for each breached password 𝑝𝑖 calculates 𝑐𝑖=𝐸(ℎ(𝑝𝑖),𝑘𝑝𝑢𝑏)." does that mean server will encrypt the database with client's public key for every request? that sounds like computationally expensive. $\endgroup$
    – Naveen S
    Mar 12, 2021 at 7:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.