How to XOR two hex values and am I doing crib dragging correctly? (OTP) Let's say I have the two cipher texts

7ECC555AB95BF6EC605E5F22B772D2B34FF4636340D32FABC29B
73CB4855BE44F6EC60594C2BB47997B60EEE303049CD3CABC29B

According to this website http://xor.pw/? the result of the XOR is

d071d0f071f000000071309030b4505411a5353091e13000000

Is this correct? I don't know as I do not know how to XOR two hex numbers (I assume you turn them into binary but this would become incredibly tedious very fast)

And to further my question, is this the correct way to crib drag?

746865 XOR d071d0
Gives a419b5, which is a non ASCII-Character

Then I would to proceed to move one character down

746865 XOR 071d0f
which gives 73756a which in ASCII turns into 'suj' but likely gibberish

and so forth.

Am I correctly doing the procedure?

Xoring this "hexadecmal" value of

7ECC555AB95BF6EC605E5F22B772D2B34FF4636340D32FABC29B

with the hexadecimal value of

73CB4855BE44F6EC60594C2BB47997B60EEE303049CD3CABC29B

will lead to:

0D071..... As the page told you.

Xoring is a so called modulo 2 addition without carry bit propagation. You are adding each bit with the corresponding bit of the other string. First you convert your hexadecimal representation into binary. Then you perform the modulo 2 addition. (dots are for better readability)

7ECC5 becomes 0111.1110.1100.1100.0101
73CB4 becomes 0111.0011.1100.1011.0100
--------------------------------------
XOR
--------------------------------------
              0000.1101.0000.0111.0001
which is converted into
              0    D    0    7    1

PS:

Apply the following rules for adding each bit.

0 xor 0 = 0
0 xor 1 = 1
1 xor 0 = 1
1 xor 1 = 0


HMAC vs Encrypted Hash What is best to use (for message integrity) between…

AES(Data) + HMAC(Data)
AES(Data + HMAC(Data))
AES(Data + Hash(Data))

…and why?

"Encrypted hash" totally fails if the encryption uses a malleable mode like CTR. CTR runs AES in a stream-cipher-like mode where the data to encrypt is simply XORed with a key-dependent stream, so the attacker can flip bits with extreme precision; so if the attacker guesses the contents, he can modify them and fix the hash easily.

More generally, if you want a MAC then use a MAC. The "encrypted hash" is just a homemade attempt at a MAC algorithm, and we know that homemade algorithms are rarely strong, and even when they are we cannot make sure that they really are strong.

As for how to combine encryption and a MAC, this is a well-known questions for which a lot of theory and practice has been accumulated; see this question. To sum it up: you want to compute the MAC over the encrypted data, because it avoids any issue with the MAC algorithm leaking information on the processed data, and it protects the decryption implementation from malformed data.

Now, HMAC seems to be reasonably well-behaved and not to leak information about the data on which it is applied. Your setups 1 and 2 are what is used by, respectively, SSH and SSL/TLS. In neither case did it prove fatal; however, the lack of protection on the encrypted format allowed various padding oracle attacks to experience some success on implementations which were not sufficiently careful when decrypting malformed input data.


Authentication of data using XOR and a secure function Suppose that:

$i$ is a zero-based index.
$K$ is a secret key.
$X$ is a stream of data.
$x_{i}$ denotes the $i$th block of data in $X$.
$s$ is the number of blocks in $X$.
$X = x_{0}\mathbin\|x_{1}\mathbin\|\dots\mathbin\|x_{s-2}\mathbin\|x_{s-1}$.
$y_{i}$ is a value derived from $x_{i}$, $i$, and $K$ in a way that incorporates some known-to-be-secure function (like a block cipher).
$\alpha = \bigoplus\limits_{i=0}^{s-1} y_{i}$.

If the authentication tag is derived from $\alpha$ and $K$ in some way that uses the same function used to in deriving $y_{i}$, then would this be a secure authentication algorithm?

It can be.

Suppose $y_i = F_K(1 \mathbin\| i \mathbin\| x_i)$ and $t = \alpha \oplus F_K(0 \mathbin\| n)$ is the authentication tag, for some PRF $F_K$ and per-message nonce $n$.  The security of this structure is called XMACC and analyzed by Bellare, Guérin, and Rogaway, ‘XOR MACs: New Methods for Message Authentication Using Finite Pseudorandom Functions’, Proceedings of CRYPTO '95, Springer LNCS 963, 1995.

Suppose $y_i = x_i {K_0}^{i + 1}$ and $t = \alpha + K_1$ with arithmetic in $\operatorname{GF}(2^{128})$, where $K_0, K_1 \in \operatorname{GF}(2^{128})$ are uniform random, and $K_1$ is only ever used once.  This is the structure of GHASH, which is used by AES-GCM in Carter–Wegman mode with $K_0 = \operatorname{AES}_K(0)$ and $K_1 = \operatorname{AES}_K(n)$ for a per-message nonce $n$.


ElGamal scheme signature: if private key a mod p is equal to private sig. key k mod p-1, can an attacker notice and determine the value of a? If someone is signing a document using the ElGamal signature scheme, and if the random involved in the signature $k \mod (p-1)$ is equal to $a$ (the private key), can an attacker notice? If so can he then determine the value of $a$?

Would it be because the $\beta = \alpha^a \mod p$ from the published key ($p$, $\alpha$, $\beta$) and $r = \alpha^k \mod p$ from the signed message triple ($m$,$r$,$s$) are the same?

No, it doesn't provide extra information on the private key.

Note that there is no restriction on the private key value, you just have to ensure that $gcd(k, p-1) = 1$ and that $k$ is only used ONCE. Otherwise the private key can be easily found: see this link which explains how it fails for DSA (this is the same reasoning for the ElGamal scheme).


IV generation best practice for AES-256 CBC I saw some SWIFT code that generates IV for AES 256 from selecting 16 characters from a-zA-Z0-9 space. Is this secure? Sufficiently secure?

What is the best practice to generate IV for AES 256? Will picking random 16 bytes from 0x00-0xff be good?

We want to store key and IV in Database and retrieve it for encryption/decryption. We want to store it as a string of values (i.e "1, 255, 126, 124 ..." - 16 values like this). Then decrypt the fields using the decoded values as bytes.

Is there anything to look out for when it comes to IV generation other than making sure that the random generator is good?

We want to use AES-256 CBC.

I saw some SWIFT code that generates IV for AES 256 from selecting 16
  characters from a-zA-Z0-9 space.

  Is this secure? Sufficiently secure?

Almost always, when you see that modern ciphers are initialized by strings then the developer doesn't really understand that ciphers operate on binary data. This is a development practice that has got a special name: stringified code, where each parameter is a string, no matter what.

The characters that are used are almost the base 64 alphabet, which uses 6 bits for each byte. That means that you have (128 / 8) * 6 = 96 bits of security. We'll excuse the 64Ki options left out. That's still plenty of IV space for most usages, fortunately.

It does limit the amount of messages to encrypt with this kind of random IV though; keep to around 4 billion messages ($2^{32}$) or less for high security, and possibly a thousand times ($2^{42}$) more if you want to live dangerously.

The bigger problem is that I would not trust any developer that would use a string as key or IV. That's a $\color{red}{\text{red flag}}$: I'd start looking for other issues, because those are almost certain going to exist.

  What is the best practice to generate IV for AES 256?

  Will picking random 16 bytes from 0x0-0xff be good?

Yes, that is probably the best way of generating an IV for CBC mode. There are other ways of doing the same though. For many modern modes (that are based on CTR mode) you are however only required to use a nonce. In that case, a random IV may still be the best way forward, but a counter has advantages as well. For instance, a counter is less likely to repeat (the chances of an IV colliding are relatively high due to the birthday problem).

Do make sure that you are using a well seeded cryptographically secure random number generator.

  We want to store key and IV in Database and retrieve it for encryption/decryption. We want to store it as a string of values (i.e "1, 255, 126, 124 ..." - 16 values like this). Than decrypt using this as bytes.

That's a bad idea because for any mode the IV should not repeat for the same key. Generally, this is achieved by keeping / prefixing it to the ciphertext. Keeping a key in the database makes little sense as well. The key should be harder to access than the fields that it is trying to protect after all.

Finally, the problem with strings is that they are commonly hard to delete from memory. Generally, you want to remove keys once they are not used anymore. For IV's that's less of an issue, as they can be made public without compromising security.


How can I make my cipher show the avalanche effect? I am a beginner in cryptography. I designed an password based encryption-decryption algorithm, which uses a random salt and a password to encrypt a message. I'm using SHA-512 for hashing, matrix operations for shuffling, bitwise XOR for mixing data and retrieving. The length of the salt and the ciphertext is 256 letters.

To my knowledge, the avalanche effect means that a slight change in any of the following:

cipher
password
salt

must change the output drastically.

In my implementation, if I change the salt or the cipher, I don't see any big changes in my output. However when there is a slight change in password, the output changes drastically.

So, my questions:

Is my understanding of the avalanche effect generally correct? If not, what should it be?
What can I do to best produce the avalanche effect in my (or any) cipher? should I reduce the salt length less and generate a smaller ciphertext to create an avalanche effect? If not, then how can I achieve this?

Don't bother with changing the actual cipher algorithm.  Read about Kerckhoffs's principle: you should only change things like the key and the IV, not the actual algorithm.

In order to test your avalanche, flip one bit in your key.  That should change about half the bits in your output.

For cipher design, Applied Cryptography has already been suggested.  As well as that you need to look at introducing Diffusion and Confusion into your algorithm.  Also it is well worth while studying existing algorithms to see how they go about things.  I started by designing my own simple Feistel cipher, that way a lot of the surrounding structure is already done for you.  It also simplifies the design, in that the F function does not have to be invertible.  That allows you a lot more flexibility in that area.

The warning about not using your own design for anything other than a learning exercise is a good one.


TPM authorization Digest calculation I am going through Steven Kinney's book; "Trusted Platform Module Basics", and pp 90 - 92 discuss how to calculate the authorization digest. He talks about 1H1, 2H1, 3H1, and 4H1 fields which I do not even see in the corresponding diagram. Can anyone explain this process, or point me to a document which does? If you are going to point me to the specs, please advise with document and section if possible.

