Hot answers tagged

23

Curve25519 was designed to take advantage of the Montgomery ladder, which combined with Montgomery curves forgoes the $Y$ coordinates, is side-channel resistant, and enables public keys to be any 255-bit string. The ladder looks something like this (pseudocode): Q[0] = P; Q[1] = 2*P; for(int i = log2(exponent) - 2; i >= 0; --i) { Q[ bit(exponent, i)] ...


20

Well, cryptographers have been contemplating a post-quantum world for some time now. Quantum computing, although in its infancy as far as real-life computers go, has been studied in a theoretical sense for a quite a while. Shor's algorithm was published 19 years ago; Grover's, 17 years ago. These are the two most-famous quantum algorithms, I think, but the ...


14

Both of the other answers tackle the question of encryption in a particular format, but I would argue that neither of them is necessarily a good fit for your use case. You want to be able to generate 20 character codes that a server will be able to verify. A symmetric MAC is sufficient for this use case, if you don't need the codes to contain any secret ...


14

A simple way to imagine the effect of the hash function is a truncation. A "good" hash function ought to behave like a random oracle. If your source has entropy $s$ bits, then this means that the source somehow assumes $2^s$ possible values. When processed with a random oracle with an $n$-bit output, you force the $2^s$ input values into $2^n$ possible ...


14

The main difference is that secp256k1 is a Koblitz curve, while secp256r1 is not. Koblitz curves are known to be a few bits weaker than other curves, but since we are talking about 256-bit curves, neither is broken in "5-10 years" unless there's a breakthrough. The other difference is how the parameters have been chosen. In secp256r1 they are supposedly ...


12

I have a list of Bitcoin-related publications here: Bitcoin Bibliography (Crypto & Security) They are all the academic papers (as opposed to whitepapers) that I know about, relating to security or cryptographic aspects (as opposed to economic or implementation aspects) of Bitcoin. Most are published.


12

I restrict to hash functions $H$ with an output of some fixed size $n\ge1$ bit(s), accepting as input some strings, including all $n$-bit strings; MD5 (resp. SHA-1, SHA-256) is an example of such function for $n=128$ (resp. $n=160$, $n=256$). Whether there exists a solution to $H(x)=x$ depends on the particular hash function. If $H$ is a random function (as ...


11

Here's the Research article on the Bitcoin wiki: http://en.bitcoin.it/wiki/Research You might find some of the authors in the list have related research that is not directly related to Bitcoin so is absent from that list.


11

Randomness is not a property of strings of bits (or characters of any sort). Rather it is a property of the process that generates those strings. However, it is convenient to conflate the string with the thing that produced the string, and thus to speak about strings being “random” or “not random”. The string 00000, for example, is random if it was the ...


11

What choice did they have? F1 is a bitwise function with three inputs and one output. There are $2^8 = 256$ such functions. Only 70 of them are "unbiased" (i.e. have as many 0 and 1 outputs in their image). If you further require that each input, as well as the order of inputs, matters for the output, you are left with only 36. However, those 36 are all ...


11

The first part of this partial self-answer uses additional information I received from Professor Simon R. Blackburn, one of the author of the recent attack. The method used to generate parameters is not public, e.g. for the matrix $m\in GL(n,\mathbb F)$ which careful choice was acknowledged critical to defeat an earlier version of the attack. The authors of ...


9

Here is how you do a literature search, to find relevant research papers in the literature: You identify some search terms related to your topic, and search for them on Google Scholar and other places (e.g., Crypto.SE, via web search, on Citeseer). (For cryptographic work, also try searching Google with site:eprint.iacr.org and your search terms, to turn ...


9

No, because even SHA-512 was considered overkill from a security perspective. It has 256-bit collision resistance, which is unbreakable. (The link is about keys but a similar argument applies.) If you think large quantum computers will be efficient, a 512-bit hash makes some sense, but even then a 1024-bit one wouldn't. A quantum computer requires ...


9

Pure Threefish has received less attention than Skein. Shortly speaking, it has a large security margin, and can be safely used for encryption. In more details, Threefish has been tweaked twice. The first two versions were vulnerable to rotational cryptanalysis in weak models (related-key attacks or distinguishers) up to 57 rounds. All these attacks are ...


9

Full disclosure — I'm a Skein/Threefish co-author. Also, when I mention Skein/Threefish without any other qualification, I mean Skein/Threefish-512. The security proofs we did for Skein prove that if there's a weakness in Skein, it implies an underlying weakness in its components (Threefish or UBI). As Dmitry says above, Threefish is very strong, and there ...


8

In RSA as usually practiced (encryption or signature per PKCS#1, signature per X9.31, ISO/IEC 9796-2, FIPS 186), it is NOT necessary, or even common, to require $n=p⋅q$ with $p=2⋅p′+1$ and $q=2⋅q′+1$ with $p'$ and $q'$ huge primes, as stated in the question. IF that's done, it ensures that: any small odd $e>2$ (including the common $e=3$ and $e=65537$) ...


8

Uniformity is a tricky one. SHA-256 (as well as SHA-3 for that matter) follows a heuristic approach. That is, the design is not based on a hardness assumption (for example, the factoring or discrete-log assumption) but on criteria that have only been verified empirically. As such, also the study of uniformity is an empirical study. The development of ...


8

A video camera can obtain entropy, but only at a fairly low rate and only if allowed to see "unusual" scenes… like someone making funny faces, unusual movements, etc. Of course, this only works in a room with no video bugs. Theoretical explanations… Depending on your knowledge-range, the following sources may be able to explain ways webcams can be used ...


8

The idea of "safe curve" is somewhat overrated. What you really want is a safe implementation which won't leak secret information when employed in some practical context. Leakage may occur in a variety of ways; some examples include timing attacks and implementation behaviour when encountering anomalous input. This is not an exhaustive list, and, depending ...


8

Informally, a signature scheme with message recovery is one where some or all of the message is embedded in the signature, allowing to conserve bandwidth when transmitting a signed message, compared to a signature scheme with appendix. Total message recovery A signature scheme with total message recovery [some sources make total implicit, e.g. the HAC ...


8

I would like to ask if that is true for every AES CTR mode implementation?, Doesn't have to be. You can store the nonce anywhere. You could even send it to the recipient via a different channel (e.g., email the ciphertext and use SMS to transmit the nonce). Storing it at the beginning has its advantages. For example, if streaming the data, you can ...


7

Vanilla textbook RSA does not include "padding and stuff", the term "textbook RSA" generally refers to simply encoding a plaintext message as an integer and raising it to an exponent. Implementing this is pretty easy, just follow the steps outlined on Wikipedia. You can easily translate those steps into some given programming language. Based on the rest of ...


7

What you are asking is a straight application for Format Preserving Encryption, which builds ciphers which input and output are in a constrained format (generically: common to input and output, hence preserved). The FPE field has many articles with proven techniques; and proposed standards, including BPS and SP800-38G Draft. Specifically, it looks like ...


7

Even though Dobbertin could not provide a real collision of MD5, I would say that Hans Dobbertin first publicly described MD5 collision(s) in "The Status of MD5 After a Recent Attack" (PDF) – that was in 1996. To the best of my knowledge he was one of the first who recommended to no longer use MD5 when collision-resistance is needed/expected/required. On ...


7

Safe primes (that are two times a prime plus one) and strong primes were at some point in time considered sensible. One reason was that safe primes ensures that Pollard's $p-1$ factoring algorithm stops working. However, safe primes are not enough. There are other related factoring algorithms, such as the $p+1$ method, and strong primes also stop them. The ...


7

Did you take a look at DjB's paper? One of his design criterias in order to improve performance is "Use a fixed position for the leading 1 in the secret key". The set of secret keys is defined to be $\{\underline{n} : n \in 2^{254} + 8\{0, 1, 2, 3,\ldots, 2^{251}-1\}\}$.


7

It's called a keyword cipher. See this question for some ways to break it.


7

Yes, they are (deterministically) equivalent. The original RSA paper (Section IX.C), working off Miller's results (Theorem 3), showed how knowing the secret exponent $d$ was probabilistically equivalent to factoring $n$. Later, using more advanced techniques, Coron and May showed how to deterministically reduce finding $d$ to factoring $n$.


7

For any $x,y$ represented by $\{0, 1\}$, $x \lor y = 1 - (1-x)(1-y)$. It follows, any one-multiplication homomorphic scheme would do. It also follows, just additively homomorphic scheme would be not enough.


7

The standard answer to this question is format-preserving encryption (FPE). FPE is a class of techniques that allow you to encrypt data while preserving some of its format (which can include its length). In terms of security, most FPE schemes are deterministic, which means they do not achieve the standard IND-CPA notion of security. However, for ...



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