Hot answers tagged

7

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 ...


6

The original paper (Don Johnson, Alfred Menezes, Scott Vanstone. The Elliptic Curve Digital Signature Algorithm (ECDSA), International Journal of Information Security volume 1, 2001, pp. 36–63) is surprisingly quiet about the rationale for all of these. Check that $Q_a$ is not equal to the identity element $O$, and its coordinates are ...


6

Is it possible to retrieve $x_1$ and $x_2$ in this scenario? Yes. We multiply each equation by it's corresponding $k_i$ and reformat, giving $$\begin{array}{rrrrrrr} s_1\,k_1&&-r_1\,x_1&&\equiv&h_1&\pmod p\\ s_2\,k_1&&&-r_1\,x_2&\equiv&h_2&\pmod p\\ &s_3\,k_2&-r_2\,x_1&&\equiv&h_3&\pmod ...


5

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 ...


5

This isn't completely standard terminology, so you should check the precise definitions in your lecture notes. But I can't think of anything else that the exercise should be. You have a definition of the DSA signature process: given some parameters $(p,q,g)$, a private key $x$ and a message $m$, generate a nonce $k$ and calculate $(r,s)$ given by a certain ...


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

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

It is not possible: Let $d_A, d_B$ be distinct private keys. Then $$ s=k^{-1}(z+rd_A)=k^{-1}((z+r\;(d_A-d_B)) + rd_B) $$ So the pair $(r, s)$ is not only a valid signature for the public key $d_AG$ and the (partial) hash $z$, but also for the public key $d_BG$ and the message hash $z+r\,(d_A-d_B) \pmod n$. So in many cases (if there are no restrictions ...


4

As pointed out by @SEJPM, you can read more about security proofs for DSA/ECDSA family on this thread. As for whether there exists an interactive protocol corresponding to DSA/ECDSA à la Schnorr identification/Schnorr signature, not that I am aware of. I would add that this is unlikely for two reasons: The (unfortunate) reason for coming up with DSA/ECDSA ...


3

ECDSA is specified in SEC1. It's instantiation with curve P-256 is specified in FIPS 186-4 (or equivalently in SEC2 under the name secp256r1), and tells that it must use the SHA-256 hash defined by FIPS 180-4. I'll leave aside ASN.1 decoration (since the question uses none), conversions between integer to bytestring of fixed width (which all are ...


3

In ECDSA one randomly selects the private key $d_A$ from interval $[1,n-1]$, where the $n$ is the order of the Elliptic curve with $n-1$ non-trivial points, and with the point at infinity, $\mathcal O$ as the trivial point. $n = \texttt{FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141}$ that is 64 bytes, or as an integer $n = ...


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 ...


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 = ...


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 ...


2

Why does $p$ need to be a prime number? That's necessary for arithmetic modulo $p$ to be a field. For non-prime modulo, we only get a ring. That's important because we want to compute modular multiplicative inverses, and need a field for that to work consistently. More specifically: if $q$ is such that $0<q<p$ and $\gcd(p,q)\ne1$ (which is possible ...


2

However, suppose that you are aware of public key $K$ and are looking to do a tweak of $K$. Let $t$ be the tweaking factor, and so $tK=K'$. If you then wanted to prove that you are in possession of $t$, how would you do that? The obvious way to do this is a Schnorr proof of knowledge, which does precisely what you're looking for; given a public $K, tK$, it ...


2

If you know the sender's verification key previously: Yes, it does prove the authenticity and integrity of that message. No one else could have created a matching signature - for any message under that public key. As a side note: hashes of files are in theory a good idea to check that it was not changed. But when you get the hash from the same source as the ...


2

Depends if "between themselves" means that they are sort of in a simple group-chat scenario. Then one private-public-key pair (i.e. RSA) would theoretically suffice (not factoring in the security), because they can all encrypt messages with the public key and decrypt messages with the private key that they all have an identical pair of it. In actual group-...


2

The $k$ is randomly chosen as nonce (number used once) from the range $[1,q\hbox{ - }1]$ according to NIST FIPS 186-4. As far as I've searched there is no reason not to use $k=1$. The probability of selection $k=1$ is $1/q$ and that is actually is very small. You should not re-use any $k$. That simply breaks it. A linearly increased $k$ is also insecure. ...


2

Can we provably state that for a given payload and given private key, there is only one valid signature in the 512-bit signature space? No. If you consider EdDSA verification a legitimate signer can generate more than one signature of a given message, and all will pass EdDSA verification. However, only the signature generated with the EdDSA signing ...


2

No, the 00 simply indicates how many least significant bits are not used in the last octet of the BIT STRING. As the bit string contains an octet string (consisting of the sequence of two integers) it will always be zero, as all the bits in the BIT STRING are used. This is defined for the BER/DER encoding of BIT STRING itself. As for why the signature is ...


1

Yes. There is a difference between key strength, key size and the size of the encoding of a key. The modulus of the RSA private key determines the key size, for instance, but an RSA key commonly also contains the public, private exponent and CRT parameters, an encoding structure etc. etc. In GPG indeed the "key" consists of many additional parts as well (...


1

Among errors: In proper DSA, $s=\left({k_E}^{-1}\right)\,\left(h(x)+d\,r\right)\bmod q$, not $s=\left(h(x)+d\,r\right)\,α\bmod p$ as in the question.That computation (including the missing modular inverse) must be performed $\bmod q$; and $α$ is unwanted. That's mostly what prevents some examples from working. In proper DSA, $r=\left(α^{k_E}\bmod p\right)\...


1

Keeping your notation, signature generation in DSA is the following: $r = (\alpha^{kE} \bmod p) \bmod q$ $s = kEinv \times (h(x) + d\times r) \bmod q$ where $kEinv$ is the modular inverse of $kE$ modulo $q$. But you actually did was using the formula $s= (h(x)+d\times r) \times \alpha \bmod q$, and you forgot to reduce $r$ modulo $q$. You can take a look ...


1

Let's take a look at this from a higher level of view. In asymmetric cryptography, private keys provide some form of authentication. Let $(e, d)$ be a public/private key pair respectively of a secure asymmetric encryption scheme $E$, and let $c = E_e(m)$ be the ciphertext corresponding to the plaintext $m$. If one is able to recover $m$ from $c$, then it's ...


1

Yes. Pollard's $\rho$, a generic method to compute discrete logs, costs only about $2^{128}$ group operations for a group of order about $2^{256}$ so secp256k1 should be considered to have a ‘128-bit security level’, not a ‘256-bit security level’, against discrete logs. But a 128-bit security level is enough to thwart all adversaries—at least, the ones ...


1

Without explaining all details of ECDSA, a public key consists of a curve $E(\mathbb{F}_p)$ and a point $P \in E(\mathbb{F}_p) \setminus \{0\}$. The point $P$ is a random point chosen from all points of the curve (minus the point at infinity). Because the number of points must be large to be secure, it is very unliky that two randomly generated public keys ...


1

This is an old and off-topic question, but having just struggled a day with the same problem, couldn't resist answering. ASN.1 bignum's are tricky, and using the raw bytes from the token doesn't work. Instead, the data from token, two 256-bit integers R and S need to be first read by mbedtls_mpi_read_binary after which the ASN.1 signature can be written by ...


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