Finding key of AES in ECB mode How many plaintext-ciphertext pairs would be needed to guess with probability, say $p=0.5$, the key $k$ of AES under ECB mode?

Most of the articles that I found tried attacks on single plaintext-ciphertext pair. How would the chances on attack on key increase with increase in number of plaintext-ciphertext pairs.

Link to document or discussion thread about various attacks would be highly appreciated.

As CodesInChaos notes in the comments, having more ciphertext–plaintext pairs doesn't help with brute force guessing attacks.

Well, that is, except for the minor issue of unicity.  Basically, to narrow the results of your brute force attack down to a single key, you do need to have enough ciphertext–plaintext pairs that the length of the known plaintext exceeds the length of the key (by some reasonable amount — but one extra cipher block is more than enough).

For example, if you were trying to break AES-256 using just one block (i.e. 128 bits) of known plaintext (and somehow had a magic supercomputer that could actually test 2256 keys by brute force), you'd end up with about 2128 false positives — wrong keys that produce the correct ciphertext for the known plaintext block just by chance — in addition to the correct key.  Testing a second ciphertext–plaintext block pair would narrow that down to just one false positive (on average; you might get none, or you might get two or even more if you're unlucky), and a third pair would almost certainly (with probability about 1 − 1/2128) eliminate the false positives completely.

So you do need at least two, and preferably three, blocks of ciphertext–plaintext pairs to uniquely determine the correct key for AES-256.  For AES-128, one block may be enough if you're lucky, but you preferably want two.

All that said, having even more ciphertext–plaintext pairs than that won't help with brute force attacks — once you've got enough to uniquely identify the correct key, any more is useless.

Having more known plaintext does typically help with cryptanalytic attacks.  For example, the biclique attacks of Bogdanov, Khovratovich and Rechberger can, given 256 ciphertext–plaintext pairs, speed up AES key recovery by a factor of about four (4 = 22) compared to simple brute force.  Obviously, this is still a completely infeasible attack in practice, but it does mean that, technically, having more ciphertext–plaintext pairs does make AES key recovery faster.  (Well, that is, except for the fact that the extra complexity of the biclique attack would almost surely slow it down by far more than the factor of 4 that it theoretically gains over plain brute force, were anyone to try to actually implement it.  But in principle it works...)

Similarly, the related-key attack by Biryukov and Khovratovich requires about 299.5 ciphertext–plaintext pairs, encrypted under distinct keys satisfying a specific relationship, to recover the actual keys for AES-256.  This is still not a practical attack, and using properly chosen keys (generated randomly or using a secure KDF) defeats it completely, but it is technically an example of a situation where having more (suitably chosen) ciphertext–plaintext pairs helps to recover the key.

In any case, the reason why you should not use ECB mode has nothing to do with key-recovery attacks.  (In fact, ECB is generally no worse than any other mode of operation in this respect.)  Rather, the reason ECB mode is insecure is simply that it leaks which plaintext blocks are identical, and thus isn't semantically secure.


Probability of Fermat test going wrong How can I proof that in Fermat's primality test the probability of going wrong after k iterations is $\big(\frac{\phi(n)}{n-1}\big)^{k}$?

I give an answer summarizing and precising the comments you provided.

  Being invertible in $\mathbb{Z}_{n }$ is equivalent to having some power equal to 1.

If $b$ is invertible there exist $b^{-1}$ and as we are working in finite groups in the sequence $1,b,b^2,...,b^n$ there must be repetitions, let's say $b^i = b^j$. Then using the existence of $b^{-1}$ we have that (assume $i > j$) $b^{i-j} = 1$ so for power $i-j$ we have 1 modulo n.

If we have some power that is equal to one, say $b^x$ then we can take $b^{-1} = b^{x-1}$

Now, in Fermat's test we pick $b$ in $\{1,\cdots,n-1\}$ and going wrong means that in fact $b^{n-1} = 1$ so that $b$ must be invertible. Therefore, the total number or wrongs $W$ must be bounded by $\phi(n)$. The probability of going wrong in k attempts is therefore $\big(\frac{W}{n-1}\big)^k \le \big(\frac{\phi(n)}{n-1} \big)^k$ assuming independence.

As fgrieu pointed out this is only an upper bound which is an equality if number $n$ has the particularity that every invertible $b$ verifies $b^{n-1} = 1$ so that $W =  \phi(n)$. These funny numbers are Carmichael numbers.


Which crypto libraries/programs do we have the most confidence in? I have recently begun studying crypto. If it's one thing I have learned it's that we should not implement our own crypto. Therefore we should look to using existing software and libraries.

When I go to implement something that needs data security, there are many options -- openssl, mcrypt, truecrypt, crypt, pycrypto, bouncycastle... how do I know what is "tried and true" with regard to crypto community scrutiny?
This probably depends on the application, your implementation language, and the data under encryption. What would be generic answers for common scenarios such as basic single-file encryption, full disk encryption, and encrypted network communication?

I could do an audit of source code myself, but I would be naive to say that I could catch even some obvious vulnerabilities.
If TrueCrypt, a high profile piece of crypto software itself, is having widespread calls for a public audit, then what crypto software IS sufficiently audited? It seems to me that if any crypto software should have high confidence with many eyes scrutinizing it, it would be truecrypt or openssl.

And of course, the usual disclaimer; I understand that we can't know all vulnerabilities and bugs ahead of time. And nothing can be infinitely secure. That leaves us with simply a high confidence or low confidence measurement of worth.
Is there a list of high-confidence crypto libraries/software? Maybe confidence isn't well-defined. Is there a list of time-tested crypto libraries/software?

The question is subjective in nature, and this comment is also subjective. It was too long to leave as an actual comment so I'm posting it as an answer, although it isn't really an answer, it's a comment. This is for posterity, I guess -- this thread is already high in Google searches.

NaCl is probably the most widely respected library. It's authored by someone (Daniel J. Bernstein) with an established track record writing secure software and who understands a lot of practical and theoretical subtle security issues. It's also aimed at high-level use and encapsulates details when possible, as opposed to the more common library approach of just providing an open-ended generic API for a lot of cryptographic primitives. That makes NaCl harder to misuse, which is important since some vulnerabilities are simple innocent misuses of libraries. Few other libraries can make similar claims.

I think good audits are hard to come by. My general impression is that very few people are qualified to perform a good audit, and many of those who are qualified are only qualified to evaluate a few areas. What's more, the well-qualified are in high demand with other things and probably have minimal interest in taking the initiative on an auditing project. It isn't lucrative because a good audit:

takes a long time
is unlikely to pay much (probably nothing unless bug bounties or grants are involved)
unlikely to bring fame to the auditor unless they find something huge
is potentially a liability to the auditor if they miss something that is discovered later

So I don't think there's much incentive to drive high-quality audits.

Popular libraries/applications have had bugs sit unnoticed for a long time, which I think is evidence that audits are rare. History shows examples of bugs going unnoticed for a long time, sometimes even if when we know of them.

The Debian weak keys bug existed for over a year and a half before it was caught. The developer who made the mistake had even explicitly described his change on a public mailing list and asked if the change was secure (the question went unanswered). Let that sink in: A popular open-source library was used for 21 months with a somewhat obvious fatal mistake that was described on a public mailing list.
Look at the list of OpenSSL vulnerabilities (you can filter the more important ones) and use the release dates to match the earliest fixed version against the oldest known vulnerable version. The percentage that existed for 2 or more years before being discovered and fixed is impressive, several lived for over 4 years. Bugs are hard to find and often long-lived.
This isn't library-specific, but I think the lesson holds: The BEAST attack against TLS 1.0 exploited a theoretical vulnerability that had been published 9 years earlier (and fixed in the practically unused TLS 1.1). Even when we know of vulnerabilities, we sometimes don't fix them if it's inconvenient and the attack doesn't seem practical.

I picked on OpenSSL a bit there because it's very popular, open-source, and documented, which made it easy. (Worth noting that the source code is a mess, which probably doesn't encourage anyone to read it.) Other libraries have some similar patterns, and less popular projects may have misleading vulnerability lists because OpenSSL's vulnerabilities are popular when they show up and likely to get a CVE. Is a contributor for a less-popular project going to report every bug they fix, evaluate it as a potential vulnerability, and then file a CVE? I don't know.

In contrast, Truecrypt doesn't have a published list of vulnerabilities, and who knows what subtle fixes are going unreported (or reported under opaque names like "security fix #XYZ") in closed source libraries like Microsoft's. How can we get even a high-level assessment of their vulnerability histories?

My personal feel is that good audits are very hard, very rare, and the majority of auditing is done by the maintainers themselves. To me, the trustworthiness of a library is more centered around who maintains it than how popular (and supposedly more "eyeballed") it is.

Again, this is my general impression and is a subjective response that doesn't fully answer a subjective question.


Is this hand cipher any more secure than the Vigenère cipher? I know that inventing one's one crypto always sucks, but the problem is that hand ciphers are usually

very insecure
very slow.

This is an attempt to make a relatively secure, keyable, and modular multi-round cipher by hand.

In each round of encryption the following two steps are done:

The text is permuted by concatenating the reverse of the even-numbered characters to the odd-numbered characters. This is equivalent to writing the first char in the first place, the second in the last place, the third in the second place, the fourth in the second-to-last place, etc and is very fast to do by hand, and can be mentally reversed simply by "zig-zagging" the eyes when reading. (12345 -> 13542)

   T H I S X I S X S E C R E T
=> T I X S S C E T R E X I S H

The text is then added$\mod 26$ by repeating a series of numbers, i.e. the key. The numbers are from 0 to 10 so that they are easy to write underneath the letters and also because encryption can be done in head without memorizing, say, X is the 24th number of the alphabet. I'm especially concerned whether limiting this to numbers from 0 to 10 rather than from 0 to 25 seriously cripples security. (Obviously the digits of $\pi$ is a bad choice for a key but this is just an example)

   T I X S S C E T R E X I S H
   3 1 4 1 5 9 2 6 5 3 5 8 9 7
=> W J A T X J G Z W H C Q B O

This encryption process is continued for 5 to 10 rounds. The reason for the permutation phase is to break patterns that weaken the Vignère cipher.

I have observed the weakness that the first letter is never permuted to another place; thus known-plaintext attacks can easily trivially find the first number of the keystream given the number of rounds. Other than that I haven't found any very serious flaws.

Does this cipher system have any mathematical advantage over older (but slower to compute!) ones such as Vigenère or Playfair?

Given that the permutation is fixed and the key step is independent of the permutation you can reduce this to an ordinary text-substitution cipher.

If the key is as long as the input you have a weak one-time pad, because the per letter change is limited to 10 instead of 26.

However if the key is short then you have a Vigenère cipher (if you "decode" with $key=0$ then it is exactly a Vigenère cipher).

