Hot answers tagged

32

What you seem to be looking for is deniable authentication. This is actually a somewhat stronger property than what you're asking for: it guarantees that the recipient (let's call him Bob) cannot cryptographically convince anyone else that the sender (let's call her Alice) signed the message, even if he discloses all his private keys, simply because the ...


14

Lets say Alice wants to send Bob a sensitive message, she wants to prove to Bob that it came from her, but she doesn't want Bob to be able to prove that to anyone else. A MAC is a good way of doing this. If Alice and Bob share a MAC key (and only they have it) then Bob will know any message authenticated with that MAC key came from Alice, since he knows he ...


12

There's a few different related parts here, and the nomenclature of the library you've cited is a little confusing. Curve25519 is an elliptic curve over the finite field $\mathbb F_p$, where $p = 2^{255} - 19$, whence came the 25519 part of the name. Specifically, it is the Montgomery curve $y^2 = x^3 + 486662 x^2 + x$, but you don't need to know the ...


10

If you follow the references in RFC 8446, you'll see that it cites RFC 8032 for the definition of the EdDSA-based algorithms. RFC 8032 in turn tells you all the details about the hash functions and other parametrization—field, curve equation, base point, encoding, signature equation, etc.—of EdDSA for Ed25519 and Ed448. There are several roles for a hash ...


10

Hash algorithms: Ed25519 uses SHA-512 (As referenced on wikipedia or on bearssl.org) Ed448 uses SHAKE-256$^1$ (As referenced on bearssl.org) $^1$ SHAKE-256 is a SHA-3 algorithm, a subgroup of the "Keccak" family.


9

(The (EC)DSA algorithm involves two functions: (i) the "conversion function" $f$, which for the case of DSA is a modulo $q$ operation and for ECDSA is the modulo $q$ operation applied to the $x$-coordinate of the input point; and (ii) $H$ a cryptographic hash function applied to the message.) Brown [B] showed that the DLP implies security of ECDSA in the ...


6

The SM2 digital signature algorithm. Fix a curve $E/k$ over a field $\mathbb F_p$. Fix a standard base point $G$ of prime order $n$ on $E/\mathbb F_p$. Fix a hash function $H\colon \{0,1\}^* \to \mathbb Z/n\mathbb Z$. A public key is the encoding of a point $P \in E/\mathbb F_p$ together with an string $Z$ identifying a principal. A signature on a ...


6

In short, TPMFail attack is black-box timing analysis of TPM 2.0 devices deployed on computers. The TPMfail team is able to extract the private authentication key of TPMS's 256-bit private keys for ECDSA and ECSchnorr signatures, even over networks. This attack successful since there was secret dependent execution in TPMs that causes the timing attacks. To ...


5

Consider the function $f\colon \mathbb Z \to \mathbb Z$ given by $f(x) = g^x \bmod p$ where $g$ has order $q$ modulo $p$. If $x \equiv y \pmod q$, then necessarily $f(x) = f(y)$, since by hypothesis $x = y + \ell q$ for some $\ell$, so \begin{equation} g^x \equiv g^{y + \ell q} \equiv g^y g^{\ell q} \equiv g^y (g^q)^\ell \equiv g^y 1^\ell \equiv g^y \...


4

It is potentially a bottleneck, but will it be a problem in practice? My phone doesn't have 10TB of storage, and if the files are remote the network speed will be the limiting factor. There are other strategies possible, like computing hashes as the data is transferred to the device, or hash trees for updating a hash without re-computing the whole thing (...


4

If you wanted to compute secp256k1 discrete logs, you would use Pollard's rho, except of course the cost is far beyond your budget so it won't do you any good anyway. The number field sieve is applicable to finite fields and to elliptic curves that admit embeddings into relatively small finite fields. Such elliptic curves are called pairing-friendly, and ...


4

The question deals with the finite field $\mathrm{GF}(p^n)$. It wants to study/attack a variant of DSA in (the multiplicative subgroup of) that field, rather than $\mathrm{GF}(p)$. Whatever that DSA variant is, it can be attacked by solving the Discrete Logarithm Problem in $\mathrm{GF}(p^n)$. The multiplicative subgroup of $\mathrm{GF}(p^n)$ has order $p^n-...


4

If you happen to generate two signatures of different messages that have the same $r$ value but different $k$ values, does it break security? No, it doesn't break security. Suppose you happened up use two different $k$ values ($k$ and $k'$) that just happened to result in the same $r$. Then, when you publish the corresponding $s$ values, you would publish:...


4

From SEC1 v2.0 (§4.1, pp. 43–47), a public key is a point $Q \in E$, and a signature on a message $m$ is a pair of integers $(r, s)$ satisfying the signature equation (condensed from several steps): \begin{equation*} r \stackrel?= f\bigl(x([H(m) s^{-1}]G + [r s^{-1}]Q)\bigr), \end{equation*} where $f\colon \mathbb Z/p\mathbb Z \to \mathbb Z/n\mathbb Z$ ...


4

Supplying ECDSA with deterministic input doesn't make for a one-time signature—RFC 6979 chooses the per-signature secret as a deterministic but secret function of the message. However, there is a variant of ECDSA—or EdDSA—that could probably work. In ECDSA, a public key is a point $A$ on a curve with standard base point $G$, and a signature on a message $m$...


