# Tag Info

29

TL;DR: the assertion "SHA3 is more secure than SHA2" is unproven when we consider collision resistance, or preimage resistance. Addition: there are reasons to prefer SHA3, including being a more general tool since it's a plausible instantiation of a random oracle (contrary to SHA2 due to the length extension property). I refer to this answer for ...

22

This is more of an addendum to fgrieu's answer than an answer in itself, but 3 things stand out that COULD make SHA3 more secure than SHA2 from a design standpoint. The first and most obvious is the state size, SHA3 is substantially larger at 1600 bits than even SHA512... at only 512 bits. SHA3 being a sponge function gets its security level from how much of ...

18

This table—of Ed25519 vs. the lattice-based post-quantum candidate Dilithium vs. SPHINCS+ variants at a comparable post-quantum security level, with a tradeoff between signature size and signing time—may help explain: \begin{equation*} \begin{array}{r|rr|rr|rr} \text{sig scheme} && \text{sig bytes} && \text{cycles to sign} \\ \hline \text{...

9

As for the "foot-gun" issues with stateful hash-based signatures, it comes down to repeating state. Stateful hash-based signatures (XMSS, LMS) are moderately interesting (can be implemented with competitive signature generation time, and have a sum of public key and signature size which compares fairly well with other postquantum signature algorithms, based ...

9

I know you already mentioned length extension attacks in your question, but I don't think the importance of that can be overstated in how SHA3 is practically more secure than SHA2 - especially whenever you'll be designing your own cryptographic protocols/systems on top of it. Thanks to length extension attacks, use of SHA2 may require active measures (e.g. ...

8

The major issue will be size difference. The size of ECDSA in bitcoin is much less than the Lamport Signature. For ECDSA in bitcoin The public key is only 33 Bytes (1 byte for prefix, and 32 bytes for 256-bit integer x) Signature is at maximum 73 bytes Whereas in Lamport Signature The public key is 512 numbers of 256-bit (total of 16KB) The Signature ...

8

I see two problems with this idea. The first problem is Shor's algorithm; that's a quantum algorithm that is able to find the cycle length of a group (and if you can solve that problem, it is easy to factor and compute discrete logs). In this case, if we define the group of elements defined by the initial start state in the signature, where $H^n$ is the ...

8

Yes, a stateless hashbased signature method called Sphincs was recently proposed. It works by having a moderately large Merkle tree (similar to what D.W. suggested), but instead of using Lamport or Winternitz one time signatures at the bottom, it uses a hash based few-time signature method; this allows an occasional collision at the very bottom of the tree. ...

8

You can build a gigantic, enormous tree that has capacity for up to $2^{80}$ one-time signatures (say). Then, each time you want to sign something, you randomly pick a 80-bit value and use that to select which of the $2^{80}$ subtrees to use to sign the message. As long as the number of messages you intend to sign is much less than $2^{40}$ messages, a ...

7

Yes, there does happen to be such a scheme: the Lamport one-time digital signature. The basic idea of a Lamport signature is that the private key consists of a large number (say, 256) of pairs of secret random numbers, while the public key consists of the cryptographic hashes of those numbers. To sign a message, you first hash it down to 256 bits, and then,...

7

Gravity-SPHINCS and SPHINCS+ are two different improvements of the original SPHINCS algorithm. Both change the few-time signature scheme HORST (used in SPHINCS) in slightly different ways. However, both are variations of HORST. This leads to variable length signatures for Gravity-SPHINCS and fixed length signatures for SPHINCS+ which are as long as the ...

6

As D.W. notes, this works for the purpose in question. Actually, relying on number theoretic assumptions for the accumulators will give you no benefit as you have observed. However, here is a construction of accumulators from Nyberg in FSE'96, which does not rely on number theoretic or any computational assumptions. This is the paper of Nyberg and you may ...

6

Yes, they can be used for that purpose. The challenge in practice is exactly what you mentioned: if we're willing to trust number-theoretic assumptions, we usually don't need Lamport signatures. Nonetheless, they can be used in this way.

6

Use hash based cryptography. First, define a one way function F. It takes as input a small (10-16 byte) string and uses a secure hash function (EG:SHA2) to produce another string of the same size. We number each day from (Jan 1 2000) to (Jan 1 2100) with a number n (n=0 ... 36500) Each day is assigned a code. If the user has the code for a particular day, ...

6

No, use SHA256. If you look at https://bench.cr.yp.to/results-hash.html it seems that SHA256 would probably be the better choice concerning speed as well. Therefore I don't see a good reason to go with SHA-1.

6

W-OTS+ is stronger, as it makes weaker assumptions on the hash function. Let us take a rather extreme example, let us consider W-OTS and W-OTS+ based on the MD5 hash function. Now, the proof for W-OTS is quite invalid; it assumes that the hash function is collision resistant, and we know how to generate collisions with MD5. On the other hand, W-OTS+ based ...

6

Most of this was already explained in the comments but let me summarize this. a) SPHINCS+ as SPHINCS are stateless signature schemes like RSA or (EC)DSA. You can use the secret key to sign a virtually unlimited number of messages. In practice, you can sign up to $2^{64}$ messages with SPHINCS+ ($2^{50}$ for SPHINCS) without allowing any kind of forgery. ...

6

So as I understand, given the fact that the random bit masks are constant after instantiation of the scheme, SPHINCS is a deterministic scheme. Actually, Sphincs as originally proposed is deterministic; however there is nothing preventing a signer from selecting a path randomly (rather than making it a secret function of the message). But yes, if we assume ...

6

That's insecure. In BLS signatures: for private key $x$ and public key $X = xP$, the signature is computed as $T = xS$, and the verification checks if $e(T, P) = e(S, X)$, which works because: $e(T, P) = e(xS, P) = e(xS, P) = e(S, P)^x$ $e(S,X) = e(S, xP) = e(S, P)^x$ If you know that $S = kP$, then you can forge a signature for a message with hash $k'$ ...

6

Is it legit? No, and you hit on the reason - the algorithm converts the message into a series of 16 values from 1 to 128, and then signs based only on that. That's a total of 112 bits; actually, it's somewhat worse than that, as the algorithm they use to convert the message hash into the series of 16 values will generate values that always sum (mod 128) to ...

6

Consider $H$ defined as: SHA-512, with it's output XORed with the first 512 bits of the input message (padded with zeroes for short message). With such $H$, the proposed MAC is insecure. Yet, as far as we know, this $H$ is no worse than SHA-512 from a standard standpoint. Argument: observe that if $H(m_1\mathbin\|m_2)=\operatorname{SHA-512}(m_1\mathbin\|m_2)\... 5 There are few papers like XMSS that try to lower the requirement from collision resistant hash function to second-preimage hash function by introducing bit mask. Actually, that's not why XMSS has the bit masks; as you point out, second preimage resistance is essentially all you need for hash based signatures to be secure; the attacker needs to find a ... 5 It seems they can be used for that purpose. I found this paper: "Collision-Free Accumulators and Fail-Stop Signature Schemes Without Trees" Niko Baric and Birgit Pfitzmann Eurocrypt '97, LNCS, Springer-Verlag, Berlin 1997. 5 Can anyone explain why? That is because NIST specifically stated that stateful schemes were not allowed in the NIST postquantum competition, because they could not be implemented using the API that NIST has defined (which does not allow any state). That would appear to be reasonable, as stateful hash based signature methods do need extra care to implement ... 4 You might want to check the literature on (offline) schemes for electronic cash, where they have devised schemes where spending the same coin twice results in de-anonymizing the double-spender. I'm not immediately sure whether it will apply directly to your problem, but I think it might be possible to apply their techniques to your setting. 4 Given a set of (unhashed) Lamport signatures using the same key, an attacker can trivially forge a signature for any message whose$k$-th bit, for each$k$, is equal to the$k$-th bit of at least one of the signed messages. For example, let's say I know the Lamport signatures for the following 16-bit messages using the same key:$$m_1 = 0001111101110001 \\... 4 As I already outlined in this answer, hash trees in combination with any one-time signature scheme gives the so called Merkle signature scheme. I assume there is some misunderstanding and therefore I sketch merkle signatures subsequently: The idea is to produce$n$key pairs$(X_i,Y_i)$of a one-time signature scheme and then to take the hash values$g(Y_i)\$...

4

Though this question is fairly old, there is still no accepted answer. Hence, let me try to clarify this. The W-OTS scheme that your talking about was proposed by Ralph Merkle in his 1979 paper as an improved version of the Lamport-Diffie OTS to reduce the size of signatures. Instead of a "per-bit-signature", Merkle proposed to sign multiple Bits at once. ...

4

There are actually quite a few of these. Interest has been raised on this topic mainly due to the "post-quantum" security of such schemes. Also, Lamport is only a one-time signature, and we want a full-blown signature schemes. For just one example see, SPHINCS: https://sphincs.cr.yp.to/sphincs-20150202.pdf.

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