# Tag Info

10

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

7

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

7

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

7

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

6

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

6

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

5

If he chooses $s$ at random, then the scheme will be stateless but will fail after using the same $s$ twice, which should happen after giving approximately $\:$$\Theta$$\big(\hspace{-0.05 in}$ $2^{H/2}$$\hspace{-0.01 in}\big)\:$ signatures. If he chooses $s$ by applying a PRF to $g(m)$, then the scheme will be deterministic and stateless, but can be ...

5

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

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

Note that the signature is $(s,e)$ where $s=k-xe$. If you can learn $k$ since it is predictable, then you can learn the secret signing key by computing $x = (s-k)/e$. Note that even without a concrete attack, the proof of security completely breaks down if the value $k$ is not chosen randomly. Having said this, it is possible to change the scheme to be ...

4

Yes, it makes sense to truncate the hash to 128 bits. The security proof actually says that if finding a preimage for F requires effort $2^{n}$, then breaking the Lamport signature scheme with $G$ having k-bit digests requires effort $2^{n}/2k$. So strictly speaking, with $F$ truncated to 128 bits and $G$ having 256 bits $(2k=512=2^{9})$, you will have $128-... 4 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 ... 4 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 ... 4 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 ...

4

Is is feasible to alter b and produce a valid MAC under the unknown key? We most certainly hope not. The fundamental security property of a MAC is that, even if that attacker can get a huge number of valid (Message, MAC) pairs (where he gets to choose the messages), he still is unable to generate a MAC for a message he has not seen. This fundamental ...

4

Can someone quote a protocol, application, etc, where the disadvantages of the MAC relative to digital signatures can be ignored? Your particular attack is of no interest if B has nothing to gain to claim that it got message M from A. As for concrete examples: the TLS record format, IPsec, SSH, the IES public key system; actually, any protocol that ...

3

No, it is generally not OK to send only part of the signature, because then it can no longer be checked; that's unless we remove only very little of the signature; or unless the term signature is used for what really is a symmetric Message Authentication Code (in which case shortening only reduces the security, perhaps acceptably). For any signature ...

3

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

3

Issues with the question first: Security is not something you can duct tape on to anything you want after the fact. You can never increase information entropy by processing data. It can be kept constant or decreased depending on whether you are doing a lossless or lossy tranformation. HASH("secret"+"public") is not necessarily secure for all crypto-hash ...

3

SpookyHash is clearly designated by its authors to be a non-cryptographic hash. In the cryptographic world there is simply no room for semi-broken at this level. Either there is some kind of margin to reach, say 128 bit security level or there isn't. This means that it should stand up to the current known attacks and that the design conveys enough piece of ...

3

You've stumbled on the requirement for authentication. Recall that signature schemes have a private key and a public key. The private key is used to sign the document in question, and the public key is given to the verifying party so that they can verify that the signature is correct. You're correct that it is possible to strip a digital signature and ...

3

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

3

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

3

HMAC nor a KDF is needed here. As long as you always use a constant size key and "tag" (generally called a nonce, as in number-used-once) you can simply use a secure hash function, like SHA-256. My suggestion is to drop keeping track of the tags sent so far - this administration is bound to fail at some point. Instead, generate a 32 byte random number. This ...

3

The only requirement is $i,b \neq i^*,b^*$ where $i^*$ is a random value from $1$ to $l$ and $b^* \gets\{0,1\}$ So if $b^*=0$ then $b=1$. Don't get confused by the $x$, it has nothing to do with the secret key, it's just a variable that later becomes $y_{i,b}=f(x_{i,b})$. It could as well be called $a$.

3

Well, $f$ is assumed to be a one-way function. That means, there cannot exist an efficient algorithm for finding preimages under $f$. The algorithm $A'$ is what we call a reduction. We are trying to show that an efficient algorithm for attacking the signature scheme does not exist. To do that, we assume the contrary, i.e. we assume an efficient algorithm $A$...

3

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

3

In general (without talking about MD5): Suppose our hashfunction $H$ is a Merkle-Damgard construction using a Davies-Meyer compression function $h=(H_i,m)=E_{m_i}(H_{i-1})\oplus H_{i-1}$. Since the compression function is public, everybody is able to compute the input to the final round of the MD-Hash. In addition, if you know the input to the final round ...

3

To start with, it's certainly not a bad idea to avoid SHA-1 when other algorithms exist, which do not have the SHA-1 weaknesses to anyone's knowledge. The security of SHA-1 depends on how you're using it. The vulnerability is what's known as a collision vulnerability: an attacker has the ability to create two input strings with the same SHA-1 hash with less ...

3

A random 128 bit value has a tiny ($2^{-85}$) probability of being a perfect cube, and so that doesn't look like a viable approach. And, you can't control the output of MD5, and so it'll give you effectively random values. A better way may be to collect a large number of signatures (with their messages); that is, $S_i = M_i^3 \bmod N$ values (where $M_i$ ...

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