# Tag Info

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

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

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

4

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 ... 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 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. ... 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 ... 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 ... 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 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 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 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 ... 3 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 ... 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 ... 3 If you use a one-time pad as your encryption function then this simplifies to a proof that Alice knows some F that hashes to H. K can be trivially derived from F and E(K, F) by xor-ing. An interactive zero-knowledge proof of this simpler problem - Alice proving she knows a pre-image of H(F) - would go something like this: You need to use a ... 3 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 ... 2 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 ... 2 The security of the LD scheme can be reduced to the one-wayness (aka preimage resistance) of the used hash function. The reduction is quite easy: Assume you want to invert the one-way function f for image y=f(x), given a forger for LD-OTS. Then you generate a valid LD key pair using f, sample a random position i in the key pair and a bit b and ... 2 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 ...

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