I had to read the chapter again, and now I think I can explain my question better. My question is about how the authorization block is calculated; specifically which nonceEven is used for it. The book verbiage on page 90 states that the last nonceEven is used, and that leads me to believe that the nonceEven shown in Fig9.6 is not in the input message. Page 91 even says this explicitly; that "...realize that the last nonceEven is not part of the input message that will be sent to the TPM; this value was previously recorded after the also successful authorized TPM command, in this case, TPM_OIAP."
So this leads me to wonder why Figure 9.6 has a nonceEven in it. Is it meant to imply that this is the value, which was created by the TPM previously and will be used to calculate the authorization block? I just think it is a little confusing given the description of the figure, which states "TPM_Sign input message block". That nonceEven should be labeled as last nonceEven. It can not be the new nonce either as this is a diagram of a message input, and the new nonceEven would be generated by the TPM.

The fields are shades of grey encoded:

The legend right above the Figure description.


brute-force factors of numbers on my computer at home? I am currently researching RSA crypto and brute-forcing keys and read about the factoring-problem. There is an increasing difficulty with factorizing numbers of an increasing value, especially when it comes to primes, and this is one of the reasons to why RSA keys are impossible to brute-force.

Not completely unrelated, I was just wondering if I could brute-force factors of specific numbers using my regular computer that I have for personal use. I would like to measure the time it takes to facorize the numbers and how time changes as the numbers grow. Is there a program to download which can do so (facotrize the numbers that is, not neccesary with the time measuring part)? If not then why is it not possible?

Take a look at the paper Factoring as a Service for what you can do using the cloud. In the introduction on page 2 they write where you can find their Software.


secure system in the perfect sense a secure system in the perfect sense verifies the definition of perfect security. My question is as follows: There is always a way to check for perfect security by solving the first degree equation by finding k? for example if i have c = (k * m) xor mod7

A sufficient (but not quite necessary*) condition for a cryptosystem to provide perfect secrecy is that:

every key is equally likely (and independent of the message), and
for every message $m$ and every ciphertext $c$, there exists a unique key $k$ such that $k$ encrypts $m$ to $c$.

The relationship between $m$, $c$ and $k$ does not necessarily need to be a linear one; it is sufficient that it be one-to-one, so that we can always find a unique matching key $k$, given $c$ and $m$.

In particular, let $M$, $C$ and $K$ be random variables denoting the unknown message, ciphertext and key respectively, and let $\Pr[M = m]$ and $\Pr[M = m \mid C = c]$ respectively denote the attacker's subjective probabilities of $m$ being the correct message before and after observing the ciphertext $c$.  Then, by Bayes' law, $$\Pr[M = m \mid C = c] = \frac{\Pr[C = c \mid M = m]}{\Pr[C = c]}\, \Pr[M = m],$$ where $\Pr[C = c \mid M = m]$ is the probability of the message $m$ yielding the ciphertext $c$, and $$\Pr[C = c] = \sum_{m'} \Pr[C = c \mid M = m'] \Pr[M = m']$$ is the marginal probability of any message yielding the ciphertext $c$.

Now, by the assumptions that:

the key $k$ is uniquely determined by $m$ and $c$,
the key $k$ is independent of the message $m$, and
each key is equally likely to be chosen by the encryptor,

we have $\Pr[C = c \mid M = m] = \Pr[K = k(m,c) \mid M = m] = \Pr[K = k(m,c)] = \frac1n,$ where $n$ is the total number of possible keys — a constant independent of $m$.  Since the marginal probability $\Pr[C = c]$ is also clearly independent of $m$ (and, in fact, also equal to $\frac1n$), we find that $\Pr[M = m \mid C = c] = \Pr[M = m]$.

Thus, observing the ciphertext $c$ will not change the attacker's belief in the likelihood of a given message $m$, which is the definition of perfect secrecy.

*) Strictly speaking, the key $k$ need not actually be unique; all that's needed is that, for each $(m, c)$ pair, the number of distinct keys that encrypt $m$ to $c$ is the same.  We could also relax, or even completely eliminate, the requirement that all keys are equally likely, but then we'd have to rephrase the remaining criteria in terms of the probabilities of the sets of keys encrypting $m$ to $c$, rather than just their number, being equal.


Can we use fixed Beaver's multiplication triples many times? In the secure computation based on GMW and SPDZ style approaches, we use multiplication triples to gain efficient online computation time.

Can a same triples be used multiple times?
Is there any need to update the triples?

If you reuse the same multiplication triples, then you leak information about the secret shared values that you multiply.

Let's recall how the multiplication works in Beaver's protocol for secure evaluation of arithmetic circuits. Protocols like the ones from the SPDZ family follow Beaver's blueprint and "just" add some additional magic on top for getting active security. Let's focus on the simple approach of Beaver, since you will already run into problems there, when you reuse multiplication triples:

Assume you have a secret shared values $[x]$ and $[y]$, where the notation $[x]$ means that $x = \sum^n_{i=1}x_i$ and party $P_i$ has share $x_i$.
Let $[a],[b],[c]$ with $c = a \cdot b$ be a secret shared multiplication triple.

To multiply $[x]$ and $[y]$ you compute $[z]$, where $z = x \cdot y$, as follows:

Each party computes $$[d] := [x] - [a] = [x-a]$$ and publishes its share thereof (thus revealing $d$)
Each party computes $$[e] := [y] - [b] = [y-b]$$ and publishes its share thereof (thus revealing $e$)
All parties locally compute $$[z] = [c] + [x]\cdot e + [y] \cdot d - e \cdot d$$ (Note that when we want to add or subtract a public value like $e \cdot d$ to a secret shared value, then only one of the parties adds the public value to its shares.)

Now if you were to reuse the same multiplication triple $[a],[b],[c]$ in another multiplication of some other secret values $[u]$ and $[v]$, then you would reveal $$d' = u - a$$ and $$e' = v - b$$

From this information, a honest-but-curious party could now compute
$$ d - d' = (x-a) - (u-a) = x - u$$
This is clearly bad, since it directly reveals the difference between two secret values $x$ and $u$. The same, with $e$ and $e'$, obviously also works to compute the difference $y - v$.

For this reason it is crucial for the security of the protocol that you use every multiplication triple at most once!


Tamper-proofing log files Problem Overview

I want to securely store log files so the contents are secret, and they can't be modified without detection.

The files will be encrypted using authenticated encryption (AES in GCM mode), with a random IV and symmetric key for each file. The symmetric key will be encrypted using the public part of an RSA key pair. Both the IV and encrypred symmetric key will be included in the additional authenticated data.

This gives me confidentiality, integrity and authenticity - but only for each individual log file.

For example, let's say I have log files 2013-01-01.log, 2013-01-05.log and 2013-02-09.log - an attacker could delete 2013-01-05.log without detection.

I've come up with 2 possible solutions.

Possible Solution 1

The program could maintain an encrypted (and possible RSA-signed) 'counter file', which would contain a sequence number that would be incremented every time we write a new log file. The sequence number would become part of the log filename, and would also be included in the additional authenticated data. We could therefore detect any 'gaps' from missing files.

Possible Solution 2

The program could maintain an encrypted (and possible RSA-signed) 'database file', which would contain the filenames of all previously written log files. We could therefore detect any 'gaps' from missing files.

The Question

I'd like feedback on my 2 possible solutions - do they work, do they need some changed, have I missed anything?

Or are there better solutions to my problem?

"Efﬁcient, Compromise Resilient and Append-only

Cryptographic Schemes for Secure Audit Logging"  (PDF)

gives a publicly verifiable approach that allows fine-grained verification,

but it is in the Random Oracle Model.

The Simple Method:

The verifier and logger start with a seed for a

forward-secure pseudo-random number generator.

To denote a valid ending of a log, put the string of

the next $b$ bits of the PRNG's output into the log.

To add a log entry, get the next $\:b+k\:$ bits of the PRNG's output,

put into the log the encryption of the log entry and the mac of that

ciphertext using the last $k$ of the $\:b+k\:$ bits of PRNG output as the

mac key, then erase those $\:b+k\:$ bits and the previous PRNG state.


How we can create a protocol using Schnorr as identification scheme and a hash function as a puzzle? My question has to do with the creation of a PoWorK( Proof of Work or Knowledge) protocol.How we can create a protocol like this ,using Schnorr as the underlying CVZK protocol and using a hash function (lets say sha256) as the puzzle that is being solved?

In other words :

1) How a P can prove to V that he knows witness w (without revealing), by solving the hash256 and afterwords the V can verify the solution.

2) How a P can prove to V that he did a Proof of Work procedure by solving the hash256 afterwords the V can verify the solution.

It is not clear to me how the P computes the outcome and how the V verifies based on the receiving outcome.

Related question here:
Proving knowledge of a preimage of a hash without disclosing it?
Over at theoretical computer science SE:
Zero knowledge proof for value of a hash function

From the general properties of hash functions, we can not derive such a proof of knowledge. The reason for this is, hash functions are intended to destroy all meaningful structure. In most zero knowledge proofs structures with oneway-trapdoor functions and homomorphic properties are used, because then those proofs are short and elegant. Practical hash functions don't have that. On the contrary, a homomorphic property could be used to find collisions, which shouldn't be possible for hash functions.

For specfic ones, like sha 256, there are ways to get a proof of knowledge, and it is explicitly an example of Zero-Knowledge Using Garbled Circuits
or How To Prove Non-Algebraic Statements Efficiently, by Jawurek, Kerschbaum and Orandi (2013). There is an experimental evaluation as well. The experiment had a result of over 5s for sha 256.

That should cover your first question, but I am not sure what you mean with the second question. In a proof of work you usually have the following steps: 1. The client requests something, 2. the server gives the client a task, e.g. a partial preimage to a hash, 3. the client sends the solution, 4. the server grants the request.

Now, you can replace the 3. step of sending the solution with a proof of knowledge. But that doesn't really make any sense, because the task should be possible to complete within reasonable time (partial preimage, or preimage in a reduced input space), and the server has to know that it is actually solvable. So if the server actually wants to get the solution, he can just calculate it himself. A proof of knowledge only makes sense if the input has to be kept secret from the server, but if he can't find the solution within reasonable time, then this challenge is useless in a proof of work - the challenge has to be solvable within reasonable time.

edit: I have no idea what you mean with your references to the Schnorr identifiation scheme and commited verifier zero knowledge. Those elegant kind of proofs like the Schnorr signature scheme are unusable for hash functions.


Do practical key-less cryptosystems exist? Hopefully the question isn't too broad or off.

Basically, are there any practical, and by practical I mean secure enough that a ciphertext only attack is infeasible, key-less cryptosystems? For example, there's the Caesar Cipher (I'm aware of the fact that it can pass as a special case of the shift cipher with the key = 3, but let's assume that there is no general case of the hypothetical cipher), however, it's very impractical according to the aforementioned definition of practicality.

