Hot answers tagged

31

This question is quite broad by specifying a sudden fall to cryptanalysis and therefore my answer might not be as complete as you wish it to be. If by "become practically attackable, or close enough that use is strongly discouraged" you imply not an academic breach but assume a weaker attacker such as a single ciphertext attack, then there are quite a few ...


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


13

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


12

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

This is true of any group of prime order, over elliptic curves or not. This is due to Lagrange's Theorem which states that the order of a subgroup $H$ of group $G$ divides the order of $G$. Since orders are elements of the ring of integers and since this is a principal ideal domain, unique factorization exists and primes make sense. Or put another way, ...


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

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


7

Yes. There is an $\Omega(\log n)$ lower bound on ORAM. Therefore directly using ORAM to transform a non-oblivious algorithm to oblivious algorithm would incur a logN overhead. It is an open problem to design an ORAM matching the lower bound. No. There exists algorithms that do not have more efficient solution. As an apparent example, accessing a memory cell ...


6

In the first part of this answer, I consider the problem of decryption using leaked keys of a protocol not intended for that, which was my original reading of the question. I'll ignore that dominant industry practice is to use random symmetric session keys, leaving little opportunity to "hold a couple of secret keys" without knowing to what session they ...


6

As otus suggests in the comments, it's better to first calculate the frequency of each letter in the decrypted message, and then compare the frequency distribution to what would be expected for English text. For the comparison, you can use chi-squared ($\chi^2$) testing. (Actually, for just comparing the likelihoods of different decryptions, you don't even ...


6

A symmetric cipher design contest was started in Ukraine around 2006, and this cipher (in Ukrainian and Russian: Мухомор) was there. For specifications, look for "Applied Radioelectronics" journal "Прикладная радиоэлектроника", 2007, No 2. http://anpre.org.ua/?q=pre_2007_2 http://dspace.nbuv.gov.ua/bitstream/handle/123456789/61794/06-Dolgov.pdf


6

You may find it useful to play around with a toy example, such as the integers modulo a Fermat prime, like $p = 257$. Since $g$ is a generator of the Group, $h \equiv g^x$ for some unknown exponent $x$. In other words, $\log_gh = x$, and for Groups of order $2^k$, this discrete log is easily computed like so: Interpret $x$ as a $k$ bit number, i.e. $x = ...


6

Much of what NIST publishes about cryptographic algorithms is in Special Publications. In this case it is SP 800-131 (pdf) where they describe transitioning away from old algorithms and key sizes. Pages 14-15 have the hash function specific information: SHA-1 for digital signature generation:      SHA-1 may only be used for ...


5

The first publication of an MD5 collision was on 17-Aug-2004 17:44 UTC on the eprint archive server: Xiaoyun Wang, Dengguo Feng, Xuejia Lai and Hongbo Yu, Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD (third version). The results where fresh: the authors had just corrected IV endianness, that they got reversed in two earlier versions. Like 8 ...


5

I don't understand why this is important, but just want to note that the collision was first presented at the rump session at CRYPTO 2004, and was then later published. The earliest time-stamp is an ePrint report by Xiaoyun Wang and Dengguo Feng and Xuejia Lai and Hongbo Yu, called Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD. The date is ...


5

It is not a standard mode of operation and I do not know if anyone uses it in practice, but one option is double encryption using counter mode and a non-repeating counter. That is, doing $E_{k_1}(i) \oplus E_{k_2}(i) \oplus p$. The sum of two PRPs is a PRF with better bounds than one. The bound is basically $O(2^{2n/3})$ rather than $O(2^{n/2})$. See The ...


5

You can do anything in MPC, as long as you can express it in a circuit. I assume that there is a known upper bound on $k$ (otherwise you can't even share it). In that case, all you need to do is to take enough randomness (security parameter number of bits more than the upper bound) and then compute the sum of the randomness held by each party modulo $k$ (...


5

If $H(x) = x$, $x$ is a fixed point. If for a value the output of the function is the same as the input, it is called a fixed point. A length extension attack is unrelated to the concept of fixed points. There is a good question about understanding length extension attacks here.


5

PGP key formats are defined in RFC 4880. Specifically, section 5.5. The private key format includes the public key and quite a bit of other information in unencrypted form. It might be easier to add another layer of encryption on top of that before you use steganography.


4

The source of that quote is: Hellman, M. E. (2002). An overview of public key cryptography. IEEE Communications Magazine, 40(5), 42-49. That paper is currently available here: http://www.lkn.fe.uni-lj.si/gradiva/kk/IEEE%20%C4%8Dlanki/IEEE%20Hellman%20An%20Overview%20of%20Public%20Key%20Cryptography%20-reprint.pdf Here's the complete quote: The system ...


4

I'm sorry, but I don't believe that there are any known 'one way permutations' for small inputs (that stay one way if you know the 'key'). When we create a cryptographic permutation (or bijection; that's what we call a 'full cycle' function), we have two basic ways to do it: We can take a series of easy to invert permutations ("round functions"), and glue ...


4

The point why a simulation must not deviate too much from the real game is due to the following reasoning. You assume you have an adversary that wins the original game, but you do not know how the adversary acts if you deviate from the behaviour of the real game and the adversary can notice this. Exactly because you make no assumption whatsoever about the ...


4

Standards for Efficient Cryptography Group has published SEC1: Elliptic Curve Cryptography (pdf) about elliptic curve algorithms. If it does not explain the mathematics well enough for your purposes, there is also Fundamental Elliptic Curve Cryptography Algorithms (RFC 6090, from IETF) you could look at. There are a lot of issues you can run into, so ...


4

As of now I can think of four different applications for XOFs. Note that some change the padding depending on the requested output size and so the outputs are truly unrelated, Skein does this. Signature message hashing. Using an XOF you don't have to rely on ad-hoc constructions for hashing the message in signature schemes to the appropriate size. For ...


4

I'm happy to have a crack at this one, providing I've understood your question correctly. Firstly I wouldn't say the cipher possibly exhibits low level bias at any point. It experiences plenty of bias and I'll attempt to explain how we can use it to launch practical attacks. As I'd imagine you know, the strongest bias is found right at the start of the KSA, ...


4

The way in which it follows that "any one-multiplication homomorphic scheme would do" is false = 1 ​ and ​ true = 0 . Similarly, schemes that can do more multiplications can in that way be used for correspondingly many more OR operations. If a 1/n probability of false negatives is acceptable, then a ​ $($$\mathbb{Z}/n\mathbb{Z}$$,\hspace{-0.05 in}+)$-...


4

To be very concrete: you can use the BGN crypto system that allows addition and a single multiplication. Alternatively, you can use this scheme by Gentry-Halevi-Vaikunathan based on LWE that also allows a single multiplication.


4

You can use any library you like, as long as it is has been tested for the specific algorithm. In other words, if $G^x$ is implemented in a specific library you must make sure that there are unit tests and if it is used in a verified algorithm. There are some hints you can take from the library to see if it was programmed well: the code should point to ...



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