Tag Info

Hot answers tagged

5

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


5

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


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

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

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

Yes, the ECDSA key size as indicated by the -b argument is linked to the hash algorithm used. This is defined in section 6.2.1 of the RFC 5656: The Elliptic Curve Digital Signature Algorithm (ECDSA) is specified for use with the SSH ECC public key algorithm. The hashing algorithm defined by this family of method names is the SHA2 family of ...


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

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

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

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

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

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


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


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

This is the algorithm from your other question Lamport-Diffie + Security Proof , I guess. What happens here is this: We create a special public and secret key for a LD-Sign Scheme: We choose $x_{i,b}$ randomly for all but one single entry (which is $x_{i^*,b^*}$) and this is our secret key. In the public key we just apply $f(x)$ to all randomly chosen ...


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

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.


2

For any signature scheme, we can remove a few bits of the signature, say $k$, and define a verification scheme that accepts the signature if any of the possible $2^k$ original signatures matching the truncated signature is acceptable. The risk of forgery is increased by at most $2^k$ but might remain acceptable. The work to verify the signature is increased ...


2

In the blind RSA signature scheme the blinding of a message $m$ (to be blindly signed) is multiplicative with value $r^e$, where you ensure that $r$ is invertible modulo $N$. So if the sender receives the signed blinded message back from the signer, he can unblind by multiplying with $r^{-1}$, yielding $s\equiv m^d \pmod N$ which is a valid (textbook) RSA ...


2

The answer is "any sane summarization function is about as good as any other; pick whichever is convenient" To the best of our knowledge, SHA-256 acts pretty much like a random function (except for the length extension attack; that wouldn't apply here) So, the output of SHA-256 is essentially a random 256 bit number; so, if we have a 128 bit hash function: ...


2

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


2

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.


2

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.


2

As both of us recently learned, the public key signature hash algorithm is negotiated completely separately from the MAC algorithm. DSA and RSA use SHA-1, ECDSA uses SHA-2, and Ed25519 uses, um, Ed25519. I'm skeptical that SSH crypto performance will be a serious issue for you. I suspect you would have to be transferring a lot of data on a really bad CPU ...


2

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


2

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


2

I guess they would need to go to my website, find the document and check whether the signed code is the same as the document they want to check. If you assume people are able to trust your website, you could simply list the SHA-256 (for example) hashes of your documents on your website. Perhaps include an URL in the signed document pointing to a ...


2

One of the main reasons for hashing is that hashing destroys any algebraic structure that is hidden in the signatures. If you don't hash, then in most signature schemes the messages will satisfy some algebraic relation. A typical example is that $$Sign(m_1m_2)=P(Sign(m_1),Sign(m_2))$$ meaning that the signature of a product/concatenation/whatever of two ...


1

Here's something similar but completely different... A 'one-way' cryptographic hash function which is regressible when combined with the function's parsed trapdoor index. That is to say, the hash function is the file and the trapdoor table file is the key! The trapdoor table generated is approximately 60% larger than the original file but eminently ...



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