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


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


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

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-9=119 bits of ...


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


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


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


1

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


1

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


1

Ed25519 or more general the EdDSA (Edwards-curve Digital Signature Algorithm) approach can be considered as a variant of ElGamal signatures (such as Schnorr or DSA). They all are signatures following the hash-then-sign approach. This simply means that you can sign arbitrary length messages by hashing them to a constant size string using a secure ...


1

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


1

The main difference is that the salt is not assumed unknown to the attacker, but the key is. An additional difference is that salts are supposed to vary; if you hash three passwords within the same system, then you should use three distinct salt values, whereas keys are reused. Another way of seeing salts is to consider that you do not have one hash ...



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