In essence you use 2 transformations: a character scramble ($P$  $P'$) and a "xor" ($X+$ and $X-$).

Your algorithm is $text1=X+(P(text_0),key)$for each phase.

However this is equivalent to $text1= P(X+(text_0,P'(key)))$.

Then the next fase is $text_2= P(X+(P(X+(text_0,P'(key))),P'(key)))$ which can be rewritten to $text2 = P(P(X+(X+(text0,P'(key) ), P'(P'(key))))$ and so on.

Given that P is easily reversible you can extract $X+(text, X+(P'(key), P'(P'(key)) )$.


Static salt for PBKDF2, but unique salt for HKDF? Hypothetical. Lets say you have an application where you generate a master key from a user password using PBKDF2 (static salt) and then use the master key to derive two passwords keys for an encrypt-then-mac scheme using HKDF (unique salt per encryption).
The password would be shared by two individuals, who would then potentially share many messages. Each message would share the same master key, but would have unique encryption and MAC keys. Does this make sense, or is the unique salts in HKDF unnecessary?

Yes, the salt in the HKDF can provide for key separation between the encrypt-then-mac applications. If that's needed depends on the system, maybe using an IV/nonce is enough, it depends on how many messages you want to encrypt and the used encryption and MAC scheme basically.
Some other remarks:

we derive keys - not passwords - for ciphers and MAC algorithms;
using an authenticated cipher such as GCM mode instead of encrypt-then-mac would be wise, in that case you only need to derive one key;
you'd use a static salt with PBKDF2 to derive the same master key, it's probably best to only use a static salt if you need to reuse the key (which of course assumes that you also use the same password);
you may want to additionally use a separate KDF invocation to derive a "key check value" stored with the ciphertext to check that you've derived the correct master key (instead of having to rely on authentication tag failures).


Composing and Inverting Symmetric Encryption Keys Using a symmetric encryption algorithm $E$ on a message $M$, users usually send $E(M)$ to the recipient and then the recipient will compute $E^{-1}(E(M))=M$ to retrieve the message. For what symmetric encryption algorithms would it be equally secure to instead send $E^{-1}(M)$ and have the recipient compute $E(E^{-1}(M))=M$?

Suppose we have two symmetric keys $K$ and $L$ to encrypt $M$. We could compute $K(L(M))=M'$. Is there any secure encryption algorithms such that from $K$ and $L$, we can compute a new key $KL$ where $KL(M)=K(L(M))$?

I know XOR has both of the above properties if used on just one block. But my question is: does there exist any secure symmetric algorithms that have both properties and can be used for multiple blocks?

As block ciphers are invertible, and since XOR is too - the main operation on the key stream for many stream ciphers - the resulting encryption/decryption modes of operation are often invertible. For stream ciphers that create a key stream that is XOR'ed with the plaintext, it is even true that $E = E^{-1}$.

Some block cipher modes of operation however require padding. If padding is included in $E$ then then you cannot perform $E^{-1}(M)$, because the padding would likely fail or result in a wrongly sized plaintext.

ECB mode is invertible, but requires padding
CBC mode is invertible, but requires padding
CFB, OFB and CTR modes generate a key stream are therefore invertible, they do not require padding

Any authenticated cipher is of course not invertible as $E$ would include creation of the authentication tag, (and $E^{-1}$ includes the verification of an authentication tag that isn't there).

Usually a (block) cipher has the same security for $E$ as for $E^{-1}$. It would however be advisable to use the cipher as intended, or verify (somehow) that the security conditions hold.

As for the keys, that's an entirely different question. If you have two (possibly identical) encryption functions $E_1$ and $E_2$ then you could create an encryption function $E_3(K_3, M) = E_2(K_2, E_1(K_1, M))$ that uses the $K_3 = K_1 | K_2$ as key. I don't see why you couldn't combine that with the previous approach.

Obviously such a construction is not safe by definition; if $E_2 = E_1^{-1}$ and $K_2 = K_1$ then you would have created the identity function. The identity function is not secure. You should also know about meet-in-the-middle attacks. You may want to study the multiple ways that DES can be - and has been - combined in this regard.


What is the security model of the FHE system introduced in Fully Homomorphic Encryption Using Ideal Lattices? How would one construct a security model to play against the adversary, and define the security of the overall scheme? This is in reference to the scheme introduced in "Fully Homomorphic Encryption Over Ideal Lattices".

Usually, the FHE schemes are proved to be CPA secure, therefore, the game is similar to the IND-CPA game, with the caveat that the attacker also hold a evaluation key (generally necessary to perform the homomorphic operations). Note that the evaluation key is public anyway, therefore it could just be considered as a part of the public key so that the game would be the same (this is done, for example, in the proof of security of BGV).

If there is some type of circular assumption (which is normally the case), then, you suppose that the evaluation key depends on the private key. However, this does not change the game.

Thus, the game would be more or less like this:

Parameters are set, keys are generated and the adversary receives the public and the evaluation keys.
The adversary can encrypt messages and compute over the ciphertexts freely.
The adversary sends two messages $m_0$ and $m_1$ to the challenger and receive a ciphertext $c_b$ corresponding to $m_b$ (for a random $b$).
The adversary can again encrypt and perform other computations.
The adversary outputs a bit $b'$.

Side note:

As noted by @Maeher in the comments, we have to be careful when talking about CCA security and homomorphic encryption. It is already known that homomorphic encryption schemes cannot be CCA2 secure, thus, in your model, the best you could do to prove CCA security would be to use a game for IND-CCA1 security, as it is done, for instance, on this article (although they are dealing with Somewhat Homomorphic Encryption instead of FHE).


What is "blinding" with cryptographic hash functions? What is blinding with a SHA256() or similar cryptographic hash function?
What applications does it have?
An answer to a recent question briefly mentioned "Consider blinding before calling an external function [such as] SHA256()".
( https://security.stackexchange.com/questions/246209/is-it-safe-to-publish-the-password-hashes-from-my-sha256-md5-custom-password-h/246275#246275 )
The Wikipedia article "blinding (cryptography)"
currently mentions several different types of blinding, including asymmetric encryption, asymmetric digital signatures, and the one-time pad (a kind of symmetric encryption), but never mentions hash functions.
Most applications in that article involved tweaking the plaintext slightly, then running the tweaked plaintext through some (untrusted) function to get some intermediate output, then untweaking to get the final output, in such a way that we get the same final output without the tweaking and untweaking, but without handing over plaintext to the (untrusted) function. Does SHA256() support such tweaking and untweaking?
Whether or not it does, what is the proper approach to blinding with SHA256() or other cryptographic hash functions?

There are at least three possible senses of blinding in crypto in a context involving a hash such as SHA-256. In all cases, the purpose is to hide something (the value, or the true meaning) of some data element manipulated.

Blinding with the hash as a tool used as a black box. The exact meaning depends on the purpose. That can further subdivides into

we only to need to compare data elements for equality, so we can hash them, then compare the hashes
we use the hash output combined (e.g. by XOR) with a data element to mask.

Blinding within the implementation of SHA-256, to thwart attacks trying to find the input of the hash from some side channel, like electromagnetic emission.

Blinding the input of the hash. This is the sense in the linked text

Consider blinding before calling an external function.You're passing your password into the MD5() and SHA256() functions plain-text-style.  If either is backdoor'd, then they get your password.  Consider blinding.

Here the goal seems to be hiding the password from an attacker having hooked the MD5() or SHA256() APIs (that could also be: able to invert these functions with a rainbow table). I think the author is suggesting transforming the password before hashing. That could be XOR-ing it with a secret constant, or applying some rudimentary cipher with a fixed key. This is not crypto, but an attempt to make code harder to reverse-engineer, or attacks more specific, using security by obscurity.


Associative Multivariate Permutation Popular multivariate schemes are constructed by having a several easy-to-invert functions/maps as parivate key, and their composition as the public key.

When signing, the hash, or a padded form of which is converted to a series of multivariate variables, and its pre-image under the maps computed as signature. However, public-key encryption is not as easy to construct as signature schemes in multivariate cryptography right now.

I'm wondering if it's possible to do the following:

For signature:

Generate a random public multivariate system $g()$,
Generate a random private multivariate system $f()$ as private key, and publish $p = g \circ f$ as public key.
Publish $\sigma = f(h)$ where $h$ is the hash of the message signed, and verify $g(\sigma) = p(h)$.

For key exchange:

Generate a random public multivariate system $g()$,
Generate a random private multivariate system $f()$ as private key, and publish $p = f \circ g$ as public key.
Client generates a random $x$ and sends $y = g(x)$ as public component, and calculates $p(x)$ as the key exchanged.
Server calculates $f(y)$ as the key exchanged.

My questions are:

What are the known attacks that doesn't involving inverting the multivariate equations system?
Had there been similar proposals? And if not, possibly why?

A couple of papers by Faugère and Perret (and, in one case, von zur Gathen) provide efficient (i.e., polynomial time) algorithms to solve the Functional Decomposition Problem:

Given: a list of $u$ multivariate polynomials $H = (h_1, \ldots, h_u) \in (\mathbb{K}[x_1, \ldots, x_n])^u$ in $n$ variables over some field $\mathbb{K}$.
Task: find a non-trivial decomposition $(F,G)$ where $F = (f_1, \ldots, f_u) \in (\mathbb{K}[x_1, \ldots, x_n])^u$ and $G = (g_1, \ldots, g_n) \in (\mathbb{K}[x_1, \ldots, x_n])^n$ such that $H = F \circ G$.

There are various definitions of "non-trivial" designed to explicitly exclude pathological cases such as where $F$ or $G$ are the identity or linear transforms. Suffice to say that any cryptosystem claiming security based on the hardness of multivariate polynomial decomposition, such as your proposals, should convincingly argue why the algorithms of Faugère et al. do not apply.

Specifically, these algorithms enable the attacker to obtain $f$ from $p$ in your proposals, even without using $g$. This breaks the schemes without inverting anything because $f$ represents the secret key.

There was a similar proposal called 2R$^-$. It was the original motivation for Faugère and Perret to study the FDP, which lead to that scheme's demise.


How to require two keyholders to decrypt a document? I want to create a system to encrypt a document and store it with a 3rd party, but not have the 3rd party be able to decrypt it until some unspecified later date. It seems like the solution would be to split the key into two parts, given to two different trusted 3rd parties. Then when the date arrives those 3rd parties can come together to decrypt the document.

I realize that splitting a key effectively reduces the strength of the key in half for anyone who has half of the key.

Is splitting an AES key into two parts is an effective method of preventing either party from decrypting a document?
Is there a preferred method of splitting a key? Down the middle? Every other byte, etc.?
When splitting a key will one party have an advantage over the other party in a brute force attack? In other words, are certain parts of the key more important than others?

Splitting a key does not reduce the key strength at all. Simply generate two random 128-bit strings and give one to each party. Encrypt the data with the exclusive OR of the two random strings.

Each string alone gives no information whatsoever about the final key, assuming your random number generator is sound. No party has any advantage.


Is it possible that a signing algorithm produces no output? I am reading Vadim Lyubashevsky's paper on Lattice Signatures without Trapdoors and I came across a somehow counter-intuitive part where he defined an algorithm $\mathcal{A}$:

$y\leftarrow D_\sigma^m$, where $D_\sigma^m$ is the discrete Gaussian distribution centered at $0$ with standard deviation $\sigma$ on $\mathbb{Z}^m$.
$c$ is some hashed value
$z\leftarrow Sc+y$, where $S$ is the signing key.
output $(z,c)$ with some probability.

The pair $(z,c)$ is the potential signature and can only be output with the given probability in step $4$. He also mentioned that if nothing was output, the signer runs the signing algorithm again until some signature is outputted.

I just can't imagine an algorithm that doesn't give an output wherein the algorithm above, it seems that it will always produce a certain output. It also seems to violate the definition of an algorithm by Knuth. Am I missing something here?

Thanks!

I just can't imagine an algorithm that doesn't give an output wherein the algorithm above, it seems that it will always produce a certain output.

Actually, step 1 is randomized; that is, it will select a value of $r$ randomly (from some probability distribution).  If step 4 decides to rerun the procedure, then step 1 will likely generate some different value, and so the output would be different.

  It also seems to violate the definition of an algorithm by Knuth.

Well, by Knuth's definition, it's a "computational method" rather than "an algorithm".  I don't think, in this case, the distinction is important, as the algorithm will terminate with probability 1 (and terminate quickly with high probability).  I don't believe that Knuth had randomized procedures (like this one) in mind when he wrote his definitions...


How to calculate the bias of cryptographic hash output from biased input? Assume that I have a hardware entropy source.  Not a TRNG, but the source that might feed a TRNG's extraction algorithm.  This source produces independent bits with a not unreasonable bias of $60/40$.  So that's $p(1) = 0.6$ and $p(0) = 0.4$ and min. entropy would therefore be 0.737 bits/bit.

I then use a cryptographic hash function to extract entropy. Let's say I take groups of 320 bits from my entropy source and hash them with SHA1. What is the resulting bias in the long run output? Or how might this be calculated?

I'm hoping for a numeric answer or calculation rather than verbiage.

Let's call the output of your TNRG $X$—this is a random variable taking the values 0 and 1, with $\Pr[X = 0] = 0.4$ and $\Pr[X = 1] = 0.6$, so that $H_\infty[X] = -\log_2 0.6 \approx 0.737$ bits.  This induces the random variable $Y = \operatorname{SHA-256}(X)$, which has

\begin{align*}
  \Pr[Y = \operatorname{SHA-256}(0)] &= 0.4, \\
  \Pr[Y = \operatorname{SHA-256}(1)] &= 0.6.
\end{align*}

Since $\operatorname{SHA-256}(0) \ne \operatorname{SHA-256}(1)$, we clearly have $H_\infty[Y] = H_\infty[X]$.

What if we have a set of observations $\{X_i\}_i$, which are independent and identically distributed?  Then, e.g.,

\begin{align*}
  \Pr[X_0 = 0, X_1 = 0] &= 0.4^2 &&= 0.16, \\
  \Pr[X_0 = 0, X_1 = 1] &= 0.4 \times 0.6 &&= 0.24, \\
  \Pr[X_0 = 1, X_1 = 0] &= 0.6 \times 0.4 &&= 0.24, \\
  \Pr[X_0 = 1, X_1 = 1] &= 0.6^2 &&= 0.36.
\end{align*}

I leave computing the entropy of the tuple $(X_0, X_1)$ as an exercise for the reader.  What about $\operatorname{SHA-256}(X_0 \mathbin\Vert X_1)$?  Since SHA-256 has no collisions on $00$, $01$, $10$, $11$, once again the entropy is preserved.

In fact, the entropy is not preserved only if there is a collision in the possible inputs.  Obviously the entropy is at most 256 bits for the output of SHA-256 on a single input.  How many distinct outputs are there?  Nobody knows for SHA-256, but for a uniform random function $F\colon \{0,1\}^{256} \to \{0,1\}^{256}$, the expected fraction of distinct outputs is about half the total output space—specifically, $1 - e^{-1}$.  So you might estimate a maximum min-entropy of about 255 bits, in the best case of a perfectly uniform input.

However, you're not limited to feeding in 256 bits; you could feed in 512.  If you feed in $256 + k$ bits to a uniform random function 256-bit function, the expected fraction of distinct outputs is about $1 - e^{-2^k}$ which very rapidly approaches 1 as $k$ grows.  The min-entropy of $(X_0, X_1, \dots, X_{511})$ is obviously $-\log_2 0.6^{512} \approx 377 \gg 256$ bits.  While passing 512 bits through SHA-256 may not necessarily cover the entire 256-bit output space and may not attain the full possible entropy of 256 bits, it's probably a pretty safe bet that the entropy is close enough to 256 bits that the difference doesn't matter to you.  This is plenty to use as a key for a PRNG for cryptographic work.


Where in the FIPS documents is it stated that SHA-1 is not secure? SHA-1 has not been secure for a very long time, but I still can see
it here.
Where in the FIPS documents did it state that SHA-1 is not secure?

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 digital signature generation where specifically allowed by NIST protocol-specific guidance. For all other applications, SHA-1 shall not be used for digital signature generation.
SHA-1 for digital signature verification:
     For digital signature verification, SHA-1 is allowed for legacy-use.
SHA-1 for non-digital signature applications:
     For all other hash function applications, the use of SHA-1 is acceptable. The other applications include HMAC, Key Derivation Functions (KDFs), Random Bit Generation, and hash-only applications (e.g., hashing passwords and using SHA-1 to compute a checksum, such as the approved integrity technique specified in Section 4.6.1 of [FIPS 140]).

FIPS 140, being the document you linked in the question, points to this document for guidance.


Can quantum computers break quantum cryptography? I happened to learn that encryption by quantum cryptography would be impossible to break as it's state changes the instant of an eavesdropping event(by non-quantum systems) occurs. But I'm not sure if it's still held in the case of the eavesdropper using a quantum computer(not sure how that works either) as well. Couldn't find the answer on Google so felt the community could shed some light on this.

I happened to learn that encryption by quantum cryptography would be impossible to break as it's state changes the instant an eavesdropping event (by non-quantum systems) occurs.

Actually, the QKD system doesn't assume that the eavesdropper is nonquantum; he is allowed to attempt to generate an entangled state with the qubit being transmitted.  However, even the act of generating such an entangled state would alter the received bit (with a probability that is bounded away from zero), hence any such eavesdropper is detectable, even if the eavesdropper is allowed a quantum computer.

[Insert standard skepticism about whether QKD is a practical system, compared to the alternatives]


Is it possible to generate a hash function that produces similar output to SHA-256? Is it possible to create a hash function that generates a correlated to SHA-256 when given the same input?
In other words, given a fixed input X:
SHA-256(X)=A
SHA-256'(X)=B

where he outputs A and B are similar, or correlated.
I was thinking about remodeling a few parts of the SHA-256 function without changing the underlying construction too much. Can someone offer more insight or suggestions on whether it is possible to do this?

EDIT: I was thinking of creating a hash function with a *built-in "backdoor" that allows for preimage attacks. Sort of creating a breakable version of SHA-256.

I was thinking of creating a hash function that produces a similar/correlated output to SHA256, but with an in-built "backdoor" that allows for preimage attacks. Sort of creating a "breakable" version of SHA-256.

That is not possible for arbitrary sized messages and unkeyed hash functions.
Assume that you created a hash function such that $h(m) \approx SHA256(m)$. This similarity is not defined in the question, however, we can consider that it a permutation, or small edit distance, or correlated. Assume that the similarity can be found faster than pre-image attack of SHA256.
Now assume that $h()$ is a weak hash function that you can find pre-images easily. Now;

take $z = SHA256(m)$
use the similarity to find all possible candidates  ( from the premutation, small edit, correlation, or..) $$z_i \in \{ a\;|\; a \text{ similar to } z\}$$
find pre-images of each $z_i$; $$m_i = \operatorname{pre-image-h}(z_i)$$
check all $m_i$ on SHA256 to see that one of them is the pre-image $$ z \stackrel{?}{=} \operatorname{SHA256}(m_i). $$

That is the break of the pre-image of SHA256. Not expected!.


Best way to use a block Cipher as RNG I am using some block Ciphers (AES and Threefish in particular) as RNG for the purpose of parallel Monte Carlo simulations. For each key, simply encrypt a sequence of counters produce a random stream more than good enough for the specific purpose. I don't. need CSPRNG. The use of these ciphers are because good performance (<1 cpb in my implementstion) and easy to setup multiple streams in parallel environment.

For each thread, a new cipher with a new key is used. Each thread has a different key. For the purpose of my simulation, it is sufficent that the two streams of any two threads are statistically  independent. Now my questions is that what is better way to seed each thread.

The first i am considering is simply seeding each with a counter as key, so, thread 1 has key equal to 1, thread 2 has key 2. And so on

The second is to use a seemly random key. For example, Say the cipher in use is AES256, for thread 1, I encrypt value 1 (256bit integer) with a zero keyed Threefish256, and a "random" 256bit number as key for the AES256 cipher. And so on for each thread. Since Threefish as a cipher is also a bijection, there's no risk that two threads having the same keys, up to 2^256 threads, which is far more than enough.

Which of the two will be better?

Edit
I meant to post it as a comment to the answer, but it was too long.

The indistinguishability is the part I don't quite understand. In fact I have read that wiki article for a couple of times before posting this question. Please bare with me. If I understand correctly, the basic principle is that knowing the cipher text without the key, one cannot guess the plain text with any advantage. In other words, given two almost identical streams, or highly correlated streams, and knowing the key of one stream, does not give any advantage of guessing the key of the other. However, my problem is more or less the inverse of this. Does two different keys, either random or related, always produce two uncorrected stream? My intuition is yes, since there are 2^k keys while there are (2^n)! permutations of the period 2^n streams, where k is the bits of key and n is bits of block. Or another way is, is it always the case, that for two keys, k1 ≠ k2, the cipher streams will be apparently uncorrelated? I understand that for k1 = 1, k2 = 2, etc., it should be so, at least if the total number of keys are not too big. But I am not sure if it is so for any two k1 and k2 from the 2^n possible keys.

If we assume that your ciphers have the IND-CPA property (indistinguishability under chosen-plaintext attack) then both methods will be equally good.

However exact reproducability of the values can only be achieved by the first method.


Is Functional Encryption about Access Control over encrypted data alone? Informally, In functional encryption system , a decryption key allows a user to
learn a function of the encrypted data. But all i see is that the function acts as an access control over the data.

Can we have richer functions, say can a user add two cipher texts and get the result in plain text using decryption key ?

Are there any known forms of functional encryption schemes that allow anything else other than access control ?

Existing definitions for functional encryption don't support "combining" ciphertexts in the way that you suggest.

As far as doing more than just access control, two very recent papers (to appear next month at STOC 2013) achieve functional encryption for arbitrary functionalities:

Attribute-Based Encryption for Circuits by Gorbunov, Vaikuntanathan, Wee
Reusable Garbled Circuits and Succinct Functional Encryption by Goldwasser, Kalai, Popa, Vaikuntanathan & Zeldovich

Two caveats:

These are feasibility results only, and are not practical (one could probably argue that they cannot be both practical and support arbitrary functionalities)
They achieve slightly relaxed (but still natural & useful) security definitions for functional encryption, where either the number of keys or number of ciphertexts in the system is bounded (I don't remember the exact details).


prove PRG is secure assuming DDH holds Let $\Bbb{G}$ be a cyclic group of prime order $q$ generated by $g \in G$.

Let $G$ be a  PRG defined over $(\Bbb{Z}_q^2, \Bbb{G}^3)$ such that:

$G(a, b) = (g^{a}, g^{b}, g^{ab})$

How can I show that $G$ is a secure PRG assuming DDH (decisional Diffie-Hellman) holds in $G$?

After reading this, I'm confused to prove $G$ is secure:

  Importantly, the DDH assumption does not hold in the multiplicative group $\mathbb{Z}^*_p$, where $p$ is prime. This is because given $g^a$ and $g^b$, one can efficiently compute the [Legendre symbol] of $g^{ab}$, giving a successful method to distinguish $g^{ab}$ from a random group element

As Shan Chen said, the reduction is easy. Note if the DDH adversary gets $g^a,g^b,g^{ab}$ then it gets $g(a,b)$, and if it gets $g^a,g^b,g^{c}$, then he gets a uniformly random string.

Now for the second question. First for a prime number $p$, the order of $\mathbb{Z}^*_p$ is $p-1$. If $G$ is a (integer) cyclic group of prime order $q$, then you are not using $\mathbb{Z}^*_p$, but the order-$q$ subgroup of it ($q$ needs to be large which I assume here).

Why DDH is not hard in $\mathbb{Z}^*_p$? By Euler's criterion, in $\mathbb{Z}^*_p$ there are $\frac{(p - 1)}{2}$ quadratic residues and $\frac{(p − 1)}{2}$ non-residues. So in for a random $x \in \mathbb{Z}^*_p$, the probability of $x$ being a residue (non-residue) is exactly $\frac{1}{2}$. Legendre symbol for an element $x \in \mathbb{Z}^*_p$ can be calculated as:

$$
\Big(\frac{x}{p}\Big)= x^{\frac{p-1}{2}} \bmod p
$$

and the symbol tells whether $a$ is a residue or non-residue:
\begin{equation*}
\Big(\frac{x}{p}\Big) = \begin{cases}
1 &\text{if $x$ is a residue}\\
-1 &\text{if $x$ is a non-residue}
\end{cases}
\end{equation*}

Now given the DDH tuple $(g^a,g^b,g^c) \in (\mathbb{Z}_p^*)^3$, we can calculate the Legendre symbols of $g^a,g^b,g^{c}$. If either $\Big(\frac{g^a}{p}\Big)$ or $\Big(\frac{g^b}{p}\Big)$ is 1, then $Pr[\Big(\frac{g^{ab}}{p}\Big)=1] =1$.

The reason is that a residue $x$ is congruent to a perfect square. So that if $g^a$ is a residue, then it can be expressed as $g^a=h^2$. For $g^{ab}$, it can be rewritten as $(h^b)^2$, which is also a residue.

But for a random $c$ that $c\ne ab$, the probability of it being a residue is only $\frac{1}{2}$, which means we can distinguish $g^{ab}$ and $g^c$ easily.

If the DDH tuple $(g^a,g^b,g^c) \in G^3$, since $q$ divide $p-1$ and $p-1$ is even, $\frac{p-1}{2} = kq$ for some $k$, then $\Big(\frac{g^a}{p}\Big), \Big(\frac{g^b}{p}\Big),\Big(\frac{g^{ab}}{p}\Big), \Big(\frac{g^c}{p}\Big)$ are all 1 (because all elements in $G$ are of order $q$, thus the $q$-th power of all elements in $G$ congruent to 1).


Inverse public-key encryption I'm in the need of an inverse public-key encryption method where you encrypt with the private key and decrypt with the public key. In other words an asymetric encryption where you can't generate the encryption key from the decryption key. Does such encryption exist? If yes which, and which would be the fastest?

If nothing like that exists I would be glad if you helped me out with my situation:

I need to authenticate users logging in from my Java application in the way that the response from the server cannot be falsified and thus giving the user full access to the application. Using public key encryption was an obvious method, I would decrypt data received from the client to confirm the credentials. This won't work because if someone manages to decompile and get the private key from the code, they would be able to generate the public key, which would make them able to crack my application again.
So any ideas how I can get this secure?

What you are looking for is so called white-box cryptography. That said, you should definitely check if you can't get away with digital signatures. The reason is that white box cryptography is a special case of program obfuscation that is quite hard to achieve. Existing, practical schemes do not rely on hard problems but rather on not being broken so far. So you do not get rigorous security guarantees but only the statement that nobody that tried did succeed (which says nothing about how many tried and who tried...).


Point decompression on an elliptic curve I'm programming an elliptic curve cryptosystem and I'm having difficulty with decompressing points. The following information is from my project specification as to my understanding:

Given a point $x$ and $y$, we can compress its representation since for every $x$ on the curve, there are two $y$s; one even and one odd. Therefore, we can express the point as $x$ concatenated with a bit $y'$, thus representing the point in half the bits. To do this, we calculate $y' := y \bmod 2$ to detect if $y$ it is even or odd and add this remainder to the $x$ value which has been left-shifted by one bit (one can think of this representation as $2x + y'$). I understand completely why we do this, in fact it's pretty ingenious. My problem is with decompressing the point which apparently involves square roots in a finite field.

Since the equation of the elliptic curve is $y^2=x^3+ax+b$, where $a$ and $b$ are parameters of the curve, we apparently need to compute square roots to uncover $y$. I know how to recover $x$ from the compressed representation; just subtract $1$ if it is odd and divide by $2$ and that's the $x$ coordinate. My specification noted the formula: If $p$ is prime and congruent to $3$ modulo $4$, then finding square roots of an element $z\in\mathbb F_p$ is easy. $z^{(p+1)/4}$ is one root and the other is its negative. This confuses me: Why is this a square root and how do I implement this computation?

Let $x\in\mathbb Z/p\mathbb Z$ be the point's first coordinate, and define
$z := x^3+ax+b$. We know that there exists a square root $y\in\mathbb Z/p\mathbb Z$ of $z$, i.e. $y^2=z$.
Let's assume we have already found such an $y$. Since the order of $(\mathbb Z/p\mathbb Z)^\ast$ is $p-1$, Lagrange's theorem implies $y^p=y\text,$ hence
$$\left(z^{(p+1)/4}\right)^2=\left((y^2)^{(p+1)/4}\right)^2=\left(y^{(p+1)/2}\right)^2=y^{p+1}=y^2=z\text,$$
which shows that $z^{(p+1)/4}$ is a square root of $z$. The possible second coordinates for the uncompressed point are thus $z^{(p+1)/4}$ and $-z^{(p+1)/4}$, and you can select the right one using the "sign" bit from the compressed representation.


Is any decent RNG acceptable as a stream cipher? I have a function f(x,n) that takes a 128-bit key x, and generates n bytes of pseudo-random data. I've tested the output bytes this function for various keys with the NIST RNG testing suite (NIST Special Publication 800-22 A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications) and the results were very good. What concerns are there before simply using the random bytes XORed with the plaintext as a stream cipher?

Edit:

I figured I'd add some more details. The best analogy I can come up with is that the bytes are random in the same way the digits of pi are random.

To be able to withstand cryptanalysis, are there any standard attacks that I should try, or should I just sit down and try my best to expose a weakness, then give it to someone who has more experience in cryptanalysis and ask them to do the same?

The property desired of stream ciphers, just like for any random number generators, is indistinguishability from true randomness — and indeed, any RNG that fails a statistical test suite is obviously not a good stream cipher.

However, to be considered secure, a stream cipher must not only withstand a generic battery of statistical tests; its output needs to be indistinguishable from a truly random bitstream even for an attacker who knows exactly how the cipher works (but doesn't know the key), allowing them to devise specific tests just for that algorithm.

This is the point where most non-crypto RNGs fail: there are various cryptanalytic techniques than can be used to devise specific tests to tell the output of a given algorithm from random data, and RNGs which are not specifically designed to withstand them will usually succumb to them.

Of course, as the state of the art advances, sometimes that can happen even for ciphers that were previously thought to be secure, but any cipher generally accepted as secure must at least have withstood a considerable amount of attention from the cryptanalytic community without being broken.


How common are weak RSA keys? There exist certain attacks that can be used against RSA keys whose prime factors are of specific forms, such as one by Coppersmith.

How common are these RSA keys?  If you generate primes randomly, is there a realistic risk of choosing a weak prime number?  Does this risk, if realistic, vanish if you always choose $p$ and $q$ to be safe primes?

For Coppersmith's method to work on $n = p\cdot q$, you need to know $\frac{1}{4}\log n$ bits of $p$.  It would take an amazingly badly botched random number generator in your key generation procedure to reveal that to an adversary.  There have been two high-profile cases of this: low-quality hardware RNGs Taiwan's national identity smart cards in 2013 (summary), and the ROCA vulnerability in Infineon's RSALib library for smart cards in 2017.

Unless you are trying to use the cheapest possible hardware RNG (as seems to be the case with Taiwan's national identity cards), or trying to be clever about generating keys as efficiently as possible (as seems to be the case with ROCA), you don't have to worry about Coppersmith's attack.  There are various ways to generate RSA moduli, and they're all basically fine except insofar as they are distinguishable from one another and enable fingerprinting of RSA key generation procedures.

Safe primes, i.e. primes of the form $p = 2q + 1$ for prime $q$, are not really relevant to RSA.  Strong primes, which are similar but with a few more criteria, were once suggested to be relevant but no longer—the costs of the attacks that they thwarted are much higher than the costs of the best modern attacks on >=1024-bit moduli.  None of these attacks—from the old Pollard's $p - 1$ or William's $p + 1$ to the modern elliptic curve method or general number field sieve—are related to Coppersmith's method, which is about known fixed bits in the factors.


Challenge Response at Application Layer of BLE using ECDSA There is a need for an Offline BLE device to Auth a Phone. I am planning to use challenge response somewhat outlined here.

There is a small change. Instead of shared secret. I am planning to use a Public Key and Private Key.

Basically as soon as the phone connects to ble device. Device gives a random message (at max 20 bytes). Phone reads and generates signature using deterministic ECDSA signature and sends it back to device.

Device validates the signature. Establishes the authenticity for that session.

Public Key is embedded in the device. Private key is made available to owner through user manual or qr code on the device.

Questions:

How good is deterministic ECDSA for a small random message of 20 bytes?
Any visible problems with the flow?

Regarding your Q1, well, ECDSA is fine as long as you have a good random generator on the signer side, while deterministic ECDSA tries to address the randomness issues and thus is good (as long as you do not include fault attacks in your model). I personally prefer Ed25519 amongst the deterministic signatures scheme, but that is a question of personal taste, I'd say.

Now, because your challenge is 20 bytes, if you have enough entropy to be sure to generate random challenges, or a way to ensure the increment of a counter value on each challenge in a non reversible way, then you won't be concerned with replay attacks (which would otherwise be a concern with really small challenges).

As for Q2, your biggest concern would be the lack of Threat model! Or if you have one, you should have provided us with it, because the scheme might seem good if you only consider active eavesdroppers, but is broken as soon as you consider fault attack in your threat model (ie. the attacker has the device and can make it perform faults during its computation).

Since the device which would be performing the signature is a phone, I'd say you won't be subject to private key recovery through faults.

On the other side, the Offline BLE device is most likely subject to faults, which may allow to trick the signature validation. See for example the work of Riscure to bypass Secure Boot using Fault Injection, where they bypass such a single verification easily.

Now, another concern is that you have to use an OOB (out of bound) channel to transmit the private key to the phone, which means that you may as well have transmitted a secure LTE key using that same OOB method and you would have arguably (don't hit me) achieved the same goal: only the device knowing that key would be able to communicate with your device...
(Okay, with your scheme, if the Offline Device is stolen, it does not allow private key recovery, but if someone has the ability to recover a key from a BLE device, I'd say they have the ability to perform faults on the signature verification process and trick the device into believing he's speaking with someone who's got the key... thus achieving the same result. Unless you were to authenticate every message sent to the device, in which case it might be a bit harder, but faults of LE devices are generally really easily to perform.)

I don't see any other concern with your design, except that low energy devices generally don't have the power to perform ECDSA signatures, from what I know... But maybe this is old news and not the case anymore.

By the way, you might want to check the http://www.gattack.io/ website, and more specifically to read their whitepaper (even if it seems a bit dated).
From what I've read, it looks like you really should use BLE 4.2, which features ECDH for the LTE key exchange. (Yet, I haven't found much information on that topic). If you are compelled to use a prior norm, or can't rely on ECDH, then it seems like only BLE link-layer in OOB mode is actually secure.


MAC forgery using the DES's Complementary Property I've started reading on MACs and working on a problem where given a MAC construction as $H_0=IV$ and for every $i>0$ $H_i=H_{i−1} \oplus E_{M[i]}(H_{i−1})$ and the tag is $(IV,E_{k_1}(H_ℓ))$, I would like to show for a DES as a cipher this construction does not give message integrity.
The way I'm thinking of approaching this is, I can start by using the complementary property of DES cipher, to show that for message $M_1$ given that $H_1=H_{0} \oplus E_{M[1]}(H_{0})$ is equal $-H_1$ for message $-M_1$ (complement of message $M_1$). Hence, under the chosen message attack with given construction, I can perform existential forgery. Based on my reading and the details defined in Coursera I think I almost got the concept but not sure if I'm on right track?

Yes, you are on the right track.
Let the MAC is given as

$H_0 = IV$
$H_i=H_{i−1}\oplus E_{M[i]}(H_{i−1})$ and for every $i>0$, and
$tag = (IV,E_{k_1}(H_\ell))$

and the attacker has the tag $t$. The observation is that the message is used as a key in the encryption. If the attackers can use some property of the cipher like a fixed point or more then they can forge. Actually more than the existential forgery, if we omit the keeping the IV same, they can find another message that is exactly the same MAC output.
The simple case: one block message $m$ and its tag;
$$t = (IV, IV \oplus E_{m}(IV))$$ for a fixed IV, and this is hard. We need some weaknesses in the Encryption algorithm. As you noted the DES has complementation property
$$E_K(P)=C \iff E_{\overline{K}}(\overline{P})=\overline{C}$$ then the attacker can use this as;
Let $ C = E_m(IV)$ then with DES complement property $\overline{C} = E_\overline{m}(\overline{IV}) $ Then
$$ \overline{IV} \oplus E_{\overline{m}}(\overline{IV}) = \overline{IV} \oplus \overline{C} = IV \oplus C$$ therefore this is a forge with almost the same tag $t$ with just complemented IV $$t' = (\overline{IV},\overline{IV} \oplus E_{\overline{m}}(\overline{IV})).$$


64 bits password = 13 characters? If we use upper and lower case letters, and 10 digits, we get
  approximately 6 bits per character. Then, strings of 13 characters
  should work.

I saw above explanation in the material, but I cannot understand how 13 characters are appeared. How can I compute?

Suppose the number of a set $S$ is denoted as $Card(S)$ (which is sort for cardinality if you didn't know), then

$Card($uppercase-letters$)+Card($lowercase-letters$)+Card($digits$)
=26+26+10=62$

To represent an element from a set of 62, you need a string of at least 6 bits, this is because $2^{6} = 64 \ge 62$

However I don't understand the title where it says "64 bits password = 13 characters" because $ 6 \cdot 13 = 78 $ which is way bigger here, than 64.

To achieve at least 64-bit entropy, you need to uniformly draw ${ {64} \over {log_2{62}} } \approx 11.00$ characters (10.749 to be more exact).


Can rainbow tables find the preimage of a hash? Given a hash value, how are you supposed to find its preimage? What steps can I take to solve find the preimage of a hash such as this 2d202cb6a781edf6ac01d14e1dd6367497db90ba9e8ad721fd17239228a213f9 (SHA256)

The only way to find the preimage of a hash value is to guess. There is no better way than trying all possible inputs by brute force until you find a match. This property is a design goal for cryptographic hash functions (preimage resistance).

A rainbow table doesn't help finding preimages, as such. Rather, it's a tool that helps you reuse somebody else's brute force work. If a rainbow table contains 1 trillion entries, then you can use it to find the preimage of any of those 1 trillion hash values in a short time. But the maker of this table had to make the 1 trillion hash computations. The reason rainbow tables are (occasionally) useful is that once the table has been built (a high one-time cost), you can make as many queries as you want (very low cost per query). It is useful if you have reason to believe that the preimage is among the 1 trillion in the table — if the preimage isn't one of these then all the rainbow table will tell you is that it definitely isn't one of these. See Crunge's answer on Security Stack Exchange for a very nice explanation of how rainbow tables work.

In practice looking up a hash value on Google is a low-effort way to find some simple preimages. When that doesn't work, it tends to suggests that tying to invert the hash won't be the easiest method of solving your problem.

Looking for the hash value in your question turns up a partial copy of a homework assignment which mentions “You should use the tools provided in the file, but are not limited to them.” Said file was not included in that copy of the assignment, but it should be in yours. What you need to do to solve the assignment is, presumably, to figure out how the provided tools work.


Using Chi-Square for Vigenère Cipher I am writing a program which will use Chi-Square to determine which is the correct keyword for a ciphertext via Vigenère cipher.
I came across a website that describes the Chi-Square statistics in a rather simplistic manner and had also written some code to achieve my goals. However, the actual keyword does not seem to be the lowest chi-square value as according to the website. I'm not sure if the method as describe is correct or not.
Quoting the website:

Chi-squared Statistic
The Chi-squared Statistic is a measure of how similar two categorical probability distributions are. If the two distributions are identical, the chi-squared statistic is 0, if the distributions are very different, some higher number will result. The formula for the chi-squared statistic is:

where CA is the count (not the probability) of letter A, and EA is the expected count of letter A.
This page will describe the use of the chi-squared statistic for cryptanalysis. Ordinarily, statisticians use the chi-squared statistic for measuring the goodness of fit of data. Unlike statisticians, we make no assumptions about the distribution of our data, and draw no conclusions about the significance of the result. We simply use the method to suggest a possible decryption.
…

Would someone be able to provide some advice on this?

This method isn't deterministic. That is, just because a keyword has the lowest chi-square value, that doesn't mean it's the keyword. All it means that there is a good chance that it is the keyword. It's not a guarantee. You should look at the first several likely options to see if the keyword lies there. If you want to automate this, you could compare the possible keywords against known words using some dictionary file.


How to prove hardness of approximate-GCD problem? I am trying to prove the security of my system using the hardness assumption of the approximate-GCD problem using contradiction, i.e. If the attacker is able to break in our scheme, then attacker would be able to solve the approximate-GCD problem. I am stuck at the point where I proved that the complexity is O(2^rho) using brute-force approach. How shall I proceed? Is there any concrete complexity measure which can be used as to prove the contradiction?

I am stuck at the point where I proved that the complexity is $O(2^\rho)$ using brute-force approach. How shall I proceed?

Well, a proof that assumed a specific attack strategy is of limited use, as that proof would be inapplicable if the attacker used some other strategy.

Instead, what we typically do in a proof is assume that the adversary had some Oracle that could break your system, and then show that, using that Oracle, he could break the hard problem (in this case, approximate-GCD).  This has the advantage that it doesn't matter how the adversary breaks your system; if he can break it by any means, then he can solve the hard problem; hence, if he is unable to solve the hard problem (which is our assumption), then he can't break your system.


Known Plaintext Attack on Block Cipher in ECB and CBC Modes of Operations These 2 similar questions  are from Paar's Understanding Cryptography. I could not see the answer so if someone can help I will appreciate:

Question1:  We consider known plaintext attacks on block ciphers by means of an exhaustive key search where the key is $k$ bits long.The block length counts $n$ bits with $n>k$ .

(i)  How many plaintexts and ciphertexts are needed to succesfully break a block cipher running in ECB mode? How many steps are done in the worst case?

(ii) Assume that the initialization vector IV for running the considered block cipher in CBC mode is known. How many plaintexts and ciphertexts are now needed to break the cipher  by performing an exhaustive key search? How many steps need now maximally be done? Briefly describe the attack.

(iii) How many plaintexts and ciphertexts are necessary if you do not know the IV?

(iv) Is breaking a block cipher in CBC mode by means of an exhaustive search considerably more difficult than breaking an ECB mode block cipher?

Question 2: Keeping an IV secret in OFB mode does not make an exhaustive key search more complex. Describe how we can perform a brute force attack with unknown IV?What are the requirements regarding plaintext and ciphertext?

Let me proceed by giving the answers, some of which are probably considered wrong by the book:

(i) One. If you have two ciphertext blocks that are identical you leak information about the message itself, so the cipher would be broken. A message may well consist of multiple blocks with repeated plaintext after all. You'd need $m$ messages of a single block (max) before they start to repeat in the worst case, assuming non-random padding. Here $m$ is the number of messages in the message space, with $m \leq 2^n$ - so $2^n$ is the maximum  of the maximum.

(ii) One. You can verify the correctness of the key with high probability using the a single known block as $n > k$. Even if this is not the case the message may occupy multiple blocks. You'll never be completely certain though. The maximum time for an exhaustive key search is of course $2^k$ (this one is probably correct by the book).

(iii) Still one, because you can simply consider any blocks after the first block.

(iv) Yes, generally it is considered more difficult. ECB is insecure and exhaustive key search is often not practically possible for high enough $k$.

2 You just consider the next blocks as you know the first (known) ciphertext block. The plaintext and thus ciphertext needs to consist of more than one block for this, but only if the IV is random instead of just "unknown"; the more bits you know of each message the better.

As indicated, horrible questions. I would presume I would have quite a few wrong, if just out of sheer unwillingness to understand.


What would be a really secure way to encrypt sensitive data on a web site The problem

I need to encrypt sensitive client information in my site and make sure that even in the worst case scenario that the site gets hacked the information cannot be retrieved. (I guess is similar to the credit cards situation)

What I see around

I found many discussions regarding how to secure the credit card information and the approach I see around in forums is to use an algorithm like AES to encrypt the data using a key stored in the code or a configuration file or similar.

My guess of whats wrong

Surely that would make the data secure as long as the attacker only gains control over the database and no other file in the server, but, if someone was good enough to break your security or find an exploitable hole in your system is a good chance he also gained access to the key, and therefore, is still a chance he can decrypt the data.

A possible approach I think it could work

I'm thinking I could split the key in two parts, have one part in a file readable only by the web server's user and the other part shared by the users with rights to see that data in this way:

First the key is assigned to the first admin user and I use the user's password (which is not saved anywhere) to encrypt that part of the key and stored encrypted with that users information.
When another user is to be assigned that part of the key, then the first admin would decrypt the key and encrypt it with the new user's password and store that with that user's information, and like that for any other user.

Update for more clarification:
Having a message $m$ I will use a key $k$ that I will generate, and then when storing that key to use later I will split (or XOR it or something) so that $k$ now will be the result of some operation applied to $k_1$ and $k_2$, for example: $k = k_1 \oplus k_2$, then I save $k_1$ in a file readable only by the web server user. And to save $k_2$, I will use the user's password as key $s$ to encrypt $k_2$ and store it with the user information, and therefore there will be $n$ different $r$, where $r$ is $f(k_2, s)$ where $s$ is different by each user and therefore $r$ is different by each user.

So that to recover $m$ from the encrypted version $e$ and $d$ being the algorithm to decrypt we need to: $m$ = $d(e, d(k_2, s) \oplus k_1)$, and as $s$ is the user's password, you can't decrypt the message unless you the password of a person with access to the data; the system will never have stored the complete key anywhere.

This way even if gained access to the complete server there would be no full key to decrypt the sensitive data.

Would that be a good way?

Does this makes sense? are other/better ways to achieve it? (I'm sure there are).
So, that is what I'm after, to know what other/better ways solve this can someone with actual knowledge on encryption can tell me (I consider my self a complete newbie on cryptography).

Note:

It seems there is a confusion on my question being off topic. I want to clarify that I'm not looking for any implementation, what I'm after is to know what the recommended algorithm and techniques are suggested for this kind of situation, so I can proceed to research and implement them.

1. Clarifying the attacker model

You need to decide, what sort of attacks you want to protect from. The general  eavesdropping adversary model suggest that the attacker can access your database and your entire system any time.

Another, more specific assumption can be mobile eavesdropping adversary. The "mobile" attributive relates to the fact that the adversary does not have access to your system any time, only for a limited time - for instance, somebody breaks in to your server and you detect the attack, patching the system, and with that move you "remove" the attacker. The attacker might break in again, but until that point the new information is considered to be secure. Any data accessible on your server during the time window of compromise considered to be leaked in full.

You may also consider, that some special hardware (e.g. HSM) stored private keys cannot be compromised - whether this assumption is correct or not depends on the further capabilities of the attacker

You also need to consider outsider or insider attack - outsider can be a hacker from the internet, insider can be a rogue employee.

It is important to note, what axapaxa pointed out clearly: an active attacker might be able to change the behavior of your site, and steal the passwords or do other malicious changes to gain access to the information. Protection against an active attacker is hard, would require digital signing of your webserver resources on a way, that the user can check it before connecting to your service - for instance, checking the code signature on your javascript, signed with a key not available on your webserver (so, TLS does not count...). Unfortunately, there is no such a standard - yet.

So, I will stick with the passive/eavesdropping adversary assumption. Still a nice challenge to solve :).

2. Encryption architectures

On the market, you can categorize the existing solutions for this matter based on two standpoints:

where is the key managed and persistently stored
where is the encryption process takes place

Key management categories:

Managed by the site provider (this is you) with the site (e.g. simple database encryption)
Managed by the site provider in a different system (e.g. a HSM or other special hardware)
Managed by the end-user, in its own datacenter/on-premise server (e.g. HSM is provided by the end-user, your system get temporal keys from such hardware)
Managed by the end-user, on its end-device (e.g. private keys in the browser; or the password of the user if you don't store it on your webserver)

Encryption process categories:

Encryption takes place at the site provider's server (e.g. using simply a software encryption lib, with a key anywhere above)
Encryption takes place at the site provider's, separate subsystem (e.g. using a special hardware, HSM, for the encryption process as well, not just for key management)
Encryption takes place at the end-user on-premise server (e.g. encryption gateway like CipherCloud)
Encryption takes place at the end-user device (e.g. using JavaScript to encrypt).

I will not go through all of the combinations here (16 cases) in details, only the end-device key management and encryption.

Note, that your suggested version falls into the category of End-device managed key with site provider managed encryption process. This can limit the damage of a mobile eavesdropping adversary, if you regularly patch and check the system. If you want to go down that road, that is fine, even not the most secure setup, I would suggest the following:

Use PBKDF2, or preferably bcrypt, or scrypt (the last is the best) to derive a good secret from the password. Use random salt + at least 1000, but preferably 10,000 iterations, with scrypt sufficient size of memory map (larger the better, but webserver is a tricky question...). Let's say that the secret derived from the password is X.
DO NOT store X for password validation.
Use HKDF-Extract with random salt to derive from X (let's say, V), or derive from the password using PBKF2/bcrypt/scrypt using the same parameters as for X, but with a different IV. Store V for password validation.
Use HSM or other special hardware to do the server side encryption of the data.

DO NOT encrypt data with HSM+X, rather encrypt a key-encryption-key K. Encryption of actual data with K can be done outside of a HSM, simply using a crypto lib on your webserver.
I suggest using AES-GCM with random IV for data encryption, AES-KW for key wrapping. You may also consider format-preserving encryption modes IF, and ONLY IF there is an unavoidable size constraint for the data, because format-preserving encryption modes are less secure than AES-GCM with random IV.

3. End-device managed key with end-device managed encryption (aka. end-to-end encryption)

You asked about a website, so I will focus only on WebCrypto API capabilities - an encryption library for JavaScript, provided by modern browsers. For applications, you may use other cryptolibs.

With WebCrypto, you can generate a secure random key, to use it for encryption. Encryption can take place at the frontend of the website, for instance before submiting a form, a JavaScript encrypts its content with AES-GCM. The keys can be stored in the local storage of the browser, which is never shared with your website, unlike cookies - it is kept local all the time.

However, if you want that a user access the information from another computer, I suggest that you use PBKDF2 to derive a secret from user password (using proper salt and proper number of iterations for stretching) on the browser side. Then, using this derived key, you can wrap the encryption keys with AES-KW - all supported by WebCrypto API.

This way, your server will not get access to the user password any-time, unless you do the password authentication properly. If you want to authenticate the user, do not send the password to your server, because that is an actual disclosure and the whole point of keywrapping, encryption will slip on this banana... instead of that, use PBKDF2 derived secret for authentication, with a completely random salt, different from what is used for encryption. You may also consider using SRP, SPAKE, AugPAKE, etc. for authentication - however, those are not supported by WebCrypto.

If you do not want to implement those, you may also consider using 0_kit, a project I am involved in, which provides all those features integrated, on top of WebCrypto and other JavaScript implementation of crypto algorithms.


Why we can't implement AES 512 key size? Out of curiosity why we can't implement AES 512 key size?

Please explain somehow i can understand! I'm not an expert.

We can't implement "AES 512 key size" because AES is defined for key sizes $k\in\{128,192,256\}$ bits only¹; much like, by definition, we can't make a bicycle with 3 wheels.
I see no reason why we would want to define an AES variant with 512-bit key size (since AES-128 is safe enough for anything foreseeable most current applications except those that require huge security margins, AES-192 is more than enough for the most demanding ones, and AES-256 more than overkill³). However we could define an AES variant with 512-bit key size. If we stick to the 128-bit block size, the two choices we have to make are:

How many rounds we should use; since the number of rounds in standard AES is $r=k/32+6$, anything even from $r=14$ (for performance and subkeys space comparable to AES-256, at the expense of resistance to related-key attacks much lower than AES-256) to $r=24$ (as a paranoia damper) seems justifiable.
How we would generate the $4(r+1)$ 32-bit words forming the $(r+1)$ 128-bit round subkeys out of the 512-bit key. By analogy with standard AES, the first 16 such words should be right from the key. I won't venture further.

The question seems to have been motivated by a "paper" titled AES Algorithm Using 512 Bit Key Implementation for Secure Communication (I'll charitably not mention the authors) which presents an AES variation with 512-bit key and block size, best summarized as: AES-128 with $8^2$ bytes wherever the original has $4^2$, an idea that at least could be made to work. However the "paper" has blatant issues:

The "paper" present as "drawback" of AES-256 (which uses 14 rounds) that a 9-round variant is vulnerable to a related-key attack with $2^{224}$ works; yet it introduces a 10-round AES variant without the slightest justification that it will resist similar attacks.
The aim is "higher level of security throughput", without attempt of definition; and doing so "without increasing overall design area as compared to the original 128 bit AES", while the state of the proposed algorithm (thus number of D latches in an hardware implementation) is 4 times that of AES-128, for both key and data.
The drawing of the byte substitution step clearly shows a 4x4 grid of bytes holding "an array of 64 bytes".
There is the same issue in the "shift row" step (to be read as ShiftRows), and the drawing gets confusing, since the line with $s_3$ is shown right-rotated by 1 step, when the intend is that it is left-rotated by 3 steps.
Proof that the "Mix Column" step (to be read as MixColumns) is reversible, which is necessary for decryption to be possible, is alluded to only by dumping an alleged inverse of the polynomial used in MixColumns, without derivation.
On closer inspection, the matrix given for MixColumns does not correspond to the polynomial stated for MixColumns per the conventions used in the real AES; and the alleged inverse polynomial can not match either, according to any convention, for it contains too many terms with multiplication by $\{01\}$, so that decryption using it won't work. I conjecture that this would-be inverse polynomial simply has its four terms of even degree taken from the polynomial used for AES's InvMixColumns (within a reflexion); and other terms set to $\{01\}$, because there are a lot of these in the direct polynomial.
The number of rounds in the 512-bit AES variant is set to 10 with the sole justification that there are "ten AES rounds", without reference to which of the three AES ciphers that applies to.
The round index is variably $I$ or $i$ including in the same equation.
The first round constant probably has a typo.
But there's no test vector to settle that.
Performance is compared against AES-128, stated as encrypting "128 bytes" in "30-50 Seconds" on an unspecified platform; which (if we ignore the spurious capital S) is about $2^{26}$ times slower than routinely achieved by a single core of a modern CPU with AES-NI.
The 512-bit AES variant is stated as encrypting the same "128 bytes" in "20-40 Seconds" yet has "230%" the throughput; this creatively redefines benchmarking.
It is stated that the "Processor Required" is "Less" than for regular AES, with no attempt to evaluate the number of operations or memory accesses per byte encrypted; indeed this is about the same as in AES-128 for all steps except MixColumns, where there is significantly more work per byte (twice as many columns, each requiring multiplication by a matrix with twice as many raws and twice as many columns, thus about 8 times more work for 4 times as many bytes, thus about twice more work per byte; admittedly, the proportion of entries in the matrix that hold a $\{01\}$ is higher, but this only partially lowers that increase in work).
Proceedings is spelled "Pro-ceding's".
Several entries in the citations are to equally vacuous papers published in caricatures of scientific journals.
Two citations ([1] and [11]) are to other papers about AES-512, yet are not mentioned in the Existing Work section.
Citation [1] is a 2010 paper strikingly similar to the 2014 paper itself, including having nearly the same title ("Implemented" rather than "Implementation"), yet other authors (and even more mistakes and vacuity).
Citation [11] was published in the proceedings of an IAS 2011 conference with enough relation to the IEEE to be on their website and use their logo (notice that this IAS stands for Information Assurance and Security, not IEEE's Industry Applications Society). A look at this online version shows it is strikingly similar to the 2014 article (including same erroneous polynomials, typo in first round constant, and 230% improvement), with different authors. I vote this 2011 paper as poor (especially on justification of security and misleading benchmark), but the least objectionable of the three.
The numbers for references in the text are often from text cut and pasted from the 2010 paper, rather than related to the numbering of the references given in the end.
The paper is published in the "Best Peer-Reviewed Journal", which also brags being an "ISO 3297:2007 Certified Organization" (when a cursory look at the summary of this standard shows that it is about numbering publications, not review of their content). That journal also boasts an impact factor of 7.488; this is telling of how reliable a measure of seriousness the impact factor is.

¹ Quoting FIPS 197:

This standard specifies the Rijndael² algorithm, a symmetric block cipher that can process data blocks of 128 bits, using cipher keys with lengths of 128, 192, and 256 bits.

² The Rijndael block cipher has the same 256-bit key limitation:

the block length and the key length can be independently specified to any multiple of 32 bits, with a minimum of 128 bits, and a maximum of 256 bits.

³ By most accounts, 256-bit key is safe including against hypothetical quantum computers usable for cryptanalysis. If we also want 256-bit blocks, Rijndael allows that.


How to encrypt plain message with RSA Let's say I want to use RSA to encrypt a message 'Rocket will be launched at 2am' that has 30 letters.

I use the keys from this example: https://etherhack.co.uk/asymmetric/docs/rsa_key_breakdown.html, so the modulus is 129 bytes long (1032 bits long number). So my message is shorter than the modulus and I can encrypt it.

(Let's assume I don't use padding scheme.)

What I have to do now with my message to encrypt it?

I have to convert it to a number $m$, so I use some encoding to convert each letter to byte and I concatenate the bytes? (how do I choose that, is there a convention, will encoding and endianness be written into ASN.1 keys)

According to RSA I now have to compute:
$$c(m)=m^{65537} \pmod{\text{...1032_bits_long_number...}}$$

and message is 240 bits long number. Is this the procedure?

The straight-forward way to do this is:

Convert the ASCII string into an array of bytes.
Convert that byte array into a large integer. For that you need a library with support for arbitrary large integers (e.g. BigInteger)
Endianness does not matter for this.
For encryption, the library should already offer some modular exponentiation method, because otherwise you will have to write square-and-multiply yourself, where you apply the modulus after every step.
Decryption is the same as encryption, it's just modular exponentiation again.

Of course this is just for this basic exercise. In an actuall application, you definately need:

A proper padding scheme, e.g. RSA-OAEP
You usually don't encrypt the message directly. Instead, hybrid encryption is used in all cases, so that it doesn't matter how long the message is.
Follow the standards, e.g. PKC#1, section 4 for the data conversion from integers to byte strings (thanks to @MaartenBodewes for pointing that out)
And to be honest: You should just use an implementation of RSA (and other encryption schemes) provided by a cryptographic library.


Is there a standard way to use a nonce with HMAC? Many protocols use HMAC on messages that include a nonce, but they don't seem to do it in a consistent way. For example, in OAuth the nonce is in the middle of an URL-encoded key-value string, like this:

POST&http%3A%2F%2Fexample.com%2Frequest&a2%3Dr%2520b%26a3%3D2%2520q
%26a3%3Da%26b5%3D%253D%25253D%26c%2540%3D%26c2%3D%26oauth_consumer_
key%3D9djdj82h48djs9d2%26oauth_nonce%3D7d8f3e4a%26oauth_signature_m
ethod%3DHMAC-SHA1%26oauth_timestamp%3D137131201%26oauth_token%3Dkkk
9d7dh3k39sjv7

This is probably because different protocols use the nonce for different purposes. However, I'm interested specifically in using a nonce with a constant message to get different authenticators for repeated messages (with the same key).

Is there a standardized way to include a nonce in HMAC authentication?
Is there any theoretical difference in between $H_K(\text{Msg}||\text{Nonce})$ and $H_K(\text{Nonce}||\text{Msg})$?

Under the assumption that $(K,\text{Msg})\to H_K(\text{Msg})$ is a secure MAC (be it HMAC or any other MAC), and $\text{Nonce}$ does not repeat and is of fixed size, both $H_K(\text{Msg}||\text{Nonce})$ and $H_K(\text{Nonce}||\text{Msg})$ are demonstrably secure, in the sense that an adversary not knowing $K$ can't distinguish either from random, even for iteratively chosen $\text{Nonce}$ and $\text{Msg}$.

When $(K,\text{Msg})\to H_K(\text{Msg})$ is HMAC, and we do no trust the underlying hash, and the weakness of this hash is bad enough that HMAC is not secure, it is hard to tell which of $\text{HMAC}_K(\text{Msg}||\text{Nonce})$ or $\text{HMAC}_K(\text{Nonce}||\text{Msg})$ is likely to be least broken. I wouldn't worry about that, because HMAC is secure with less-than-collision-resistant-hashes both in theory and practice (MD5's collision-resistance has been torn to pieces, but HMAC-MD5 so far stands valiantly). Any remaining security may depend more on what constraints the adversary really has on $\text{Msg}$, and what really counts as a success, than on anything else.


Modular Reduction of polynomials in GF(2^m) I am having trouble understanding the algorithm implementation in the hardware of the reduction process over Galois fields of $F_{2^{163}}$
In the following process, it looks like we are calculating the $zc(z)$ value from 2m-2 downto m
which the first half of $c(z)$

but I am not getting to understand what is $r(z)$ and how it is obtained?
$r(z)$ shouldn't be fixed as $Z^m$ and if it s a polynomial what is its value and what is W?
and how is the process of $z^k * r(z)$ viewed as in hardware
is it only left shift by 1 for each k and an and gate with $r(z)$?

I don't know if this can help you, but did you know if in Binary Arithmetic, you have: $f(z)=z^m+r(z)$; then $z^m =f(z)+r(z)$.
NB: The addition here represents the bitwise XOR, that you can easily represent in hardware by appropriate gates.
Then Let's continue by examining the reduction algorithm you show us:
$c(z)=c_{2.m-2}.z^{2.m-2}+c_{2.m-1}.z^{2.m-1}+\cdots+c_{m}.z^{m}+c_{m-1}.z^{m-1}+\cdots+c_1.z+c_0$
We factorize by $z^m$; then, we obtain:
$c(z)=(c_{2.m-2}.z^{m-2}+c_{2.m-1}.z^{m-1}+\cdots+c_{m}).z^{m}+c_{m-1}.z^{m-1}+\cdots+c_1.z+c_0$
And replacing $z^m=f(z)+r(z)$ and performing the reduction mod f(z): the remaining is:
$c(z)=(c_{2.m-2}.z^{m-2}+c_{2.m-1}.z^{m-1}+\cdots+c_{m}).r(z)+c_{m-1}.z^{m-1}+\cdots+c_1.z+c_0$
Which can be computed, with the precomputed table!

Another interpretation of $r(z)$ from $z^m =1.f(z)+r(z)$ shows that $r(z)$ is the remainder of the division of $z^m$ by  $f(z)$ while the quotient is the constant polynomial 1.


Differential-linear attack on DES Is there any known differential-linear attack on full round DES? I couldn't found any and couldn't work on this due to time restriction.

For this particular type of attack, the best it can do is attack 10 rounds of DES, with 2^50 time complexity and 2^20 plaintexts.


Is there an existing AE protocol with forward secrecy for embedded devices? I'm working on an embedded device that is connected to a computer over an untrusted channel. According to my threat model I need authentication and encryption on the wire with perfect forward secrecy. Both endpoints have a pre-shared key and/or each other's authentic public keys, as well as secure random number generators (although not requiring a secure RNG on the device is a plus). All messages on the wire are fixed-length (16 bytes, i.e. 128 bits).

I'm looking for an existing cryptographic protocol satisfying these properties that would be reasonably simple to implement.

The "toy" protocol I've come up so far is performing an Elliptic-curve Diffie-Hellman key exchange (wrapped in AES-CCM with pre-shared key for authentication), then running a key derivation function on ECDH shared secret and using the result as session key for AES-CCM that encrypts and authenticates data. AES-CCM is used to authenticate ECDH because of limited amount of space code on the device, so I have to use as little primitives as possible.

But I don't want to use a protocol that I've just made up (for obvious reasons) and protocols like TLS, OTR and SSH are way too complex for use in embedded devices. Is there a simpler protocol that provides authentication and encryption with forward secrecy that I could use?

Update: to clarify, establishing a connection doesn't have to be fast, so I can afford a lot of computation. The only requirements for asymmetric crypto is keeping the keys short, hence elliptic-curve cryptography instead of discrete logarithms.

I've finally found a solution - some variants of key ratcheting, e.g. the one used in SCIMP, provide perfect forward secrecy assuming an initial shared secret is established without any asymmetric crypto, and they don't even require a secure random number generator on any of the endpoints!

In this case all we need for an authenticated and encrypted protocol with perfect forward secrecy a symmetric cypher, an authenticated encryption mode for said cypher (e.g. EAX) and a hash. We can even ditch the RNG on the embedded device.

This is not a complete protocol, but gets us most of the way to one, and it's dramatically simpler both in the implementation and the number of required primitives than TLS.

The hard part is proper handling of message losses on the wire without opening up to downgrade attacks, but it's easier than correct custom implementations of asymmetric crypto.

Ironically, nobody I asked could tell me about using such key ratcheting for perfect forward secrecy. Our team has come up with the scheme on its own and only after that I've found it in literature.


If OAEP is introducing randomness to encryption how could be ciphertext decrypted? I was studying OAEP and see we introduce a random value $r$ when computing the padding. See the figure below from Wikipedia

So if we are adding randomness to encryption, how could this ciphertext be mapped to plaintext? I understand a plaintext $m$ being mapped to numerous $c_i$ ?

Also to decrypt, don't we need to know $r$? In that case $r$ becomes a key

To decrypt the ciphertext you definitely need to recover the random token $r$.
But $r = Y \oplus H(X)$. Then knowing $r$ the padded message can be recovered as $m0\dots0 = X \oplus G(r)$. The decryptor only need to known the size of the random token $r$ and this is usually part of the standard. Of course the standard has to define the $F$ and $G$ functions and how to pad the message. The padding process has to be such that unpadding the message after the decryption is deterministic and unique.

The randomness added to the encryption process makes impossible for an attacker having access to an encryption oracle (or observing a lot of messages and their effect) to create a dictionary of corresponding couples of $(m_i, c_i)_{i\in S}$ where $c_i = Enc(m_i)$. This property has been defined for the first time in the paper by Goldwasser and Micali "Probabilistic Encryption" (Shafi Goldwasser and Silvio Micali, Probabilistic Encryption, Special issue of Journal of Computer and Systems Sciences, Vol. 28, No. 2, pages 270-299, April 1984)


Is being cryptanalyst synonymous with being a code breaker? I have been recently considering becoming a cryptanalyst. I have moderate background in mathematics, but I am not sure if that is the case with breaking codes and cryptanalysis is just like in the movies. I have passion for puzzles in many forms and brain teasers, finding patterns etc. I have seen that there are contests with brain teasers that agencies such as GCHQ claim to use to screen candidates for code breakers. I don't generally know how do the things look with general code-breaking and I'm asking for some clarification.

Is being cryptanalyst synonymous with being a code breaker?

How much maths will I need? What knowledge will I need?

As someone said with maths Olympiads you use theorems as tools that you have to know well and all the tricks that come with them to do something at Olympiad.

First up, please note that this Q&A is primarily opinion based. Therefore, I’ll be focusing on the symmetric part and nothing else you’ve mentioned and/or asked for in your question.

  99% of cryptanalysis are not code breaker.
   If you try a PhD in cryptanalysis and expect to break code, you are dreaming.

In movies such as Mercury Rising, Imitation Game or A Beautiful Mind, you see cryptanalyst (or child) breaking codes just by being exposed to the cipher text.

Academics consider this kind of attacks as weak. We now works something similar to a Lunchtime attacks. We consider the internals of the algorithm to be know by the attacker and the goal is now to find weakness in it. We are not looking for deciphering a single ciphertext.

Attacks that are used on these algorithm are far more complex (have a look at Differential cryptanalysis, Linear Cryptanalysis, Related keys...)

About the maths level, are required: Probabilities (a lot!), Finite Fields, Affine Varieties and other tools, all of them are about Bachelor-Graduate level.

What is the current state of the art?

In symmetric crypto, using the correct algorithm we are already post-quantum. Should you use strong enough algorithm, even the NSA won't be able to read what you are hiding.

In asymmetric crypto, the research is currently being done to get post-quantum assurance. We have things like New Hope.

EDIT:

As stated at the beginning of my answer, the question is off-topic by definition. The reason why it still exists and has been locked (by e-sushi♦) for “Historical significance”, is that we thereby gain a Q&A for all those newcommers to cryptography (and our site), who are confusing “fiction” (read: code breaking in movies) with “reality” (read: modern cryptanalysis in the real world). By keeping this Q&A around, we now have a place to point them to… hoping they learn something from it.


Mutating a SHA-2 input would allow us to have multiple hashes for a single input, would this increase SHA-2's security? Let me elaborate: Say we have two distinct inputs: $A$ and $B$. We also have some arbitrary deterministic mutation protocol $M$ (for example reversing the characters and performing a Caesar cipher).

Say by chance (I understand this is extremely unlikely) $A$ and $B$ result in the same hash when run through SHA-256. However, when $A$ and $B$ are mutated with $M$ first, and then run through SHA-256, they have different hashes.

Am I correct in this thinking? Deterministic mutations would allow us to have multiple hashes for a single input which would make the probability for collisions even lower, because another input would have to have the same hashes for all mutations.

Arbitrary mutation protocol is equivalent to a random permutation (i.e., a random invertible function); so running through $M$ is basically equivalent to encrypting with some random key $K$. You don't need something so complex as a permutation - you could be adding on a fixed prefix, suffix, etc, just as well.

From a hashing perspective, there's no real reason to do this.
Your chances are already $2^{-256}$ anyway for a collision between two inputs (more inputs increase the chance via birthday).  For each change you do and output you're basically increasing the bit-length, so $2^{-512}$, $2^{-768}$, etc. (so you are increasing security). But you could just as well just use SHA-512 if 256 bits isn't enough for you (and it generally runs faster on modern processors)


Decryption of a file encrypted by pseudo-random number generator (The Linear Congruence rand() How to decrypt this file:

https://drive.google.com/open?id=1gZCujDYmEL-FZ5o_xBUS-Ng5979HSsZ7

Given that the only information available about it are:

It has been created on 21/3/2018, 9:05:15 AM
The plaintext of the file is probably starting with "\documentclass[12pt]{article}", and it's a latex file
The code used for encryption is in C, and used a pseudo-random number generator (The Linear Congruence rand()):

/* The ISO/IEC 9899:1990 edition of the C standard */
#define RAND_MAX 32767
static unsigned long int next = 1;
int rand(void) // RAND_MAX assumed to be 32767
{
    next = next * 1103515245 + 12345;
    return (unsigned int)(next/65536) % 32768;
}
void srand(unsigned int seed)
{
    next = seed;
}

#include <stdio.h>
#include <time.h>

//Return a byte at a time of the rand() keystream
 char randchar() {
  static int key;
  static int i = 0;

  i = i % 4;
  if (i == 0) key = rand();
  return ((char *)(&key))[i++];
}

int main(int argc, const char* argv[]) {
  static char randstate[64];

  srand(time(NULL));
  FILE *input, *output;
  input = fopen("Homework1b.tex", "r");
  output = fopen("Homework1b.tex.enc", "w");

  int c,rc;
  while ((c = fgetc(input)) != EOF) {
    rc=randchar();
    printf("c=%d (%c) and rc=%d\n",c,c,rc);
    fputc(c^rc,output);
  }
  fclose(input);
  fclose(output);
}

I read about the weakness of C random and I know that knowing a part of the plaintext should help, but couldn't figure it out.

Short answer: Just replace the srand(time(NULL)); with srand(<epoch
  seconds when encrypted>); and then "encrypt" the encrypted file again
  to decrypt.

Long answer: The unserlying priciple of this programm is a stream cipher, as you already mentioned in your tags, which means the plaintext $P$ is xored with a random keystream $K$. To undo this operation, you simply need to xor the ciphertext $C$ with the same keystream again, which is proven by $C \oplus K = (P \oplus K) \oplus K = P \oplus 0 = P$.

So to reconstruct the plaintext, we need to reconstruct the keystreams to which can be achieved in two ways:

Using the time of encrytion: As you can see in the second line of the main method, the seed of the rand-function is set to the current time in secconds. Since all the following outputs of the rand-function depend on that seed only, one can reconstruct the keystream by setting the seed to the seconds since the unix epoch.
Using a known plaintext:
Let's take a look at how the keystream is generated: $K_{i+1}=(1103515245 \cdot K_i + 12345)\ /\ 65536\ (mod\ 32768)$ This may look complicated at first, but there is one simple property which can easily be exploited: The next state only relies on the previous state. This allows us to compute all the following states using only one state. To get this, we simply xor the ciphertext with the plaintext since $K_0 = C_0 \oplus P_0$ and use it as seed for $K_1$. You can then go on and use the rand-function to get the keystream.

Finally, you need to know the endianness of the encrypting source, so that your decrypting program can match and correctly decrypt.


ECDSA public key point uniqueness I'm new to ECDSA and there is something I still not sure about.
If I have a classic Certificate Authority server that delivers PEM certificates containing public key with ECDSA, I can retrieve the coordinates of the Point on the curve, and the curve used.

My question, is regarding the coordinates of the point $x,y.$
Is it possible that two different generated certs can give me the same point?

Or points are sure to be unique?

Is it safe to set ownership from the combination of $x,y.$
For example, I have an asset and I want to set its owner to "$\{x\}:\{y\}$" ?

Thank you,

Without explaining all details of ECDSA, a public key consists of a curve $E(\mathbb{F}_p)$ and a point $P \in E(\mathbb{F}_p) \setminus \{0\}$.

The point $P$ is a random point chosen from all points of the curve (minus the point at infinity). Because the number of points must be large to be secure, it is very unliky that two randomly generated public keys share the same point.

For example, for secp256k1 (the curve used for bitcoin) you have $115792089237316195423570985008687907852
837564279074904382605163141518161494337 - 1$ possible points.

Without more details of the applications, it is probably safe to use the coordinates of the point to identify peers.