.\" This file is dual-licensed.  Choose whichever you want.
.\"
.\" The first licence is a regular 2-clause BSD licence.  The second licence
.\" is the CC-0 from Creative Commons. It is intended to release Monocypher
.\" to the public domain.  The BSD licence serves as a fallback option.
.\"
.\" SPDX-License-Identifier: BSD-2-Clause OR CC0-1.0
.\"
.\" ----------------------------------------------------------------------------
.\"
.\" Copyright (c) 2020, 2022 Fabio Scotoni
.\" Copyright (c) 2023 Loup Vaillant
.\" All rights reserved.
.\"
.\"
.\" Redistribution and use in source and binary forms, with or without
.\" modification, are permitted provided that the following conditions are
.\" met:
.\"
.\" 1. Redistributions of source code must retain the above copyright
.\"    notice, this list of conditions and the following disclaimer.
.\"
.\" 2. Redistributions in binary form must reproduce the above copyright
.\"    notice, this list of conditions and the following disclaimer in the
.\"    documentation and/or other materials provided with the
.\"    distribution.
.\"
.\" THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
.\" "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
.\" LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
.\" A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
.\" HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
.\" SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
.\" LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
.\" DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
.\" THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
.\" (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
.\" OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
.\"
.\" ----------------------------------------------------------------------------
.\"
.\" Written in 2020, 2022, and 2023 by Fabio Scotoni and Loup Vaillant
.\"
.\" To the extent possible under law, the author(s) have dedicated all copyright
.\" and related neighboring rights to this software to the public domain
.\" worldwide.  This software is distributed without any warranty.
.\"
.\" You should have received a copy of the CC0 Public Domain Dedication along
.\" with this software.  If not, see
.\" <https://creativecommons.org/publicdomain/zero/1.0/>
.\"
.Dd March 6, 2023
.Dt CRYPTO_ELLIGATOR_MAP 3MONOCYPHER
.Os
.Sh NAME
.Nm crypto_elligator_map ,
.Nm crypto_elligator_rev ,
.Nm crypto_elligator_key_pair
.Nd hiding of X25519 public keys
.Sh SYNOPSIS
.In monocypher.h
.Ft void
.Fo crypto_elligator_map
.Fa "uint8_t curve[32]"
.Fa "const uint8_t hidden[32]"
.Fc
.Ft int
.Fo crypto_elligator_rev
.Fa "uint8_t hidden[32]"
.Fa "const uint8_t curve[32]"
.Fa "uint8_t tweak"
.Fc
.Ft void
.Fo crypto_elligator_key_pair
.Fa "uint8_t hidden[32]"
.Fa "uint8_t secret_key[32]"
.Fa "uint8_t seed[32]"
.Fc
.Sh DESCRIPTION
These functions allow obfuscating X25519 public keys by making
them appear effectively indistinguishable from random noise.
This is of interest for key exchange protocols that require
indistinguishability from randomness, such as padded uniform random
blobs (PURBs).
They are intended for ephemeral (short-lived, possibly just one-time)
X25519 keys, not for long-term public keys.
After an initial key exchange involving hidden keys,
subsequent key exchange messages should be encrypted instead;
see, for example, the Noise Protocol Framework.
This is an
.Em advanced feature .
Unless you are implementing an protocol that requires
indistinguishability of all communications from random noise,
consider
.Xr crypto_x25519 3monocypher
instead.
Both this family of functions and
.Xr crypto_x25519 3monocypher
should be used as a building block to implement a key exchange protocol.
.Pp
For understanding what these functions do, it is important to note that
a
.Dq public key
in this context refers to a
.Em point on Curve25519 .
This also means that these functions are not compatible with
.Xr crypto_eddsa_sign 3monocypher
and related functions.
.Pp
.Fn crypto_elligator_rev
takes a public key
.Fa curve
and a
.Fa tweak ,
hiding the public key so that it is effectively indistinguishable
from random noise.
Note that only
.Xr crypto_x25519_dirty_fast 3monocypher
or
.Xr crypto_x25519_dirty_small 3monocypher
can generate a suitable public key;
the
.Xr crypto_x25519 3monocypher
function is insufficient.
The
.Fa tweak
must be chosen at random.
Even then, this operation
.Em may
fail because
not all curve points are capable of being hidden.
In this case,
.Fn crypto_elligator_rev
must be tried again with a new key pair,
though
.Fa tweak
does not need to be changed.
On average, two attempts are needed.
Once a suitable public key has been found,
.Fn crypto_elligator_rev
always succeeds for it.
Given the same values for
.Fa tweak
and
.Fa curve ,
.Fn crypto_elligator_rev
yields the same output value
.Fa hidden .
.Pp
.Fn crypto_elligator_map
performs the inverse operation:
It decodes a hidden point to a curve point on Curve25519.
.Pp
.Fn crypto_elligator_key_pair
is a convenience function that generates a secret key and its
corresponding public key, which is effectively indistinguishable from
random noise, from a random seed.
.Em The execution time of this function is unpredictable
because it may take many failures until a key pair could be generated
successfully.
.Fn crypto_elligator_key_pair
uses
.Xr crypto_x25519_dirty_fast 3monocypher
internally;
if code size is an important concern,
its functionality can be replicated with
.Xr crypto_x25519_dirty_small 3monocypher
instead.
.Pp
The arguments are:
.Bl -tag -width Ds
.It Fa curve
A point on the curve which is a Curve25519 public key generated with
either
.Xr crypto_x25519_dirty_fast 3monocypher
or
.Xr crypto_x25519_dirty_small 3monocypher .
.It Fa hidden
The hidden encoding of a point on the curve which is effectively
indistinguishable from random.
.It Fa secret_key
The secret key that was generated from the given
.Fa seed .
.It Fa seed
A 32-byte random number from which to derive a key pair.
See
.Xr intro 3monocypher
for advice about generating random bytes (use the operating system's
random number generator).
The
.Fa seed
is wiped automatically.
.It Fa tweak
A 1-byte random number,
which influences the final output of
.Fn crypto_elligator_rev .
.El
.Pp
The
.Fa hidden
and
.Fa curve
arguments may overlap or point at the same buffer.
.Sh RETURN VALUES
.Fn crypto_elligator_rev
returns 0 on success and -1 if the given
.Fa curve
argument is unsuitable for hiding.
.Pp
.Fn crypto_elligator_map
and
.Fn crypto_elligator_key_pair
return nothing.
They cannot fail.
.Sh EXAMPLES
Generate a key pair manually using
.Xr crypto_x25519_dirty_small 3monocypher
instead of its fast variant:
.Bd -literal -offset indent
uint8_t sk  [32]; /* Secret key output        */
uint8_t pk  [32]; /* Hidden public key output */
uint8_t tweak;    /* Random tweak input       */
arc4random_buf(&tweak, 1);
for (;;) {
    arc4random_buf(sk, 32);
    crypto_x25519_dirty_small(pk, sk);
    if (crypto_elligator_rev(pk, pk, tweak) == 0)
        break;
}
/* Now save the secret key and send the hidden public key. */
.Ed
.Pp
Performing a key exchange with the other party's public key having been
hidden:
.Bd -literal -offset indent
uint8_t hidden_pk [32]; /* Their hidden public key   */
uint8_t their_pk  [32]; /* Their unhidden public key */
uint8_t your_sk   [32]; /* Your secret key           */
uint8_t shared_key[32]; /* Shared session key        */
crypto_elligator_map(their_pk, hidden_pk);
crypto_x25519(shared_key, your_sk, their_pk);
/* Wipe secrets if they are no longer needed */
crypto_wipe(your_sk, 32);
.Ed
.Sh SEE ALSO
.Xr crypto_x25519 3monocypher ,
.Xr crypto_x25519_dirty_small 3monocypher ,
.Xr intro 3monocypher
.Sh STANDARDS
These functions implement the Elligator 2 mapping for Curve25519.
This mapping is incompatible with both the hash-to-curve Internet draft
and the implementation of Elligator 2 in libsodium.
Elligator 2 was described in:
.Rs
.%A Daniel J. Bernstein
.%A Mike Hamburg
.%A Anna Krasnova
.%A Tanja Lange
.%T Elligator: Elliptic-curve points indistinguishable from uniform random strings
.%J CCS '13: Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security
.%I Association for Computing Machinery
.%D 2013
.%P pp. 967\(en980
.Re
.Pp
Monocypher's Elligator 2 representatives are encoded as little-endian
254-bit numbers.
The two most significant bits (254 and 255) are not used.
.Fn crypto_elligator_map
ignores them,
and
.Fn crypto_elligator_rev
sets them at random.
The mapping uses 2 as the non-square
.Va Z ,
and [0..2^254-10] as the set of non-negative field elements.
See
.Lk https://elligator.org/map
for more details.
.Sh HISTORY
The
.Fn crypto_curve_to_hidden ,
.Fn crypto_hidden_to_curve ,
and
.Fn crypto_hidden_key_pair
functions first appeared in Monocypher 3.1.0.
In Monocypher 4.1.0,
they were renamed
.Fn crypto_elligator_rev ,
.Fn crypto_elligator_map ,
and
.Fn crypto_elligator_key_pair
respectively.
.Sh CAVEATS
Monocypher does not perform any input validation.
Any deviation from the specified input and output length ranges results
in
.Sy undefined behaviour .
Make sure your inputs are correct.
.Sh SECURITY CONSIDERATIONS
The secret keys for the public keys fed into
.Fn crypto_elligator_rev
.Sy must be chosen randomly
rather than deterministically.
Otherwise, the timing information given by the required number of
retries also leaks information on the secret keys.
.Pp
These functions
.Em help
build highly difficult-to-analyse protocols
but are insufficient by themselves:
Other metadata, such as the number of bytes sent in a packet or the size
of the 32-byte random looking string that represents the curve point
itself, can be very strong indicators of the use of cryptography.
Consider using appropriate padding algorithms, such as PADME,
and obscure other metadata as much as possible.