Sure, use AES with a fixed key. Since the key is fixed, it could be considered keyless in the traditional sense. Someone with only access to the ciphertext could not crack it as long as you use a good mode (say GCM, CCM, or EAX) using proper nonces, IVs, or whatever else is required.

This is security by obscurity as the plaintext is only as secure as the fixed key. Since the fixed key is on the devices, it is only as secure as the security of the devices. A physical security breach could leak the keys and thus destroy security. A "cyber" attack could do the same.

Note though, that this security will not continue forever. IV's will eventually repeat, counters will eventually repeat, etc.


Probability that n is prime such that n fails the Miller-Rabin test N times I'm working through An Introduction to Mathematical Cryptography and one of the exercises asks

  Suppose that we run the Miller–Rabin test N times on the integer n and that it fails to prove that n is composite. Show that the probability that n is prime satisfies (approximately)

  Pr($n$ is prime $\mid$ the Miller–Rabin test fails $N$ times) $\geq 1 − \frac{ln(n)}{4^N}$.

This is assuming that the Miller-Rabin test is 75% accurate and that the probability $n$ is prime is $\frac{1}{ln(n)}$. I think by "failing on a number", they mean they identify the number as prime. (Fail to identify it as composite.)

Based on the assumptions, I find the following:

Let $n$ be "$n$ is prime" and $N$ be "The Miller-Rabin test fails $N$ times". Because the test always fails on a prime, $P(N \mid n)=1$. $P(n)=\frac{1}{ln(n)}$ as above, and $P(N \mid n^c)=(\frac{1}{4})^N$ because the test identifies a composite as prime $\frac{1}{4}$ of the time.

From this, I can use the fact that $P(n \mid N)=\frac{P(N \mid n)P(n)}{P(N \mid n)P(n) + P(N \mid n^c)P(n^c)}$ to find

$$
P(n \mid N)=\frac{\frac{1}{ln(n)}}{\frac{1}{ln(n)} + (\frac{1}{4^N})(1-\frac{1}{ln(n)})}\\
=\frac{\frac{1}{ln(n)}}{\frac{1}{ln(n)} + \frac{1}{4^N}-\frac{1}{4^Nln(n)}}\\
=\frac{\frac{4^N}{ln(n)}}{\frac{4^N}{ln(n)} + 1-\frac{1}{ln(n)}}\\
=\frac{4^N}{4^N + ln(n)-1}\\
$$

But that doesn't seem to get me anywhere. What am I missing here?

Just one step more, your last expression is

$$\frac{4^N}{4^N +\ln(n)-1}=1-\frac{\ln n -1}{4^N+\ln n -1}\geq 1-\frac{\ln n -1}{4^N}\geq 1-\frac{\ln n}{4^N}.$$


What are monotonic and non monotonic access structures in ABE ? While reading Attribute Based Encryption Schemes, I did not quite understand what a monotonic access structure or non monotonic access structures are.

Is there a popular explanation of those terms ? any references ?

My understanding of this is as follows:

Monotonic access structure: if $\mathbb{A}$ is a set of attributes satisfying an access structure $T$, then any $\mathbb{A}'$ such that $\mathbb{A} \subset \mathbb{A}'$ also satisfies $T$. For example, consider $T = A \cap B$, then both $\mathbb{A}=\{A,B\}$ and $\mathbb{A}'=\{A,B,C\}$ satisfy $T$.
Non-monotonic access structure: there exists $\mathbb{A}'$ such that $\mathbb{A} \subset \mathbb{A}'$ and $\mathbb{A}'$ does not satisfy $T$. For example, consider $T = A \cap \neg C$. Then in the previous example, only $\mathbb{A}$ satisfies $T$.


What is the difference between exhaustive search and factorization in relationship to determining a key? It seems to me an exhaustive search would simply try to use all the possible bit combinations of a key, while factorization is some mathematical formula for determining the key? When discussing the NSA's cryptography "breakthroughs" some articles discuss factorization as the contributing factor. However, others go further and mention that they have only found a flaw in how some programs use factorization. I guess I'm not understanding how that term should actually be used as it relates to cryptography.

Your summary of exhaustive search is essentially correct; the attacker just tries every possible key until he finds one that works.  This works against almost any cryptosystem (exceptions: OTP, secret sharing, quantuum cryptography).  It's not practical against any modern system (mostly because 'has a key too large to be brute forced' is an essential attribute of any modern system).

Factorization is not a generic attack; instead, it is attack on certain public key crypto systems (mainly RSA).  With RSA, the public key contains a composite number; if someone where again to derive its factorization, they could reconstruct the private key.  That is, if someone could factor, they could break RSA.  However, a breakthough in factorization would affect only RSA (and a handful of other systems that are not used much in practice); there is no known way to use factorization to attack (say) AES, SHA-2 or Elliptic Curve Cryptography.


Does keeping a public key private or using multiple encryption help? I recently had a discussion with a friend of mine about cryptography. As we are both no experts, I thought that I could better resolve are dispute here.

