# Tag Info

127

The simple answer is that hashes don't ensure uniqueness. Very broadly, hashes behave like "deterministic random numbers" – deterministic in the sense that hashing the same data always gives the same answer; random in the sense that the value of the hash is basically unpredictable without actually computing it. And sufficiently unpredictable that, ...

29

Firstly, some definitions; Pre-image resistant: given a hash value $h$ find a message $m$ such that $h=Hash(m)$. Consider storing the hashes of passwords on the server. Eg. an attacker will try to find a valid password to your account. Second Pre-image resistant: given a message $m_1$ is should be computationally infeasible to find another message $m_2$ ...

12

... its practically impossible to recreate a hash that for any foreseeable endeavor its fine or is there some element that I'm missing that reduces even that extremely low probability to zero? The input space of hash functions is limited, but to a ridiculously large input message size ($2^{64} - 1$ bits), this will lead to an average of 2^{2^{64} - 1} \...

11

There are many advantages of MAC's over signatures. For signatures you need to use asymmetric key pairs. Public keys need to be trusted for this to work. Unfortunately establishing trust is not that easy. Furthermore you don't want to use a private key stored on, for instance, a smart card (which would require a PIN and would likely be too slow). Instead ...

11

First, you need more than just a signature, because a VRF produces both an output and a proof. To an observer, the output is uniformly distributed unless the observer also has the proof, which can be used to verify the output. With a signature scheme and a random oracle $H$, you could use a signature $s$ on a message $m$ as a proof and $h = H(s)$ as an ...

10

No, in general the hash isn't determined by the curve definition by NIST. Reasonable mappings of course exist (for a 224 bit curve you would probably use a hash with output size of 224 such as SHA-224). The hash used should however be specified by the protocol itself. The ECDSA key size as indicated by the -b of the openssh argument is linked to the hash ...

9

Keyed hashing is usually used to build message authentication codes (MACs), the most common of which is the hashed-based MAC (HMAC). MACs are basically cryptographic checksums. They are used to detect when an attacker has tampered with a message. Therefore they require a secret key (to be withheld from an attacker) and should be as fast as possible (to ...

9

MACs have some advantages over digital signatures The component of the computational cost that is independent of message size is much higher for digital signatures, to the point of being an obstacle and requiring milliseconds or/and dedicated hardware. We know no signature scheme where both signature and verification of short messages are of speed any ...

8

If the message is random each additional signature halves the security level. If the message is chosen by the attacker, two signatures (of messages where each bit differs) are enough for a complete break. A security level of about 64 bits can be broken by a determined attacker, and a level of 32 bits can be trivially broken on a single home computer. So if ...

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

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

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

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

I think you don't quite understand how RSA signatures work (and why they are the size they are). When generating an RSA signature, we follow a two-step process: We take that hash of the message we're signing, and convert (and pad) it into an integer $M$ which is between 0 and $N$ (where $N$ is a large integer that specified by the RSA key) We use the RSA ...

7

$w$ is a parameter that can be freely chosen, to maximize performance. Each element of the signature encodes $w$ bits of the message to be signed, so the larger $w$ is, the fewer elements you need to include in the signature. If you make $w$ large, then signatures can be shorter; however, the tradeoff is that key generation, signing, and verification run ...

7

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

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

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

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

A digital signature is not encryption using a private key, if not just because private key encryption is a contradiction in terms; anybody with a public key can decrypt. It is often explained as encryption with a private key because the RSA signature scheme uses modular exponentiation both for encryption as well as generating signatures. However, even the ...

5

I think you have some misunderstanding here. Finding collisions when knowing the trapdoor is a required feature, but leaking the trapoor when knowing collisions is an undesirable "feature" (which some constructions suffer from). A chameleon hash function (aka trapdoor commitment) allows you given the trapdoor to find pairs $(m,r)$ and $(m',r')$ with $m\neq ... 5 We can attack the MAC defined by: MAC(k,m)=MD5(m||k), in a chosen-messages setup, basically because MD5's collision-resistance is broken. The adversary chooses m and m' of the same length$b\ge64$bytes, differing only in their first$\lfloor b/64\rfloor\$ 64-byte blocks, such that there is a collision after hashing these blocks of m and m'. If follows that ...

5

Short version: the signature is correct, it is a real signature and therefore it is possible to verify it with one's favourite software. The scam is not based on a cryptographic attak but on what is signed. Craig Wright has recovered an old (and real) Satoshi's signature and tried to provide it as a new signature to validate his identity. It's, as someone ...

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

Your questions are good. The other answers cover them well, but I wanted to provide an answer which addresses your concerns in a less formal way. As far as I understand, hashes are just long alphanumeric strings. If one computes hashes across all documents, keys, information, files, etc, over and over again- its simply a matter of time until the same ...

5

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

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