Content deleted Content added
Jasonkresch (talk | contribs) m →Password-authenticated key exchange: fixed typo |
Altered template type. Add: url, chapter-url-access, chapter-url, isbn, volume, date, series, chapter, title. Removed or converted URL. Removed parameters. Some additions/deletions were parameter name changes. | Use this tool. Report bugs. | #UCB_Gadget |
||
| (29 intermediate revisions by 16 users not shown) | |||
Line 1:
{{Short description|
An '''oblivious pseudorandom function''' ('''OPRF''') is a [[
== Definition ==
Specifically, an OPRF is a [[Pseudorandom function family|pseudorandom function]] with the following properties:
* The parties compute: '''O''' = OPRF('''I''', '''S''')
* The first
* The second
* The function has the same security properties as any (cryptographically secure) [[
The function is called an ''
However, because it is only the second
== History ==
While conventional [[
▲While conventional [[Pseudorandom_function_family|Pseudorandom Functions]] computed by a single party were first formalized in 1986<ref>{{cite journal |last1=Goldreich |first1=Oded |last2=Goldwasser |first2=Shafi |last3=Micali |first3=Silvio |title=How to construct random functions |journal=Journal of the ACM (JACM) |date=1986 |volume=33 |issue=4 |page=792-807 |doi=10.1145/6490.6503 |url=https://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Pseudo%20Randomness/How%20To%20Construct%20Random%20Functions.pdf}}</ref>, it was not until 1997 that the [[Naor%E2%80%93Reingold_pseudorandom_function|first two-party Oblivious Pseudorandom Function]] was described in the literature,<ref>{{cite journal |last1=Naor |first1=Moni |last2=Reingold |first2=Omer |title=Number-theoretic constructions of efficient pseudo-random functions |journal=Journal of the ACM |date=2004 |volume=51 |issue=2 |pages=231–262 |doi=10.1145/972639.972643 |url=https://dl.acm.org/doi/10.1145/972639.972643}}</ref> but the term "Oblivious Pseudorandom Function" was not coined until 2005 by some of the same authors.<ref>{{cite book |last1=Freedman |first1=Michael |last2=Ishai |first2=Yuval |last3=Pinkas |first3=Benny |last4=Reingold |first4=Omer |title=Keyword Search and Oblivious Pseudorandom Functions |journal=Theory of Cryptography Conference |series=Lecture Notes in Computer Science |date=2005 |volume=TCC 2005 |pages=303–324 |doi=10.1007/978-3-540-30576-7_17 |isbn=978-3-540-24573-5 |url=https://link.springer.com/chapter/10.1007/978-3-540-30576-7_17}}</ref>
== Applications ==
OPRFs have many useful applications in [[cryptography]] and [[information security]].
These include [[PBKDF2|password-based key derivation]], password-based [[key agreement]], password-hardening, untraceable [[CAPTCHA]]s, [[
An OPRF can be viewed as a special case of [[homomorphic encryption]], as it enables another party to compute a function over an [[Ciphertext|encrypted input]] and produce a result (which remains encrypted) and therefore it learns nothing about what it computed.
=== Password-based key derivation ===
Most forms of password-based key derivation suffer from the fact that passwords usually contain a [[
▲Most forms of password-based key derivation suffer from the fact that passwords usually contain a [[Password_strength|small amount of randomness]] (or entropy) compared to full-length 128- or 256-bit encryption keys. This makes keys derived from passwords vulnerable to [[brute-force attack]]s.
However, this threat can be mitigated by using the output of an OPRF that takes the password as input.
If the secret key used in the OPRF is high-entropy, then the output of the OPRF will also be high-entropy. This thereby solves the problem of the password being low-entropy, and therefore vulnerable to [[
This technique is called ''
Further, since each attempt at guessing a password that is hardened in this way requires interaction with a server, it prevents an [[offline attack]], and thus enables the user or system administrator to be alerted to any password-cracking attempt.
The recovered key may then be used for authentication (e.g. performing a [[
=== Password-authenticated key exchange ===
A [[password]] can be used as the basis of a [[key agreement]] protocol, to establish temporary session keys and mutually authenticate the client and server. This is known as a ''
▲A [[password]] can be used as the basis of a [[key agreement]] protocol, to establish temporary session keys and mutually authenticate the client and server. This is known as a ''Password-Authenticated Key Exchange'' or [[PAKE]].
In [[basic authentication]], the server learns the user's password during the course of the authentication. If the server is compromised, this exposes the user's password which compromises the security of the user.
Line 55 ⟶ 45:
With PAKE, however, the user's password is not sent to the server, preventing it from falling into an eavesdropper's hands. It can be seen as an authentication via a [[zero-knowledge password proof]].
Various '[[Password-
An example of an augmented PAKE that uses an OPRF in this way is ''[[Password-
{{cite web |author=Tatiana Bradley |date=2020-12-08 |title=OPAQUE: The Best Passwords Never Leave your Device |url=https://blog.cloudflare.com/opaque-oblivious-passwords/ |website=The Cloudflare Blog}}</ref><ref>
{{cite web | first1= Daniel | last1 = Bourdrez | first2= Hugo | last2= Krawczyk | first3= Kevin | last3= Lewi | first4 = Christopher A. | last4= Wood | title = The OPAQUE Asymmetric PAKE Protocol (Internet Draft) | date= 2022-07-06 | url = https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-opaque | publisher = IETF }}</ref><ref name="mgreen" >
Line 65 ⟶ 55:
</ref>
Recently, OPRFs have been applied to password-based key exchange to [[back up]] encrypted chat histories in [[WhatsApp]]<ref>{{cite
=== Untraceable CAPTCHAs ===
A CAPTCHA or "Completely Automated Public [[Turing test]] to tell Computers and Humans Apart
Recently, CloudFlare developed a privacy-preserving technology called "Privacy Pass".<ref>{{cite web |last1=Sullivan |first1=Nick |title=Cloudflare supports Privacy Pass |url=https://blog.cloudflare.com/cloudflare-supports-privacy-pass/ |website=CloudFlare |date=9 November 2017 |publisher=CloudFlare.com |access-date=30 January 2024}}</ref> This technology is based on OPRFs, and enables the client's browser to obtain passes from CloudFlare and then present them to bypass CAPTCHA tests. Due to the fact that the CloudFlare service is oblivious to which passes were provided to which users, there is no way it can correlate users with the websites they visit. This prevents tracking of the user, and thereby preserves the user's privacy.▼
▲A CAPTCHA or "Completely Automated Public [[Turing test]] to tell Computers and Humans Apart."<ref>{{Cite web |title=What is CAPTCHA? |url=https://support.google.com/a/answer/1217728 |url-status=live |archive-url=https://web.archive.org/web/20200806173938/https://support.google.com/a/answer/1217728 |archive-date=6 August 2020 |access-date=2022-09-09 |website=Google Support |publisher=Google Inc. |quote=CAPTCHA (Completely Automated Public Turing test to tell Computers and Humans Apart) is a [...]}}</ref> is a mechanism to prevent automated robots or ([[Internet_bot|bots]]) from accessing websites. Lately, mechanisms for running CAPTCHA tests have been centralized to services such as a [[Google]] and [[CloudFlare]], but this can come at the expense of user privacy.
▲Recently, CloudFlare developed a privacy-preserving technology called "Privacy Pass"<ref>{{cite web |last1=Sullivan |first1=Nick |title=Cloudflare supports Privacy Pass |url=https://blog.cloudflare.com/cloudflare-supports-privacy-pass/ |website=CloudFlare |date=9 November 2017 |publisher=CloudFlare.com |access-date=30 January 2024}}</ref> This technology is based on OPRFs, and enables the client's browser to obtain passes from CloudFlare and then present them to bypass CAPTCHA tests. Due to the fact that the CloudFlare service is oblivious to which passes were provided to which users, there is no way it can correlate users with the websites they visit. This prevents tracking of the user, and thereby preserves the user's privacy.
=== An improved password manager ===
A [[password manager]] is software or a service that holds potentially many different
The first proposal for a password manager based on OPRFs was SPHINX.<ref>{{cite book |last1=Shirvanian |first1=Maliheh |last2=Jarecki |first2=Stanislaw |last3=Krawczykz |first3=Hugo |last4=Saxena |first4=Nitesh |chapter=SPHINX: A Password Store that Perfectly Hides Passwords from Itself |title=2017 IEEE 37th International Conference on Distributed Computing Systems (ICDCS) |date=2017 |pages=1094–1104 |doi=10.1109/ICDCS.2017.64 |isbn=978-1-5386-1792-2 |s2cid=4781641 }}</ref> It uses two devices (such as the user's laptop and phone) which collaborate to compute a password for a given account (as identified by the username and website's ___domain name). Because the user's two devices exchange values according to an OPRF protocol, intercepting the connection between them does not reveal anything about the password or the internal values each device used to compute it. Requiring two devices to compute any password also ensures that a compromise of either device does not allow the attacker to compute any of the passwords. A downside of this approach is that the user always needs access to both devices whenever they want to log in to any of their accounts.
▲A [[password manager]] is software or a service that holds potentially many different passwords on behalf of the a single user.
An OPRF is used by the Password Monitor in [[Microsoft Edge]] to allow querying a server for whether a credential (which the user saved in the browser) is known to be compromised, without needing to reveal this credential to the server.<ref>{{Cite web|last1=Lauter|first1=Kristin|last2=Kannepalli|first2=Sreekanth|last3=Laine|first3=Kim|last4=Cruz Moreno|first4=Radames|date=January 1, 2021|title=Password Monitor: Safeguarding passwords in Microsoft Edge|url=https://www.microsoft.com/en-us/research/blog/password-monitor-safeguarding-passwords-in-microsoft-edge/
Similarly to securing passwords managed by a password manager, an OPRF can be used to enhance the security of a [[key
For example, an OPRF enables a key-management system to issue [[
▲An OPRF is used by the Password Monitor in [[Microsoft Edge]]<ref>{{Cite web|last1=Lauter|first1=Kristin|last2=Kannepalli|first2=Sreekanth|last3=Laine|first3=Kim|last4=Cruz Moreno|first4=Radames|date=January 1, 2021|title=Password Monitor: Safeguarding passwords in Microsoft Edge|url=https://www.microsoft.com/en-us/research/blog/password-monitor-safeguarding-passwords-in-microsoft-edge/|archive-url=|archive-date=|access-date=January 1, 2021|website=Microsoft Research Blog}}</ref>.
▲=== A homomorphic key management system ===
▲Similarly to securing passwords managed by a password manager, an OPRF can be used to enhance the security of a [[key management system]].
▲For example, an OPRF enables a key-management system to issue [[Key_(cryptography)|cryptographic keys]] to authenticated and authorized users, without ever seeing, learning, or being in a position to learn, any of the keys it provides to users<ref>{{cite book |last1=Jarecki |first1=Stanislaw |last2=Krawczyk |first2=Hugo |last3=Resch |first3=Jason |chapter=Updatable Oblivious Key Management for Storage Systems |date=2019 |title=Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security |volume=November 2019 |pages=379–393 |doi=10.1145/3319535.3363196 |isbn=978-1-4503-6747-9 |chapter-url=https://dl.acm.org/doi/10.1145/3319535.3363196 |access-date=Jan 27, 2024}}</ref>.
=== Private set intersection ===
[[Private set intersection]] is a cryptographic technique that enables two or more parties to compare their private sets to determine which entries they share in common, but without disclosing any
▲[[Private set intersection]] is a cryptographic technique that enables two or more parties to compare their private sets to determine which entries they share in common, but without disclosing any entires which they do not hold in common.
For example, private set intersection could be used by two users of a social network to determine which friends they have in common, without revealing the identities of friends they do not have in common. To do this, they could share the outputs of an OPRF applied to the friend's identity (e.g., the friend's phone number or e-mail address).
The output of the OPRF cannot be inverted to determine the identity of the user, and since the OPRF may be [[
== Implementations ==
There are various mathematical functions that can serve as the basis to implement an OPRF.
Line 106 ⟶ 87:
=== EC and conventional Diffie–Hellman ===
Elliptic
This blinding can be viewed as a form of [[encryption]] that survives the computation performed by the second
▲Elliptic Curves and prime order fields can be used to implement an OPRF. The essential idea is that the first-party (the client), must cryptographically ''[[Blinding_(cryptography)|blind]]'' the input prior sending it to the second-party.
When the second
▲This blinding can be viewed as a form of [[encryption]] that survives the computation performed by the second-party. Therefore the first-party can [[decrypt]] what it receives from the second-party to "unblind" it, and thereby receive the same result it would have received had the input not been blinded.
For example, the second
▲When the second-party receives the blinded input, it performs a computation on it using a [[Key_(cryptography)|secret]]. The result of this computation must not reveal the secret.
The first
▲For example, the second-party may perform a [[Elliptic_curve_point_multiplication|point multiplication]] of a point on an elliptic curve. Or it may perform a [[modular exponentiation]] modulo a large [[prime]].
▲The first-party, upon receipt of the result, and with knowledge of the blinding-factor, computes a function that removes the blinding factor's influence on the result returned by the second-party. This 'unblinds' the result, revealing the output of the OPRF, (or an intermediate result which is then used by the client to compute the output of the OPRF, for example, by hashing this intermediate result).
==== Sample OPRF protocol ====
The following is [[pseudocode]] for the calculations performed by the client and server using an elliptic
▲The following is [[pseudocode]] for the calculations performed by the client and server using an elliptic curve based OPRF.
===== Client-side calculation =====
▲The following code represents calculations performed by the client, or the first-party.
<syntaxhighlight lang="java">
Line 153 ⟶ 131:
Notes:
The client computes the [[
As a final step, to complete the OPRF, the client performs a [[
===== Server-side calculation =====
The server receives the ''blinded input'' value from the client, and may perform authentication, access control, request throttling, or other security measures before processing the request. It then uses
▲The following code represents calculations performed by the server, or the second-party.
▲The server receives the ''blinded input'' value from the client, and may perform authentication, access control, request throttling, or other security measures before processing the request. It then uses it's own secret, to compute:
<syntaxhighlight lang="java">
Line 177 ⟶ 154:
Because the elliptic curve point multiplication is computationally difficult to invert (like the [[discrete logarithm]] problem, the client cannot feasibly learn the server's secret from the response it produces.
Note, however, that this function is vulnerable to [[Shor
=== RSA blind signatures ===
When the output of a [[blind signature]] scheme is deterministic, it can be used as the basis of building an OPRF, e.g. simply by hashing the resulting signature.
Line 186 ⟶ 162:
== Extensions ==
The OPRF construction can be extended in various ways. These include: verifiable, partially
▲The OPRF construction can be extended in various ways. These include: verifiable, partially-oblivious, threshold-secure, and post-quantum secure versions.
=== Verifiable OPRF ===
Many applications require the ability of the first
Fortunately, most OPRFs support verifiability. For example, when using [[RSA (cryptosystem)|RSA]] blind signatures as the underlying construction, the client can, with the public key, verify the correctness of the resulting [[digital signature]].▼
▲Many applications require the ability of the first-party to verify the OPRF output was computed correctly. For example, when using the output as a key to encrypt data. If the wrong value is computed, that encrypted data may be lost forever.
▲Fortunately, most OPRFs support verifiability. For example, when using [[RSA]] blind signatures as the underlying construction, the client can, with the public key, verify the correctness of the resulting [[digital signature]].
When using [[Elliptic Curve]] or [[Diffie-Hellman]] based OPRFs, then knowing the public key ''y = g<sup>x</sup>'', it is possible to use a second request to the OPRF server to create a [[zero-knowledge proof]] of correctness for the previous result.<ref>{{cite journal |last1=Jarecki |first1=Stanislaw |last2=Kiayias |first2=Aggelos |last3=Krawczyk |first3=Hugo |title=Round-Optimal Password-Protected Secret Sharing and T-PAKE in the Password-Only Model |journal=Advances in Cryptology |date=2014 |volume=ASIACRYPT 2014 - 20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taiwan, R.O.C., December 7-11, 2014, Proceedings, Part II |pages=233-253 |doi=10.1007/978-3-662-45608-8_13}}</ref><ref name="voprf">{{cite journal |last1=Davidson |first1=Alex |last2=Faz-Hernandez |first2=Armando |last3=Sullivan |first3=Nick |last4=Wood |first4=Christopher A. |title=Oblivious Pseudorandom Functions (OPRFs) Using Prime-Order Groups |journal=Internet Engineering Task Force |date=2023 |volume=RFC 9497 |doi=10.17487/RFC9497 |url=https://www.rfc-editor.org/info/rfc9497}}</ref>▼
▲When using OPRFs based on [[
=== Partially oblivious PRF ===
One modification to an OPRF is called a partially Specifically, a P-OPRF is any function with the following properties:
* The parties compute: '''O''' = POPRF('''H''', '''E''', '''S''')
* The first
* The second
The use case for this is when the server needs to implement specific throttling or access controls on the exposed input ('''E'''), for example, ('''E''') could be a file path, or user name, for which the server enforces [[access control]]s, and only services requests when the requesting user is authorized.
Line 211 ⟶ 184:
A P-OPRF based on [[Pairing-based cryptography|bilinear pairings]] was used by the "Pythia PRF Service".<ref>{{cite journal |last1=Everspaugh |first1=Adam |last2=Chaterjee |first2=Rahul |last3=Scott |first3=Samuel |last4=Juels |first4=Ari |last5=Ristenpart |first5=Thomas |title=The Pythia PRF Service |journal=24th USENIX Security Symposium (USENIX Security 15) |date=2015 |pages=547–562 |isbn=978-1-939133-11-3 |url=https://www.usenix.org/conference/usenixsecurity15/technical-sessions/presentation/everspaugh}}</ref>
Recently, versions of P-OPRFs not based on pairings have appeared, such as a version standardized in the [[IETF]] [[Request for Comments|RFC]] 9497
=== Threshold implementations ===
For even greater security, it is possible to [[
This can be done by having each server be a shareholder in a [[
▲For even greater security, it is possible to [[Threshold_cryptosystem|thresholdize the server]], such that the secret ('''S''') is not held by any individual server, and so the compromise of any single server, or set of servers below some defined threshold, will not expose the secret.
The client then takes some subset of the server's computed results, and combines them, for example by computing a protocol known as ''interpolation in the exponent''. This recovers the same result as
▲This can be done by having each server be a shareholder in a [[Secret_sharing|secret sharing scheme]]. Instead of using it's secret to compute the result, each server uses it's ''share'' of the secret to perform the computation.
▲The client then takes some subset of the server's computed results, and combines them, for example by computing a protocol known as ''interpolation in the exponent''. This recovers the same result as had the client interacted with a single server which has the full secret.
This algorithm is used in various distributed cryptographic protocols.<ref>{{cite web |last1=Cachin |first1=Christian |last2=Krawczyk |first2=Hugo |last3=Rabin |first3=Tal |last4=Stathakopoulou |first4=Chrysoula |last5=Resch |first5=Jason |title=Platform for Robust Threshold Cryptography |url=https://csrc.nist.gov/Presentations/2019/platform-for-robust-threshold-cryptography |website=NIST Computer Security Resource Center |date=14 March 2019 |publisher=NIST.gov |access-date=27 January 2024}}</ref>
=== Post-
Finding efficient [[Post-
▲Finding efficient [[Post-quantum_cryptography|post-quantum]] secure implementations of OPRFs is an area of active research.<ref>{{cite journal |last1=Boneh |first1=Dan |last2=Ishai |first2=Yuval |last3=Passelègue |first3=Alain |last4=Sahai |first4=Amit |last5=Wu |first5=David |title=Exploring Crypto Dark Matter: New Simple PRF Candidates and Their Applications |journal=Cryptology ePrint Archive |date=2018 |volume=Paper 2018/1218 |url=https://eprint.iacr.org/2018/1218}}</ref>
<blockquote>"With the exception of OPRFs based on symmetric primitives, all known efficient OPRF
constructions rely on discrete-log- or factoring-type hardness assumptions. These assumptions are known to fall with the rise of quantum computers."<ref name="oprf"/></blockquote>
Two possible exceptions are [[Lattice-
A more
== See also ==
* [[Random oracle]]
* [[Pseudorandom function family]]
Line 244 ⟶ 214:
== References ==
{{reflist}}
| |||