My friend said that when he used public key cryptography in the past, he used to keep his public key private too. Only giving it out to people that really needed it (i.e. don't post it on the internet, but giving it out personal to a select group of people). He said that this made it harder for third parties to break the encryption that do not have the public key. I argued that he could have better used a symmetric cipher instead of this scheme, as it is a lot faster and with sufficient key size just as secure. So two questions arise here:

Does keeping your public key private give you any more security?
Does this scheme have any advantages over a symmetric scheme?

Also he said that he used to combine different ciphers and run them a random amount of times. Only the other party knows how many times and what cipher combination. He said that it not only makes the encryption stronger by enlarging the effective calculation time, but it also introduces a human factor, that is someone has to think this out and make the decision to try different ciphers different amounts of times. I argued that this is true, but unnecessarily complicated, because choosing a large enough key size for a single cipher will be just fine (can cost thousands of years), even for military security. So:

Are there any REAL benefits of running different ciphers for random amount of times to try to confuse the attacker? Or is this just unnecessarily complicated?

To clarify:

With military security I mean that, at the current moment, it is impossible to break the encryption, even for governments institutions (like the NSA).
To better illustrate my question: instead of giving out your public key to a select group of people, you give it out to one individual. Furthermore, you can be sure that he knows how to handle a key ring and that he has no benefit from leaking your public key (i.e. he has no benefit from leaking the clear text you messaged to him)

Keeping the public key private:

Does not help in protecting data.
Does not work: depending on the algorithm, the public key could be recomputed from the exchanged messages.
Does not work: something which has been communicated to more than two people cannot be considered secret anymore. Especially since public keys are commonly written everywhere without any particular protection.
Does not work: people who would bother trying to crack your friend's private key would be people interested in your friend's secret, so chances are that they already have the public key (the attacker is one of your friend's friends, or already has hijacked the computer of one of your friend's friends).

As for cascading ciphers, it just makes processing slower, and more complex, both activities being ultimately detrimental to security (way more than the off-chance that one of the algorithms is actually weak, which does not happen often as long as none of them is a homemade cryptosystems -- these, of course, are almost always laughably vulnerable).

And "military security" is not stronger than normal security; it is just usually much more expensive.


What's the `ticket_age_add` and `obfuscated_ticket_age ` used for in TLS 1.3 In RFC, I only find such description:

This addition prevents passive observers from correlating connections unless tickets are reused

ticket_age_addis generated randomly and obfuscated_ticket_ageis computed by adding obfuscated_ticket_age to aging time of ticket.

In my opinion, cause the PSK is sent in plaintext and it need contain the aging time which is also in plaintext, man-in-middle may know the aging time of this ticket, so we need use  obfuscated_ticket_age not the aging time directly.

Question1:
If we don't want the man-in-middle know the aging time，we can remove the  obfuscated_ticket_age simply, right? Why the server need this information ?Just using it to check the ticket's real lifetime ?

Question2:
If the client using the ticket's real aging time not the obfuscated_ticket_age, what is the harm for endpoints if a man-in-middle knows the the ticket's aging time ?

The point of these parameters is to encode the time since the ticket was issued.  This time is necessary so that a server can bound its risk of 0-RTT replay to a moderately narrow window.  The main problem with 0-RTT is the potential for a ClientHello and subsequent 0-RTT data to be captured and replayed.

If a client's 0-RTT ClientHello is replayed, having the time since the ticket was issued allows the server to reject 0-RTT quickly when the time is too far different from its own expectations.  This limits the time over which a ClientHello can be replayed, making other anti-replay techniques more feasible.  For instance, a server might remember every ClientHello it receives over a short interval, though more efficient mechanisms are definitely possible.

When a server receives a ClientHello with 0-RTT it can use the obfuscated_ticket_age to determine how old the ticket is from the client perspective.  The server compares this with its own view of the ticket age - it remembers the time it issued the ticket and the value of ticket_age_add and can use those values to recover both its own view of elapsed time and that of the client.  (A server might also remember an estimate of the round trip time between it and a client to allow for transit delays in its assessment.)

If the two times differ by too much, the server can reject 0-RTT quickly and efficiently.  The server needs to allow a little slack for things like relative clock drift, errors in its estimation of the round trip time, and retransmission delays from the transport protocol.  Values like 5 to 10 seconds either side are expected.

The ticket_age_add field is a simple form of encryption, equivalent to a one time pad.  ticket_age_add is a random value (or hard-to-guess pseudorandom value) that is added to the elapsed time from the client.  This encryption ensures that the client doesn't expose the time since the ticket was issued to anyone but the server.  If this wasn't obscured in some way, passive observers might use the time to link this connection attempt with a previous connection.  This value is added to the actual time that has elapsed (modulo 232) to get obfuscated_ticket_age.


Is it possible to verify and relay an encryption key with a trusted but transparent third party? I'm wondering if it would be possible to implement this functionality with a trusted but transparent third party (maybe an Ethereum smart contract?):

Bob has an encryption key. Alice has the encrypted data and wants to buy the key from Bob.
Bob sends the key to the smart contract (SC).
Alice sends some ether (and perhaps the encrypted data or some function on it) to the SC.
The SC verifies that the key decrypts the data properly. If it doesn't, it halts.
The SC sends Bob the ether, and Alice the key.

The main issues I'm finding when I'm trying to think of a solution are:

How does the third party verify a decryption is correct?
Is it possible for the third party to verify this decryption without revealing it, since it is transparent? I know of zero knowledge proofs, but am not sure of how they could apply here.

Thank you!

I'm not sure what you mean by transparent.
With a trusted third party what you ask is trivial. But with etherium I believe you can't, the key would become public there is nothing secret on the blockchain.

If we wanted our own distributed third party this can be done. You can perform secret sharing and send part of the key to each member of the distributed escrow. They can then perform shared computing to verify the secret without revealing the secret.


How to explain just how secure AES is in layman terms? I have a rather particular classmate who wholeheartedly believes that there isn't such a thing as reasonably secure cryptography and that most people can steal encrypted data. I have attempted to explain (with must frustration) the security of AES. I often attempt to make points about how certain implementations and stream ciphers can result in data leaks, but AES in practice with proper implementations is feasibly unbreakable.

I am trying to find a way to present that AES is secure when everything is done correctly by developers. Any help to explain this to someone who is not cryptographically inclined would be a great help.

I have attempted to explain the math and just how large the keyspace is; the amount of energy required to bruteforce a key; econmical impacts of cracking the cipher, and with no avail.

Some audiences react positively to this line of arguments:

Mathematical attack are unlikely: the AES block cipher as a mathematical construction has been scrutinized for 15 years by many bright brains, yet what they published leaves trying all the keys as the best attack within a small factor (less than 4 for the weakest AES-128), assuming random and secret keys. Anyone with a better attack would gain high social status by revealing it. And there is positive mathematical proof that attacks against mode of operations (AES-CTR..) are impossible without attack on the block cipher. We can conclude that it is unlikely that there exists a good mathematical attack; and even more unlikely that a particular attacker knows about it.
Brute force attacks are impossible with our current knowledge: there simply are too much keys to look among. Using all the money (easily, hundreds million USD) and energy that was ever used for bitcoin mining, we could perhaps break a 95-bit key. Breaking a 128-bit key requires $2^{33}$ times more effort; that's well over the ratio of cost of manufacturing all the cars now on earth, to the marginal cost of manufacturing one.
Remaining attacks are those on usage or implementation: the key can leak from its holder, or be poorly chosen, or be derived from a weak password, or be poorly derived from a fair passphrase; the key can leak thru compromise of the machine on which it is stored or used, or side channels including timing; there might be implementation goofs, including in random generator, and mode of operation. These are very real threats, and practitioners know that humans are bad at keeping secrets (they often let it leak or/and vanish), programmers often goof or make poor choices (especially when it comes to transformation of password/passphrase to key), and it is extremely hard to be highly confident that an implementation is fully immune against attacks by an adversary that is physically close to the machine, or had physical or logical access to it (including software, design of the hardware).

An honest, knowledgeable and prudent practitioner can tell that hardware AES implementations (including those with AES-NI) are verifiably immune from timing attacks, which is the only known side channel that can be exploited from a large distance, assuming the implementation is not intentionally rigged; thus s/he's confident that save for a compromise of the key, the machine or its software, a machine using such hardware AES implementation is safe from any kind of attack from distant adversaries.

Note: I have found that admitting flatly that attacks on usage and implementation are possible, and happen, helps convince that mathematical and brute force attacks do not, and that a particular implementation is safe enough.


How does encrypt-then-MAC protect from CCA? I am an application developer, implementing client-side crypto to protect data that is then transmitted to be stored on a server. The application uses AES with CBC mode with a resulting encrypt-then-mac HMAC to authenticate.

The process looks something like this:

key_material = kdf(password, salt)
mac_key = first_half(key_material)
enc_key = second_half(key_material)

iv = random_bits()
ct = aes_cbc(plaintext, iv, enc_key)
mac = hmac_sha256(ct, iv, mac_key)

This results in a ct, iv, and mac that are then transmitted to the server. The server then delivers that information back to the client each time the application starts (and user enters their password) in which the whole process is then reversed for decryption.

Validate mac. If validation fails, abort with error.
Decrypt to plaintext with enc_key, iv, and ct.

I understand the need for the mac in order to validate the authenticity of the message before the application proceeds to decrypt the plaintext to display to the user.

However, I am having trouble understanding how authentication protects against anything else. I have read that authentication will protect against things like Chosen Ciphertext Attacks (CCA). My understanding of a CCA attack is:

  A class of attacks in which the attacker modifies encrypted traffic in
  specific ways and may learn plaintext by observing how the decryption
  fails.

If an attacker obtains access to the stored ct, iv, and mac don't they have everything that they need to "observe how the decryption fails"?

From my understanding, mac validation is an application implementation. The attacker doesn't necessarily have to use my application to observe how the decryption fails. They could just write their own application that doesn't do the mac check (or just modify my open source application and remove the mac check).

Am I missing something here? How does authentication (more specifically encrypt-then-mac) protect against attacks like CCA?

What CCA basically means is that attacker supplies for decryption any ciphertext he/she wants and observes the reaction of the system. This reaction can be used to infer information about plaintext/key. Many dangerous attacks are based on changing some bits in the ciphertext and observing how when and how the system fails. This is often enough to partially or fully recover plaintext or key. What authenticated encryption (particularly encrypt-then-mac approach) basically does is prevent attackers from being able to change ciphertext. Doing so requires recomputing of mac, which by definition can't be done without knowing the mac key, otherwise decryption immediately fails due to incorrect mac, and as the system doesn't know anything about the plaintext at this point, the attacker can't possibly learn anything too.

Attacker's own application is useless in this case, as without the key itself any decryption failure just points to one and only obvious reason - wrong key.


A modified question of Hazay & Lindell's Efficient Secure Two-Party protocols Book Based on the question proposed on page 27, we propose a modified question as follows:

Suppose the protocol is based on Paillier cryptosystem and $P_2$ has generated related public and private keys ($P_2$ publishes its pub key). Then, $P_1$ will encrypt $x$ using the public key and send it to $P_2$.

Considering this scenario, is it secure in the semi-honest model?

Promoting my comment to an answer: Encryption hides information from someone who doesn't know the decryption key. In your case, $P_2$ knows the decryption key, and can therefore learn $x$. This is really no different than sending $x$ in the clear to $P_2$.

Note that this is the strange example from the book that is secure in the malicious setting but not in the semi-honest setting. Adding the encryption step doesn't change that. Your modified protocol leaks $x$ to a semi-honest $P_2$ even when its input is $y=0$, so the protocol is not semi-honest secure. But your modified protocol is secure against malicious $P_2$ since malicious $P_2$ always learns $x$ in the ideal world without loss of generality.


Is it possible to predict a randomly generated BigInteger that uses Java's default Random library? I've seen it posted on different forms here and here that explain how java.util.Random library uses a linear congruential pseudorandom number generator which can be cracked using two values. Can this type of exploit go one level deeper and guess the nextByte data used to fill in the rest of a BigInteger value?

private static Random generator = new Random();

public static String uncrackableRandomNumber() {
    return new BigInteger(128, generator);
}

A snippet of the additional layer of byte generation using java.util.Random (rnd).

public BigInteger(int numBits, Random rnd) {
      this(1, randomBits(numBits, rnd));
  }

private static byte[] randomBits(int numBits, Random rnd) {
  if (numBits < 0)
    throw new IllegalArgumentException("numBits must be non-negative");
  int numBytes = (int) (((long) numBits + 7) / 8); // avoid overflow
  byte[] randomBits = new byte[numBytes];

  // Generate random bytes and mask out any excess bits
  if (numBytes > 0) {
    rnd.nextBytes(randomBits);
    int excessBits = 8 * numBytes - numBits;
    randomBits[0] &= (1 << (8 - excessBits)) - 1;
  }
  return randomBits;
}

The first two numbers are: 233458857748780331814340414981023411537 and 141610568161066839752374346774468879751, how can I determine the next number given only this information?

Isn't the answer plainly yes by simple deduction?  The BigInteger constructor is simply a linear function as: BigInt ~ F(LCG).  Ergo if LCG is predictable, BitInt is too. It's not much deeper.

Could you do BigInt ~ F(SecureRandom)?


Difference between a nonce and IV I know the generic difference between a nonce and an IV. I am specifically looking for a clarification on these terms as used in the "Evaluation of Some Blockcipher Modes of Operation" by Phil Rogaway. In that when describing the block cipher modes for e.g. CBC he says the following (table in page 5) --

  Confidentiality is not achieved if the IV is merely a nonce, nor if it is a nonce enciphered under the same key used by the scheme, as the standard incorrectly suggests to do.

I don't understand the difference between the IV and nonce in this context. If I choose the nonce randomly won't it be the same as an IV? What am I missing here?

With CBC mode the initialization vector is referred to as IV, because it is not nonce. There are ways to construct nonce so that it does not meet the needs of CBC mode. Random IV is one generation choice which is usually fine.
Nonce can also be a counter, which is not ok here.

Definitions

Nonce means number used once.
IV means initialization vector.

CBC mode security

For security of CBC mode (SemCPA in this case), it is necessary that the IV is unpredictable, prior use of IV. However, once IV is used, the value does not need to be kept secret.

One way to generate IV is to generate random numbers. For the CBC IV size (128 bits)  it is extremely rare to get IV value which is same than one of the previously used *IV*s. In addition, random numbers are by definition unpredictable.

Such IV values are nonce as well, as the numbers are used only once (with high probability unless the number of encryptions with the same key is very large).

However, there are also other ways to generate nonce. Once of common ways to generate nonce is to use increasing numbers (increment with 1 or use linear feedback shift register). Such approach fullfils the necessary requirements for nonce, but fails to meet needs (unpredictability) of IV for CBC mode.
(In Rogaway's paper, "Random IV" is used for Random IV generation and "nonce IV" for these other ways of generating nonce.)

The Rogaway's paper is concerned investigating the security provided by AES usual block cipher modes of operation if they have been implemented as defined in papers by NIST. NIST SP 800-38A is concerned with CBC, CFB, OFB and ECB modes.
NIST SP 800-38A (Appendix C) suggests two ways to generate IV for CBC mode, Random IV and nonce-based scheme using forward cipher function ($C = E_K^R(P)$) to generate IVs.

This paper by Rogaway points out that the nonce-based scheme using forward cipher function does not provide intended security.

Random IV

When using Random IV's, remember that if you generate $2^{64}$ IV's, there is around 50% possibility that not all IVs are unique. For this reason, you need to make sure that the amount of encryptions with single key is not too large.

And... If the random number generator is not a good one, then unpredictability can be violated. So generally you should make sure that a cryptographically secure RNG is used for IV's.


Brute-force attacks practical limit My question is about practical limit for brute force attacks. As I know 3DES with 56 bits key length can be broken via brute force. I also heard the same news about 64 bit key length (correct me if I am wrong).

My question is about the minimal length of the key that can be considered as a non breakable by classical computers (not quantum ones). I have 90 bits in my mind but unfortunately don't remember the reasons for the number. I.e. it's impossible to perform $2^{90}$ operations on a classical computer in a reasonable time. Is it correct?  Could somebody provide me explanations for the number (90) or provide another answer.

Obviously the answer is about the attack potential by adversaries, such as large governments or organisations. And the truth is: we don't know. The attack on SHA-1 shows that the NSA is certainly not the only large organisation to worry about. Anybody with enough money to rent a server farm could be your adversary.
In the end, we don't really know. But there are the Lenstra equations and the site keylength.com which can be used to put in the right numbers. Entering a symmetric key size of 90 will show that 2033 is about the time that this key may be cracked using ga 50M machine, given that Moore's law holds. That's not that far away anymore. Note that single processor speed is not what Moore's law is about; it doesn't seem to be slowing down yet.
To protect against quantum computing you'd have to double the key size of symmetric algorithms in the end. But how fast quantum computers evolve is anybody's guess. Currently there have been some break-throughs with e.g. the Dutch government spending heavily on research at Delft. However a machine that could attack large keys - or anything heavier than a (normal sized) Sudoku - still seems some way off.


Why not use chacha derivatives (BLAKE, rumba) to make an [H]MAC for use with chacha? Why use poly1305? Why not use chacha derivatives (BLAKE, rumba) to make an [H]MAC for use with chacha? Why use poly1305?

This question is especially interesting considering...

  "The security of Poly1305[...] is very close to the underlying [...]
  block cipher algorithm." -Wikipedia

So... why not reconfigure chacha as a Merkle–Damgård like construction. (Or a  HAIFA construct, as is done with BLAKE.) Then do a standard H(key || H(key || message)) for effective HMAC? Then, from here, you have CHF, MAC, and AEAD, all from one cipher.

OK, so the core ChaCha primitive (for any fixed number of rounds) is a function $\operatorname{ChaCha}: \{0,1\}^{256}\times \{0,1\}^{64}\times\{0,1\}^{64}\to \{0,1\}^{512}$ which is believed to be a secure PRF when the first input is the key.

So now that we know what ChaCha is, for the three desired functionalities:

MAC. Of course a PRF is also immediately a secure MAC,  but ChaCha only accepts 128 bits of input. So you could only MAC messages that are exactly 128-bit long, which isn't practically useful in itself. So this would mean you'd have to build a secure MAC around ChaCha which is certainly possible but needs to be standardized so everyone is doing the same and can talk to each other.
 Possible variants include running ChaCha in CBC-MAC mode, in OMAC-mode, with Poly1305, or using a using a cascade-style construction where a subset of the output is the next iteration's input.
 One could also build a Merkle-Damgard HMAC out of ChaCha but there you face the significant problems, that

each iteration only consumes 128-bit of data,
the HMAC security proof requires a PRF that can use either input as the key which doesn't immediately follow from our above model, and
ChaCha only takes 384-bit of input but produces 512-bit, how do you map this for the iteration?

As for why it's paired with Poly-1305 that mostly due to the fact that this construction is even faster than any of the above other options because the evaluation of Poly1305 is one polynomial multiplication per 128-bit of data, much less work than 20 ChaCha rounds. The speed estimate is 125 cycles / byte on 8-bit low-end platforms and much faster on wider platforms.

For Collision-Resistant Hashing, see my other answer.

AEAD. Again, using a mode like CCM or EAX you can build an AEAD scheme from any PRF like ChaCha. Or alternatively you can use the more efficient ChaCha-Poly construction, but there's no "immediately obvious way" to build AEAD from a PRF short of making use of predefined modes like the above.


Stream cipher with an additional integrity stream? I want to use a stream cipher to encrypt a continuous bitstream. Additional to that, I want to generate an additional stream to guarantee the integrity of the ciphertext.

stream a: ciphertext.
stream b: integrity check on stream a.

I am aware of authenticated encryption where the MAC can be accumulated and sent. I want to avoid that.

Is it possible to do this by encrypting the same plaintext using a different algorithm, key or iv? Will that actually protect against say bit-flip attacks? Does it cause any vulnerabilities?

Is there a better (preferably cheaper) way to do this?

Note that this has to be done in hardware and I am extremely limited on energy so I can't add any sort of control logic.

Break your stream into chunks.  Use an AEAD for each chunk using the chunk sequence number as a nonce.  Anything else is going to have at best the same effect, but will be convoluted, full of holes for the first umpteen drafts, difficult to implement, and nonstandard, and will have the effect of making cryptographers look at you like you have three heads.

Or, use a system that was already designed to do this (in particular, STREAM).


How to derive a passphrase from a hash? I'd like to generate a passphrase derived from a hash fingerprint. The passphrase consists of short and human-pronounceable words from a phonetically-distinct wordlist. The derivation is a one-way function and it is acceptable for this application to lower the security against collision attacks/reduce the keyspace.

For example, a function that map 5a1138375b1c38ab49800911e6e533e2b3e60e314a042c5bca01324dc75bc710 to daycare qualified irregular plastic and that has a collision resistance as high as possible considering the reduced keyspace of the passphrase.

For this application, is it OK to use a pseudo-random number generator with the hash value as the seed to select the words of the passphrase? Are there better alternatives?

Edit: Below is a visualisation (Mathematica source) of using base conversion which is not a divisor of hash size (in this particular case $|wordlist|=5$ with 3 words derived from a 8-bit hash).

One possible solution is to use base conversion, and use the resulting "digits" of that base as index in the dictionary.

As that's probably a bit too abstract, so let's use some pseudo-code:

words = []
left = hexToNum(hash)
base = size(dictionary)
while (left > 0) {
    wordIndex = left % base
    word = dictionary[wordIndex]
    words += word
    left = left / base

The hash is treated as a positive number. This number is then converted to a number of digits using the size of the dictionary as base. Each "digit" (which is really just another large number between 0 and the dictionary size) is treated as index into the dictionary. Then we just perform a simple lookup and concatenate the words found.

As the left variable has a very big number value, you might have to use a "BigNum" library (a 64 bit integer would be too small). Most language or cryptographic API's will supply one. To speed things up a bit you might want to look for a function that performs divide and remainder in a single step, because that will incur fewer CPU operations than doing the division and remainder calculations separately.

As mentioned in the comments, there is no PRNG required. A PRNG is useful for seed expansion, but that doesn't seem required; only just conversion seems required. As the hash already is well distributed you can use the leftmost bytes of the hash to use fewer words.


On the privacy of perfect hash functions I'm digging into the several algorithms for building (Minimal) Perfect Hash Functions. It seems that the recent works provide quite a few very efficient algorithms.

However, I'm wondering how a (M)PHF behaves in case of unsuccessful searches and what level of privacy can guarantee:

What happens if a user computes the hash function over a key which wasn't in the key set used for the creation of the hash function? What result will be returned?
The user wants to run a membership test of $x$ over a set $S$ in a privacy-preserving way. He computes the hash of $x$: $H(x) = i$, and then asks the server to return the key in position $i$. Let's suppose $x$ is not in the key set, did the user leak anything about $x$? What information could the server obtain knowing that the user asked for a key in position $i$?

EDIT:

Is there any perfect hash function which allows membership tests? Given the phf $H$, a user $U$ would like to test whether $x$ is in the key set.

The definition of perfect hash functions do not have any security/cryptographic requirements. For example, the hash function that simply outputs the first n bits of any string is a perfect hash function on the set of n bit strings. Obviously this function does not hide the input at all.

So the answer to your questions is that it depends on the hash function. It being a perfect hash function alone (minimal or otherwise) does not guarantee any privacy at all. Neither does it say anything about what happens outside of the set for which the function is perfect. That means if the users hashes a value outside of this set it may well result in a collision with value in the set. Such a collision is easy to construct for the hash function I mention above.

On the other hand, if the reason you want to use a perfect hash function is that there are no collisions, you might as well use a cryptographic, collision resistant hash function instead. In this case there is basically no way for user to find a value outside of the set that collides with one in the set.

If using a collision resistant hash function in your protocol is enough for secure private set-intersection is a more complicated question. It essentially depends on your security assumptions and the flavor of PSI you want: Is the server malicious? Is the client? Should both parties learn if there is an intersection or not?


Tls protocols: is the simple diffie hellman key exchange still used these days? Or did it mostly get replaced by ecdh for key exchange and rsa for authentication ?

In TLS, Diffie-Hellman (non-EC) can be used in TLS_DH_* ciphersuites ("static DH"), and in TLS_DHE_* ciphersuites ("ephemeral DH").

Static DH occurs when the server's certificate contains a public DH key. This never gained traction; historically, the US federal government promoted use of DH for key exchange because, at that time, RSA was still patented. However, nobody in practice does that anymore, except maybe in some old, hidden systems in some US federal organizations, and not for general public consumption.

Ephemeral DH is quite widely supported. For instance, my own Web server uses the default SSL configuration of Apache+mod_ssl on Ubuntu 16.04, and offers the following protocol versions and cipher suites:

  TLSv1.0:
     server selection: uses client preferences
     3-- (key:  RSA)  RSA_WITH_AES_128_CBC_SHA
     3f- (key:  RSA)  DHE_RSA_WITH_AES_128_CBC_SHA
     3-- (key:  RSA)  RSA_WITH_AES_256_CBC_SHA
     3f- (key:  RSA)  DHE_RSA_WITH_AES_256_CBC_SHA
     3-- (key:  RSA)  RSA_WITH_CAMELLIA_128_CBC_SHA
     3f- (key:  RSA)  DHE_RSA_WITH_CAMELLIA_128_CBC_SHA
     3-- (key:  RSA)  RSA_WITH_CAMELLIA_256_CBC_SHA
     3f- (key:  RSA)  DHE_RSA_WITH_CAMELLIA_256_CBC_SHA
     3f- (key:  RSA)  ECDHE_RSA_WITH_AES_128_CBC_SHA
     3f- (key:  RSA)  ECDHE_RSA_WITH_AES_256_CBC_SHA
  TLSv1.1: idem
  TLSv1.2:
     server selection: uses client preferences
     3-- (key:  RSA)  RSA_WITH_AES_128_CBC_SHA
     3f- (key:  RSA)  DHE_RSA_WITH_AES_128_CBC_SHA
     3-- (key:  RSA)  RSA_WITH_AES_256_CBC_SHA
     3f- (key:  RSA)  DHE_RSA_WITH_AES_256_CBC_SHA
     3-- (key:  RSA)  RSA_WITH_AES_128_CBC_SHA256
     3-- (key:  RSA)  RSA_WITH_AES_256_CBC_SHA256
     3-- (key:  RSA)  RSA_WITH_CAMELLIA_128_CBC_SHA
     3f- (key:  RSA)  DHE_RSA_WITH_CAMELLIA_128_CBC_SHA
     3f- (key:  RSA)  DHE_RSA_WITH_AES_128_CBC_SHA256
     3f- (key:  RSA)  DHE_RSA_WITH_AES_256_CBC_SHA256
     3-- (key:  RSA)  RSA_WITH_CAMELLIA_256_CBC_SHA
     3f- (key:  RSA)  DHE_RSA_WITH_CAMELLIA_256_CBC_SHA
     3-- (key:  RSA)  RSA_WITH_AES_128_GCM_SHA256
     3-- (key:  RSA)  RSA_WITH_AES_256_GCM_SHA384
     3f- (key:  RSA)  DHE_RSA_WITH_AES_128_GCM_SHA256
     3f- (key:  RSA)  DHE_RSA_WITH_AES_256_GCM_SHA384
     3f- (key:  RSA)  ECDHE_RSA_WITH_AES_128_CBC_SHA
     3f- (key:  RSA)  ECDHE_RSA_WITH_AES_256_CBC_SHA
     3f- (key:  RSA)  ECDHE_RSA_WITH_AES_128_CBC_SHA256
     3f- (key:  RSA)  ECDHE_RSA_WITH_AES_256_CBC_SHA384
     3f- (key:  RSA)  ECDHE_RSA_WITH_AES_128_GCM_SHA256
     3f- (key:  RSA)  ECDHE_RSA_WITH_AES_256_GCM_SHA384

As you can see, there are quite a lot of DHE suites here. The server's certificate contains a public RSA key, so all the DHE suites are tagged DHE_RSA, which means: "the server sends DH parameters, signed with its RSA key".

Now, that the server offers DHE ciphersuites does not mean that they actually get used. As shown above, my server follows the client preferences, i.e. uses the first ciphersuite it knows of among the list sent by the client, during the initial TLS handshake. Thus, if the client supports DHE and ECDHE ciphersuites, but sends the ECDHE suites first, then the server will choose one of these ECDHE suites.

Moreover, modern Web browsers tend to drop DHE support. On my machine (a macOS Sierra laptop), I have three up-to-date browsers (Chrome, Firefox and Safari), and none of them offers DHE cipher suite support (all happily negotiate ECDHE_RSA if the server supports it, but fall back to plain RSA key exchange if the server does not support ECDHE). In that sense, DHE ciphersuites are an obsolescent feature. Take care that not all TLS is about Web browsers talking to Web servers; there are a lot of applications that also use TLS, and do not necessarily follow the browser trends. Moreover, modern Web browsers are automatically updated, so they are always "cutting edge", while servers and applications can lag for quite some time (many years even). Still, it can be expected that TLS libraries slowly deprecate DHE ciphersuites, or possibly drop support altogether, since ECDHE ciphersuites are more efficient (my own TLS library, for instance, supports ECDH and ECDHE but never supported DH or DHE).

Summary: DHE ciphersuites still work on a number of existing servers, but don't see much usage in practice when clients are Web browsers, and support is expected to dwindle and disappear over time. As you say, indeed, DHE was replaced by ECDHE.


Computational binding implies Perfect hiding? Given a commitment scheme which is computationally binding (based on some conjectured hard problem, say), does it also imply that the scheme is unconditionally hiding?

My idea was: Since the scheme is computationally binding, it can be broken by an unbounded adversary, who can produce two openings to the same commitment. But this would make the scheme perfectly hiding, because even an unrestricted attacker cannot distinguish between the two (or more) openings of the same commitment by any means.

Is this correct? If not, are there any schemes that prove otherwise?

This is not correct. It could be not binding since you can open a commitment into two options. You can quite easily construct such a scheme artificially. For example, take any perfectly binding scheme $C_b$ and any perfectly hiding scheme $C_h$. Then, commit to a message $m$ by committing to $C_b(m)||C_h(0)$ or by committing to $C_b(\overline{m})||C_h(1)$. Then, when you decommit, if the perfectly hiding part is 0, take the message $m$ in the perfectly binding part. In contrast, if the perfectly hiding part is 1, take the complement of the message in the perfectly binding part.

Clearly, this is a computationally binding scheme only, since an all-powerful committer can break the binding of the perfectly hiding part, and so can recommit to either the message or its complement. In addition, the scheme is clearly only computationally hiding as well.


Does Shamir Secret Sharing provide integrity? Shamir secret sharing splits into t number of shares with a t-threshold. However, I can find no information online if this scheme provide integrity (or authentication for that matter, which I assume it does not).

Can an adversary forge a share? If not, what hard problem is he faced with. Is it due to the share should be indistinguishable from random (psuedorandom)?

By Lagrange interpolation...

  Does Shamir Secret Sharing provide integrity?

No

  Can an adversary forge a share?

Yes


How to generate own secure elliptic curves? I know that the algorithm used to generate the Brainpool curves and the NIST curves is published. The algorithm should be this one (RFC5639 Appendix A). From what it looks like it's rather slow to find secure parameters.

After some research I've also found "Efficient Algorithms for Generating Elliptic Curves over Finite Fields Suitable for Use in Cryptography" by Harald Baier (in fact it's a PhD thesis I think) on the generation of secure elliptic curves. I've also googled around and found a tool that actually generates such curves (using this algorithm I think). From an efficiency point of view this algorithm looks faster than the NIST's one.

Now my question:
Are the above two algorithms the only ones (published) for generating safe elliptic curves or are there other ones?

Of course there are others.  Of interest might be the paper 'Efficient ephemeral elliptic curve cryptographic keys' by Mieli and Lenstra, which claims to generate fresh Elliptic Curves sufficiently quickly that they can be created on the fly for a single ECDH exchange, and then discarded.


Is AES's parity key-dependent? Is the parity of the permutation of the set $\{0,1\}^{128}$, defined by AES encryption for a certain fixed key, dependent on this key?

DES, and any pure Feistel cipher, has even parity for any key. That's less clear for AES, and of no practical importance since parity of an arbitrary permutation can not be determined until $2^{128}-2$ correspondences are known, which is infeasible. That would however be a concern in the context of this comment, considering a reduced AES variant.

AES transformation can be viewed as a sequence of invertible transformations each processing only a small part of the state. All these transformations would be even, and so is the entire AES for any key (see also this question).


Incremental RC4 algorithm? I am currently analysing a client-server application which apparently uses RC4. I've got the secret key and nonce and I was very surprised about the approach they encrypted the packets.

Since I am no cryptography expert I will explain what I did so that it works.

I created a string with the full key (nonce + secret) and I append all the unencrypted bytes without clearing it at any time
I RC4 the whole string (which obviously grows over time)
I slice the resulting string so that all old bytes will be cut and only my "new bytes" are left

I can't imagine the server side maintains the whole byte history for every connected client, hence I wonder if it's some sort of RC4 algorithm / modification or if this is a custom implementation

If I understood you correctly, the protocol you are analysing doesn't reinitialize the encryption before encrypting, so it seems like it is encrypting everything it send yet and sends only the part that "is new".

To answer your question, let's take a little excourse into stream ciphers (as RC4). These ciphers basicly generate a stream of random numbers which are then xored with the plaintext. To decrypt, you have to generate the key stream again and then xor it with the ciphertext.

$C = P \oplus K$

$P = C \oplus K$

($C$ is the ciphertext, $P$ is the plaintext, $K$ is the keystream and $\oplus$ is XOR)

One property of such ciphers is that to en- or decrypt one section is that you just need the related section of the keystream. So, in your protocol, following will likely happen:

Client-Side:

Calculates $K_{0}$
Sends $C_0 = P_0 \oplus K_0$
Calculates $K_1$
Sends $C_1 = P_1 \oplus K_1$

Note that the client doesn't need $K_0$ nor $P_0$ to encrypt $P_1$.

Server-Side:

Calculates $K_0$
Recieves $C_0$ and decrypts it using $P_0 = C_0 \oplus K_0$
Calculates $K_1$
Recieves $C_1$ and decrypts it using $P_1 = C_1 \oplus K_1$, the server doesn't need $K_0$ nor $P_0$ to decrypt $C_1$, so it doesn't have to do the operations you did while reverse engineering.


Big data and modern crypto systems Throughout history, some cryptographic systems were broken by finding patterns in encrypted messages (like frequent chars in a particular language), and thereby discovering the cipher. These classic systems, which relied on algorithms unknown to the attacker, were broken by analyzing the messages and detecting patterns. This allowed attackers to induce the algorithm that was used.

The security of modern cryptography is based on a large key and applying non-reversible mathematics to a message to obtain an encrypted message. In these modern systems it is impossible to apply reverse engineering to a message because it requires more computational capacity than available.

Since there is currently a lot of storage capacity to store an giant amount of encrypted messages, knowing that it was generated with the same key and the same algorithm, it is not possible to analyze them, for instance by finding repetitive patterns, to be able to deduce the key?

In general, no, you won't be able to find the key. The amounts of possible permutations that may be used by a block cipher is staggering. It's much higher than the key space itself. So without somehow breaking the algorithm you're out of luck.

Many cryptographic attacks require staggering amounts of storage to be even reasonably successful in bringing down the security of a cipher significantly. In that regard the increase of storage capacity is certainly beneficial. More storage capacity can certainly aid cryptanalysis. But that's something different as having a lot of pre-generated ciphertext.

Having lots of ciphertext can certainly aid attacks. Those attacks are however not so much on the block cipher itself - and, by implication the key - but on the mode of operation. Many modes of operation have maximum inputs or restrictions on their use. There are certainly protocols do not sufficiently take these into account. This can lead to repetition of blocks being used as input for the block cipher; this information can be used to leak information about the plaintext (rather than the key).

Stream ciphers are possibly more vulnerable against this kind of attack. There is no proof that these ciphers are secure so finding a pattern in a stream cipher may be somewhat easier than finding one in a block cipher. It's still not all that likely that you'd find a key though, other properties (such as the key stream being biased) are more likely to fail first.

It's very unlikely that you can find the key without performing an explicit attack on the cipher. Just looking for patterns isn't going to help you. Mercury isn't rising.


Avalanche effect sample size With a fixed key size – key has 128 bits, while block size is 8 byte – how do I calculate how many different keys and texts I have to test for an cryptanalytic statistics study?

Differently worded: I am planning to encrypt multiple samples and see how many bits have changed, compared to the input block. Finally I plan to create a Histogram and get conclusions. If the cypher algorithm is good, half of the bits should have changed (50%).

The problem is that I do not know how many samples I have encrypt to gain a good statistical foundation. How many blocks do I have to (or should I) encrypt, and what formula should I be using?

You can use the Frequency test of the NIST statistical random number test suite. ( see http://csrc.nist.gov/groups/ST/toolkit/rng/documents/SP800-22rev1a.pdf, chapter 2.2).
In that chapter is also stated the recommended sample size.

I would propose to encrypt a block of zeroes with different randomly selected keys.

Another test would be to fix the key and use random plaintexts $t$, encrypt it $c= enc(t)$ and fit $t \oplus c$ to the frequency test.


How secure is the OTR protocol? I am using Adium and wondering how secure it is.

I believe it uses AES-256 (I do not understand what that means) by default.  It also requests that users exchange fingerprints with each other before encrypted conversations can occur, and that a unique key is used for each conversation.  Logging can be turned on or off, depending on user preference.

Does this allow users that suspect snooping to breathe easier, or is it all show?

If you ask about the protocol itself, as a theoretical construct, then it is safe. In theory it indeed provides all the feature that it promises.

And now for the "but..." part. When you use a protocol to communicate, you are actually using one implementation of the protocol. The implementation tries to do exactly what the protocol says. However you can never be sure that there are no bugs in the source code.

What i am trying to say is that OTR is definitely not all show. Theoretically it provides everything that it promises, and practically the libotr library (which i think adium uses) is a good implementation of the protocol with active development and security audits (i believe). So it definitely is better than no encryption at all and if you suspect snooping you should definitely use it.

Lastly if you want even more security dont rely only on otr.You must learn how to use crypto properly, use other protocols for anonymisation, obfuscate you traffic etc.


Where is the "Letter to NBS, October 22, 1975" Discussions of the weakness of the U.S. Data Encryption Standard frequently cite a letter by Martin Hellman and Whitfield Diffie to the National Bureau of Standards that reported stated:

Whit Diffie and I have become concerned that the proposed data encryption standard, while probably secure against commercial assault, may be extremely vulnerable to attack by an intelligence organization" (letter to NBS, October 22, 1975).

I've been trying to find a scan of the original letter, but all I can find is the above quotation, which seems to have been faithfully repeated in many publications (for example, here).
Interestingly, this book attributes the letter solely to Martin Hellman.
Where can I find the original letter?

This letter, among other letters of the time, can be found in the Stanford digital repository of Hellman's papers.
This October 22 1975 letter, in particular, is here.


Is a symmetric encryption key derivable using the input and the output? I am looking for a python library for encrypting a string with a single key. I do not want the key to derivable by knowing the input and the output. I have came to cryptography.fernet so far, but I am not sure if this will fulfill my needs. Can the encryption key be derived by knowing the algorithm (assuming the fernet algorithm in this case) and knowing the input and the output?

For example when I encrypt message A with key K and it outputs B, can somehow A and B be put together, so it will output K?

EDIT

The actual use of this is the following. I need to store a password in a place that others can see (a discord config channel, but that is secondary) in a way so they cannot see the actual password. I thought that the user would encrypt the password one-time with a key only visible to the bot (a discord bot) (with a command). The encrypted password would then be sent back to the user and stored in the channel for the bot to decrypt it and use it later. The problem is: if the user knows the input and the output, if he would be able to guess the key, he would then be able to decrypt all other passwords stored this way. And absolutely noone wants this to happen!

For example when I encrypt message A with key K and it outputs B, can somehow A and B be put together, so it will output K?

Except for encryption messages where you are specifically restricted to use a specifc key K only once (e.g. OTP), then no, it is infeasible to recover K from A and B.

This is a fairly fundamental requirement on encryption methods (known as "Known Plaintext"); that is, given a plaintext message and the corresponding ciphertext (or more generally, a huge number of messages and ciphertexts, all encrypted with the same key), that is still no help in decrypting another ciphertext (also encrypted with the same key) - being able to recover the key from a plaintext and ciphertext would violate this.

Actually, we put even tougher requirements on encryption methods.  We allow the attacker to pick the messages to be encrypted ("Chosen Plaintext"), and also allow the attacker to submit his own ciphertexts (and see how they are decrypted), "Chosen Ciphertext".

An encryption method is generally not considered secure unless it is secure against all these attack scenarios.


Monoalphabetic cipher using different languages in the same plaintext Today I learned the principle of the monoalphabetic cipher. It's simple to decrypt a ciphertext written all in the same language (english for example) because I can use the syntactic properties as well as letters' frequency. What about writing a message using different languages in the same text?

  Il gatto è salito sull'albero. I don't know how to bring it down!

In this way I don't have any clues on how to decrypt the message, right? The only information that could help me should be the knowledge of which languages are in use.

Thank you very much for your time.

I don't think that this will make cracking the code that much harder. You could not use statistical "most popular letter" anymore, but I don't think that in English or Italian there are that many words that are exactly five letters and letters 3 and 4 are identical like in "gatto". We could also check what four and three letter words that share the same final two letters sometimes appear next to each other like in "know how".

And what if someone knows that the message is about a cat? He just has to check for that word in two languages, and he will get three (or in this case four) bits of the key.


Acceptable condition for dictionary search I am trying to write a program to break transposition cipher using dictionary search. But I cannot understand the finishing condition of the search. Is there any theory that the maximum number of valid word can only be generated by decripting the cipher text using the valid key only? If not what can be a good finishing condition?

In a chosen plaintext attack, the expected ciphertext length required to conclude that a decryption is correct was derived by Claude Shannon and is called the unicity distance. It depends on the distributions of the plaintext and the key and is infinite for the one time pad.

So if $K$ is the random variable describing the key with a known distribution, and the message has $N$ symbols, say $(M_1,\ldots,M_N)$ with the message distribution known, let the encryption map be $$(C_1,\ldots,C_N)=E(M_1,\ldots,M_N;K).$$

Then the unicity distance is defined as
$$D:=\min\{ N: H(K|(C_1,\ldots,C_N))=0\},$$
where $H(\cdot|\cdot)$ is the conditional Shannon entropy.

See, e.g., wikipedia or van der Lubbe's Information Theory text.


Understanding WannaCrypt's hybrid encryption scheme I'm confused about how WannaCrypt's hybrid encryption scheme works after watching Computerphile's "How WannaCrypt Encrypt's Your Files" video a number times. Below is my thought process to make it easier to pinpoint my misunderstanding.

A public and private key pair is generated for the client, Cpub and Cpriv. These are generated whenever the malware is installed on someone's machine and is unique to the infected to ensure that the ransom be paid in each instance.
In the ransomware's executable is a server's public key, which has a private key, but is kept secret in an off-site location. I'll refer to these as Spub and Spriv.
Cpriv is encrypted with Spub. Cpriv cannot be decrypted without Spriv.
An AES symmetric key, Kf, is used to rapidly encrypt a machine's files.
Kf is then encrypted with Cpub.
In order to get to Kf, we need Cpriv, but we can't get to Cpriv because it has been encrypted with Spub. To get to Cpriv, we need Spriv.

The chain of encryption:

Encrypt files with Kf
Encrypt Kf with Cpub
Encrypt Cpriv with Spub

The chain of decryption:

Pay the ransom (but don't IRL)
The server gives the client Spriv
Spriv decrypts Spub, giving the client Cpriv
Cpriv decrypts Cpub, giving the client Kf
Kf, a symmetric key, is used to decrypt the files

All keys with the exception of Spriv are on the client's machine, but are encrypted. Buying Spriv starts a decryption chain giving access to one's files again.

Is my understanding of WannaCrypt's encryption method correct? Are there any important steps or pieces of information that I'm missing here?

The server will never release Spriv, it protects all ransomed clients.
Assuming the server wants to allow a given client to decrypt it's file the server will use Spriv to decrypt Cpriv and send that to the client.
With Cpriv only the paying client/victim can decrypt the various symmetric keys $K_f$ and use them to decrypt his files.

It is worth to discuss a simpler solution not mentioned in the video where all files have the same symmetric key (and different nonce/IV), and the symmetric key is encrypted directly with Spub. Such a setup will have the single client private key available on the client until encryption is done, This is problematic for the ransomware, as they want the client key to be gone from the client asap making it impossible to stop the process mid way and capture the client key. By making a separate key per file, and encrypting that with a client public key with private key long gone this is averted. Even if you catch the process half way through you can't undue what is done without interacting with the holder of Spriv(paying the ransom).

Think of all the good that could be accomplished if the clever people writing malware actually directed their skills in a positive direction?


Algorithm for symmetric encryption (diffusion without confusion)? I'm looking for a symmetric encryption algorithm with specific characteristic. Having a key $k$ a message $m$ returns a ciphertext $c$, where $E_{k}[m] \rightarrow c$

It should be hard to perform a KPA. I believe the diffusion concept makes it hard to perform such an attack?
Yet I require that $k + x \rightarrow e$, $E_{e}[m] \rightarrow (c + x)$ where $+$ can be the sum operator in a finite field. I believe this will require to avoid the confusion concept?

Edit: From $E_{e}[m]$ I should be able to recover $c = E_{e}[m] - x$, or some other possible operation that can revert x.

Is there any algorithm with those characteristics? I do believe that a hash function can work for my use-case.

It should be hard to perform a KPA. I believe the diffusion concept makes it hard to perform such an attack?

Assuming the context of traditional symmetric encryption: confusion (combined with diffusion) is what makes this hard.

For simplicity, suppose we have a 4-bit message. Suppose the equations for each bit of ciphertext are: \begin{align}
c_0 &= m_0 \oplus m_1 \oplus k_0\\
c_1 &= m_1 \oplus m_2 \oplus k_1\\
c_2 &= m_2 \oplus m_3 \oplus k_2\\
c_3 &= m_3 \oplus m_0 \oplus m_1 \oplus k_3
\end{align}

Recovering the bits $k_i$ is trivial when you know $m$:

\begin{align}
k_0 &= c_0 \oplus m_0 \oplus m_1\\
k_1 &= c_1 \oplus m_1 \oplus m_2\\
k_2 &= c_2 \oplus m_2 \oplus m_3\\
k_3 &= c_3 \oplus m_3 \oplus m_0 \oplus m_1
\end{align}

Diffusion by itself is not generically sufficient to protect against known-plaintext attacks.

  Yet I require that $k+x→e, E_e[m]→(c+x)$ where $+$ can be the sum operator in a finite field. I believe this will require to avoid the confusion concept?

This would no longer the realm of traditional symmetric encryption.

You'll be looking for some kind of homomorphic encryption. There might be some kind of lattice-based construction that offers this feature. If I recall correctly, Ajtai's hash function offers some kind of "key homomorphism", but I'm not sure that it works the way that you require.

I can't provide a more precise suggestion of a scheme. Maybe someone else can.


How hard is it to generate a partial RSA fingerprint collision? When I  use SSH to log into a new system, I get asked to verify that the fingerprint (a 32 hex digits string) of the hosts's RSA key is correct. How much if it must I actually compare (by hand/eye) to make it unfeasible for someone to man-in-the-middle me? Assume the adversary has a budget of a few thousand dollars.

Clarification: I'm assuming that a human will never hand verify that the fingerprint printed by there SSH client is in fact exactly the same as the key on there server, but rather (assuming they are more diligent than the average human) will read a limited prefix and/or suffix. If we assume they will read the first and last 4 digits then you should be able to create a collision of just those digest in $2^{(4+4)4}=2^{32}$ guesses.

The question then becomes; how many digits can an attacker expect to match with the budget described above?

As far as we know, it is totally infeasible for anyone to create an RSA private key with a public key that has a specific 32 character fingerprint.  This remains true if you give the adversary a budget of a few billion dollars; the best approach for an adversary would be to try to break in and steal (or purchase) the private key (and the second best approach would be to factor the existing RSA key to obtain the private key, rather than trying to create a second one).

SSH uses MD5 to do its fingerprinting; the best way known to find preimages is just to go through a huge number of images, and hope to stumble across one that happens to hash into the value you're looking for; for this to work, we would expect to involve testing about $2^{128}$ images before we get lucky.  We might get lucky earlier than that; however we're more likely to hit the lottery than for this procedure to take less than $2^{100}$ trial images; creating and testing this number of RSA keys is completely unthinkable.

On the other hand, if we're looking for a partial match, for example, the first 4 characters and the last 4 characters (total of 32 bits), this changes entirely.

To attack this, we would need to generate and hash an expected $2^{32}$ RSA keys.  So, the question is "how realistic would such an attempt be for an attacker?"

Well, the answer is surpising; an attacker can probably do this in a few hours even if he has only one cPU at his disposal.

The immediate obvious objection to this is "it takes me quite a while - hundreds of milliseconds - to generate an RSA key; how can an attacker do it so much faster?".

Well, the answer is that the reason it takes you so long to generate a key is that you actually care that the RSA key is hard to factor, and so you spend a lot of time looking for large primes.  Now, it appears likely that an attacker might not actually take so much care that the RSA key he generates is as secure.

Once you stop caring whether the RSA key is actually secure, it becomes a lot faster to generate them; all you need to do is find a bunch of (say) 32 bit primes, and multiply them together in various combinations until he gets a match.  Once he has found an RSA public key that matches the parts of the hash he cares about, he knows the factorization of the RSA modulus, and so he can then generate the RSA private key, and he's good to go.

When you look at the inner-most loop of this procedure, it consists of taking a $N-31$ or $N-32$ bit number (of known factorization), multiplying it be a 32 bit prime, and then hashing that product, along with the $e$ value, and then seeing if that hash is partial match to the target.

I haven't tested it myself; it appears plausible that this multiplication and hashing might take a microsecond; if that guess is approximately close, then an attacker could, with a single CPU, find such a partial collision in a few hours.

So, to answer your clarification question: an attacker can easily find a match over 8 digits; he might (by using several CPUs and/or spending more time for the search) be able to find a match over 10 digits.  To go much beyond that would appear to require a zombie farm, or an array of FPGAs, or something other way of gaining more computing resources than are available to your average script kiddie.


Why do public keys for RSASSA-PKCS1-v1_5 follow a normal distribution? I converted ~1000 public keys generated from chrome's RSASSA-PKCS1-v1_5 implementation, converted them to decimal, prepended a "0." to them, and sorted them.

This is the graph that I got:

It puzzled me a little bit because it looks like an inverse normal distribution. I expected a uniform distribution (i.e. straight line). what gives?

the datapoints are the actual values of the keys, you could say normalized 0 to max, sorted, and then plotted by index in the sorted array.

It's not perfectly clear what your graph is actually displaying.

However, if you expect that $k$-bit RSA keys are equidistributed between $2^{k-1}$ and $2^k$, well, that's not likely (unless the key generator goes out of its way to try to ensure that).

Remember, an RSA key is (usually) produced by independently selecting two primes from a range of $[c2^{k/2}, 2^{k/2}]$ (where common values of $c$ are $0.75$ and $\sqrt{1/2} \approx 0.7071$; it varies between implementations; I don't know what Chrome uses).

Each prime might be approximately equidistributed, but the product of two such primes will be somewhat closer to a normal distribution, with intermediate values being of higher probability; however note that it won't really be that close to normal.


Signing a binary hash vs character representation of the same hash I have a hash that I want to sign, with the hexadecimal representation: hash_bin=0x11223344 (length 4 bytes).
The same hash also has a character representation hash_text=”11223344”, which is the binary stream {0x31, 0x31, 0x32, 0x32, 0x33, 0x33, 0x34, 0x34} (length 8 bytes).

Which of the hash versions (hash_bin – 4 bytes / hash_text – 8 bytes) is better to use for signing the hash by RSA, security-wise?

Which of the hash versions (hash_bin – 4 bytes / hash_text – 8 bytes) is better to use for signing the hash by RSA, security-wise?

Doesn't matter; as long as there is a 1:1 relationship between versions, it doesn't matter which representation you sign.

The only situation where you might run into a problem is if two different hashes (with version A) mapped to the same hash (with version B) - that doesn't happen here.

Now, with RSA, we (almost) always hash the message being performing the actual low-level RSA operation - are you doing the traditional RSA signature method here (which would involve computing a hash of your hash)?  Or, are you expecting to take the hash you have, do RSA padding (you are doing RSA padding, aren't you), and then doing the RSA private operation)?


Hash or compression function in Merkle tree nodes? Wikipedia says about a Merkle tree:

  Nodes further up in the tree are the hashes of their respective children. Usually, a cryptographic hash function such as SHA-2 or SHA-3 is used for the hashing.

A cryptographic hash function can be defined using a 1-way compression function. Can we use a 1-way compression function for hashing children? It seems more efficient. We don't do length padding. For every node there is 1 less computation of a compression function.

In Merkle hash torrent extension of BitTorrent and in TTH (Russian version describing Tiger Tree Hashing) they use hash functions, not compression functions. I did not find data on AICH of eMule. What about other tree hash functions (I don't know such; maybe, you know)?

In a Merkle Tree, data is eventually and inevitably lost, because it is compressed away. If a Merkle Tree used a non-padded compression function, the size of the resulting hashes would go down level by level, resulting in a top hash that is very short. The shorter that top hash is, the less it CAN say about the contents of its tree. The longer the resulting hashes in a Merkle Tree are, the more unique the tree is, and the better it expresses its data. In addition, if the results of the compression functions are not standard (i.e. dependent on tree level), than it is very hard from a developer perspective to create software that can work for any and all sizes of Merkle Tree. In short, a non-padded compression function would destroy the "uniqueness" of a tree, and be harder from a developer perspective (keeping the top hash of a long enough size to preserve data)


Which is better: “serialize and then encrypt” or “encrypt and then serialize”? Let say in a simple Java program, Considering all the facts, like security and performance, Which is the best way to follow. I tried searching for a answer but proper answer is not out there.

Which is better: “serialize and then encrypt” or “encrypt and then serialize”?

If you serialize it, then you have one [likely binary] block of data that you would then need to encrypt.

If you encrypt the contents first (however you might achieve this) and then serialize it, it would presumably have to identify the things that are encrypted, and this could likely leak information about the object or its makeup.  Also, this would theoretically open the individual parts up to tampering, or replacement, or other specific attack.

Therefore, I assume the best answer is to serialize and then encrypt.


How can AES + cycle walking be used as an FPE? I'm a bit confused after reading several articles that seem to provide conflicting information.  Basically I was wondering if AES by itself can be used as an FPE? And if so is this something computationally prohibitive, or something reasonable to do.  Furthermore how can we use AES by itself + cycle walking?

According to this paper it says one of the methods for FPE is

  5.2 Cycle walking Method "The  cycle  walking  works  by  encrypting  the  plaintext  by repeatedly   applying   AES   or   3DES   until the
  cipher   text becomes in acceptable range. The duration for ciphering
  is not deterministic. "

If this is the case, what is the general construct for this (I.e. how to set up your AES encryptor, key, IV, mode etc)

In that paper they also have a table that summarizes the speed of this method compared to others.

But in another article it is stated that it would be prohibitively expensive to use cyclewalking alone since it would take many iterations to get a value in the desired range.

  "So, why can't we just use cycle-walking? Because it only works well
  if the block size is approximately right—if the size of the valid set
  is a lot smaller than the block size of the cipher, then you have to
  do a lot of iterations in order to get an in-range result. So, you
  can't use a 64-bit block cipher in order to encrypt an SSN because you
  end up having to do a prohibitive number if iterations; you need to
  use L-R to construct a block cipher of approximately the right size
  and then use cycle-walking to shave off the last few values."

I'm not sure if the result 1500 milliseconds in the comparison table above is considered prohibitive or not for such an encryption scheme.

The general construction to encrypt (inputs of less than 128 bits) with cycle-walking is:

# IN, OUT are 128-bit unsigned integers in the range 0..MAX
OUT = AES(K, IN)
while OUT > MAX do OUT = AES(K, OUT)
return OUT

AES is going to permute your 128-bit input into a seemingly-random 128-bit output. About $1/2$ of the time the top bit of the output will be 0.  About $1/4$ of the time the top 2 bits will both be 0.  About $1/(2^n)$ of the time the top n bits will all be zero.

The construction above keeps looping until your output is coincidentally in the desired range.  This is non-deterministic: it could happen on the first iteration, or on the billionth.  Statistically it is likely to happen, on average, around iteration $2^{128}/{MAX}$.

If your MAX is close to $2^{128}$ then cycle walking can produce an efficient FPE solution.  But if your MAX is small - say a 9 digit account number ($MAX = 10^9$, which is close to $2^{30}$) then you can expect $2^{98}$ iterations to perform one FPE encryption.  That's harder than brute-forcing 2-key TDES, and clearly in the territory of 'prohibitive'.