4

TPM-Fail is a new demonstration of the well-known lattice-based attack of Howgrave-Graham and Smart on DLOG-based signature schemes such as Elgamal, Schnorr, and DSA that exploits partial information about per-signature secrets. TPM-Fail specifically applies the attack with timing side channels from the cryptogrpahy decelerators in TPMs. The attack had ...


3

Your last sentence is strange; if a non-cryptographic hash function can be used for digital signature then it will be a cryptographic hash function and that needs to satisfy the common requirements as pre-image resistance, second pre-image resistance, and collision resistance. If you need speed, you may look at Blake series which is faster than SHA-3, SHA-...


3

First note that this is essentially the same problem as if you just generated the curve parameters and now wanted to find out the order, so we can use the same strategies as for that case here: Ask a tool like sagemath: EllipticCurve(GF(17),[2,2]).cardinality() which constructs an elliptic curve over $\mathbb F_{17}$ with $a=2,b=2$ and finds out its ...


3

Suppose you have two message signature pairs and following values are then public i.e. known to you - The public keys: $Q_1 (= x_1G)$, $Q_2 (= x_2G)$ The messages and their hashes: $m_1$, $m_2$, $H(m_1)$, $H(m_2)$ The signatures: $(r_1, s_1)$, ($r_2, s_2$) The following are unknown - The private keys: $x_1$, $x_2$ The nonce: $k$ The following relations ...


3

Actually, doing $k-1$ multiplications isn't all that much less than what can be achieved using a more sophisticated power algorithm (say, base $2^w$, for an appropriately chosen $w$) - and these algorithms don't need a precomputed table. On the other hand, there are more sophisticated precomputational algorithms out there, which drastically reduce the ...


3

Actually you are both wrong, assuming that each user wants to authenticate themselves individually and / or establish private conversations between pairs. Unfortunately this is assumption is missing from the question. If everybody is using (EC)DH then they need a key pair each to setup communication by establishing a session key. That means 10 times 2 keys = ...


3

You are referring to two different protocols. The second source is linked to the DSA (Digital Signature algorithm). This uses modular exponentiation in a group of prime order over the integers. The first one is a version of the DSA over Elliptic curves, namely ECDSA (Elliptic Curve Digital Signature Algorithm). They basically work the same. You have a ...


2

Is there a "sane" implementation of the algorithms used by bitcoin? e.g. are there high-quality implementations available that incorporate defenses against side channel attacks? libsecp256k1 Does OpenSSL already protects against side-channel attacks? haha* How can I train myself to evaluate whether an existing implementation is vulnerable to certain ...


2

So the question may be rephrased to—is it still sane to use raw ECDSA signature in 2019? It's not insane, but you should use Ed25519 in any new applications: it is faster, simpler, and more confidence-inspiring. However, the standard notion of security of a public-key signature scheme—EUF-CMA, or existential unforgeability under chosen-message attack—says ...


2

A lot of libraries will define the point at infinity as $\mathcal{O} = (0, 1, 0)$ (or as $(0, 1)$ if using affine coordinates). Note that the Wikipedia article you link states: Verify that $r$ and $s$ are integers in $[1,n-1]$. If not, the signature is invalid. And a little further down: The signature is valid if $r\equiv x_1 \pmod{n}$, ...


2

In ECDSA, the R value in the signature is not the elliptic curve point $kG$, but instead only its x-coordinate, that is, an integer. So, what do you mean by R' + (C*G)? In particular, what do you mean by the operator +? If you mean "the + is an integer modular addition, that is, we take the x-coordinate of the point $CG$, and then add it (modulo $n$) to $...


2

Pick a coordinate field $\mathbb F_p$, such as $p = 2^{256} - 2^{32} - 977$. Pick an elliptic curve over $\mathbb F_p$ of the form $y^2 = x^3 + a x + b$, such as $a = 0$ and $b = 7$. (This is the curve secp256k1 used in Bitcoin.) Pick a standard base point $G$ of prime order $\ell$, so that $\ell$ is the smallest positive integer such that $$[\ell]G = \...


2

What's the use of that k? The following lines of the wiki tell you: Compute $r := ( g^k \bmod p ) \bmod q$ Compute $s := ( k^{−1} ( H(m) + xr ) ) \bmod q$ That is, it is used to compute both $r$ and $s$. However, that's not what your really asking. You're asking "why did they design DSA that way?" Well, it's actually a variation on a ...


2

An EdDSA signature is a sequence of bytes encoded according to the EdDSA paper or its extension to more curves, or according to RFC 8032, which should be treated as opaque by callers. In particular, for an instance of EdDSA on a curve $E$ over a field $\mathbb F_p$ of order $p < 2^{b-1}$: A public key is a $b$-bit bit string $n \mathbin\| \underline y$ ...


2

Public keys in this system are very sparse: for any $x$ value there are at most two possible $y$ values satisfying $y^2 = x^3 + ax + b$ where $a$ and $b$ are the curve parameters, since the equation is quadratic in $y$. (And $x^3 + ax + b$ has a square root at all only for some values of $x$; by Hasse's theorem, the number of points on the curve can't be ...


Only top voted, non community-wiki answers of a minimum length are eligible