Leaking information when a value is blinded Assume all values are defined over a field $\mathbb{F}_p$ where $p$ is a large prime number.

Given a fixed value $a,b$ we compute $v_i=a\cdot b+r_i$, where $r_i$ is picked uniformly at random from the field. For the sake of simplicity let all the values be none zero.

Assume the adversary knows $b$.

Question 1: Given $v_i$, can the adversary learn anything about $a$ (or $r_i$)?

Assume $p(x)$ is a monic polynomial whose coefficients are picked uniformly at random from the field. Let $x=\{x_1,x_2\}$ where $x_i$ are public values. Let $b_1$ and $b_2$ be known by the adversary. By $p(x_i)$, we mean polynomial is evaluated at $x_i$.

We compute $v_1=p(x_1)\cdot b_1+r_1$ and $v_2=p(x_2)\cdot b_2+r_2$, where $r_i$ are picked unifromly at random.

Question 2: Given $v_1$ and $v_2$ can the adversary learn anything about $p(x)$ (or $r_i$)?

Please note that the adversary knows $x_i$.

To make sure the values of a uniformly chosen random polynomial in $F_p[x]$ are uniformly distributed, you need to impose a maximum degree for the polynomial, since there is no uniform distribution on a countably infinite space.

Having done this and ensuring the uniformity of the polynomial values, your questions boil down to questioning the uniformity of and independence of quantities like $$a+Z$$ and pairs $$(aZ+W,aZ'+W')$$ where $Z,W,Z',W'$ are uniform and pairwise independent. And they are, since linear polynomials over $F_p$ are permutation polynomials.

To clarify, for both questions, the adversary cannot learn anything about the quantity of concern, since it is an independent random variable from the quantities they have access to. For example, $p(\cdot)$ being uniformly chosen means $p(x_1)$ is uniformly distributed and when $r_1$ which is also uniform is added to it $b_1 p(x_1)+r_1$ is distributed like $aZ+W$, which is itself uniform.


Technical details of attack on Android bitcoin usage of SecureRandom Reports are surfacing that Android's Java SecureRandom class has issues and isn't totally secure.

A specific example of how this issue translates to applications is bitcoin, where reports are stating that the bitcoin wallet is at risk of theft. With bitcoin specifically, the reports say that "colliding R values" can result.

Why did SecureRandom fail to output secure pseudorandom bits?
What exactly are "colliding R values", why is that a problem, and how can it be resolved?

It looks like there are really two potential problems. From the mailing list

  all private keys
  generated on Android phones/tablets are weak and some signatures have
  been observed to have colliding R values, allowing the private key to
  be solved and money to be stolen.

Recall that with bitcoin

  Transactions are cryptographically signed records that reassign ownership of Bitcoins to new addresses. Transactions have inputs - records which reference the funds from other previous transactions - and outputs - records which determine the new owner of the transferred Bitcoins, and which will be referenced as inputs in future transactions as those funds are respent.

  Each input must have a cryptographic digital signature that unlocks the funds from the prior transaction. Only the person possessing the appropriate private key is able to create a satisfactory signature; this in effect ensures that funds can only be spent by their owners.

So, first, if all private keys generated on an Android device are weak, anyone could (potentially) figure out your private key and basically transfer the money in your wallet to themselves. Weak private keys would be the result of the RNG not being very random in practice so there is only a small pool of random numbers being used to generate the private key (e.g., in the debian openssl key generation bug, there were some 65k private RSA keys being used due to a poor RNG, that is small enough to be enumerable).

Now, specifically on to what you asked about colliding R values. Bitcoin uses ECDSA for signing. For my description below, I'll use non-EC DSA to describe the problem for simplicity.

In DSA, the private key is a randomly generated value $x$ and the public key consists of $(p,q,g,y)$. For details on $p$, $q$ and $g$ see Parameter Generation. $y$ is computed as $y=g^x\bmod{p}$.

To compute a signature of a message $m$, we compute:
$r=(g^k\bmod{p})\bmod{q}$ (where $k$ is a randomly chosen value)
$s=k^{-1}(H(m)+xr)\bmod{q}$ (where $H$ is a hash function)

The signature is then $(r,s)$. I'm assuming that it this $r$ that they are saying is colliding. This could happen if the RNG is weak and you generate the same $k$ twice.

So, the question then is why would colliding $r$ values cause a problem. As I said, a colliding $r$ comes from generating the same value $k$ twice. I found the following note on wikipedia interesting:

  With DSA, the entropy, secrecy, and uniqueness of the random signature value k is critical. It is so critical that violating any one of those three requirements can reveal the entire private key to an attacker. Using the same value twice (even while keeping k secret), using a predictable value, or leaking even a few bits of k in each of several signatures, is enough to break DSA.

  In December 2010, a group calling itself fail0verflow announced recovery of the ECDSA private key used by Sony to sign software for the PlayStation 3 game console. The attack was made possible because Sony failed to generate a new random k for each signature.

This works as follows (adapted from here)

Say you have two signatures with colliding $r$ values. Call them $(r,s_1)$ and $(r,s_2)$.

Compute: $s_1-s_2=k^{-1}(H(m_1)+xr)-k^{-1}(H(m_2)+xr)$
Redistribute: $s_1-s_2=k^{-1}(H(m_1)-H(m_2)+xr-xr)=k^{-1}(H(m_1)-H(m_2))$
Thus: $k=(H(m_1)-H(m_2))/(s_1-s_2)$, so you know $k$.
Then you compute the private key $x$ as $x=((s\cdot k)-H(m))\cdot r^{-1}\bmod{q}$ using one of the signatures.

So, even if your private key is not weak (say you generated it on another machine then moved it to the android device), signing two transactions with the same $k$ allows someone to discover your private key.

Recommendation for resolving the problem
The bitcoin folks are recommending that bitcoin software developers switch to /dev/urandom, then in their apps have all users generate a new private key, and transfer all bitcoins to the new private key.

Note
The problem only seems to affect Android's SecureRandom class. Presumably Google could fix SecureRandom, in which case Android devices could switch back to using SecureRandom (instead of /dev/urandom). Private keys would still need to be regenerated.

Why SecureRandom Fails
The details of why SecureRandom fails to generate good random numbers were presented at RSA-CT 2013 in this paper. The problem happens when creating a self seeding instance of SecureRandom (i.e., no seed, either through the constructor or through setSeed method, is passed by the programmer). The seed is stored in a buffer with the seed data, a counter, and padding. In the case where no seed is passed by the programmer, a bug in the code caused a pointer into the buffer to not be updated, which causes other code to overwrite portions of the seed. This data should be appended to the seed instead. See Figure 4 of the linked paper.

The result is that there is only 64 bits of entropy in the buffer. This is much, much too low.


Benchmark (hash rate) for SHA-3 (SHAKE128) To estimate the time for brute-force attack we need to compute keyspace size divided by hash rate, where the hash rate (hash/second) varies depending on the computer's capabilities.

The website https://bench.cr.yp.to/results-hash.html shows the hash rate for different computers.  Can you explain the following two confusing phenomena?

The hash rate decreases as the message size increases.
Core i3 has a higher hash rate than Core i7 for SHAKE128.

The hash rate decreases as the message size increases.

What's quoted by the benchmark decreases with the message size. But it is not a "hash rate", at least in hashes per unit of time on a certain computer as thought by the OP. The unit is cycles per byte, thus higher values mean proportionally more cycles spent, more time spent, and less hashes performed (with all of many other more important things being equal).

Assume computer(s) used to their full computing power for hashing, with a total of $u$ CPU(s), each with $n$ core(s) running a frequency $f$ (in Hertz), for total time $t$ (in seconds), to hash $m$ messages each $b$-byte, with each hash produced requiring $c$ cycles of one execution thread of one core of one CPU. It holds that
$$u\cdot n\cdot f\cdot t=m\cdot c$$
Derivation: Left side is the number of cycles across all $u\cdot n$ cores, with $f\cdot t$ cycles for each core given frequency and time spent. Right side is the number of cycles $m\cdot c$ necessary to hash the messages, given how many messages there are, and how many cycles are required for each hash. They are equal due to the assumed "used to their full computing power", which can be closely met when $m\gg u\cdot n$ by splitting the messages evenly among the cores.
What the linked benchmark quotes is $c/b$ in cycles per byte, where cycles are those actually used by one thread running sequential code computing the hash. This quantity $c/b$ depends a lot on the algorithm, the CPU architecture, and the quality of the code (including fitness to the CPU, compiler..); on the value of $b$, especially when low (see below), which is why $c/b$ is given for several values of $b$; and seldom on the rest.
Note: Thread(s) running on a core have to share that core's $f\cdot t$ cycles. My understanding of the benchmarks quoted is that the number of threads per core is considered part of the CPU architecture; if that could be adjusted, e.g. to 1 or 2 at boot time, there would be separate benchmarks or/and the $c/b$ quoted would be the highest achieved.
Note: The benchmarks quoted, and the present answer, stick to fixed hash output size, e.g. 32-byte. SHAKE128 has variable-size output, and this could be an extra parameter.

Most practical hashes (including SHA-3/SHAKE) group bytes (after padding) into block of fixed size $B$-byte ($B=136$ for SHA3-256/SHAKE128), and have an iterated structure processing blocks sequentially. It follows that $c$ grows with $b$ approximately as
$$c=c_0+c_1\lceil(b+b_0)/B\rceil$$
(ignoring cache and other effects), where $0\le b_0<B$ is a padding size in bytes ($b_0=1$ for all SHA-3), $c_0$ is a fixed overhead in cycles, $c_1$ is the number of extra cycles to hash an extra block (with $c_1<c_0$ for SHA-3), $\lceil x\rceil$ is rational $x$ rounded up to the next integer. The quantity $c/b$ reported by the benchmark is:

for small messages (up to $B-b_0$-byte), approximately $(c_0+c_1)/b$, decreasing quickly with $b$;
for large messages ($b\gg B)$, approximately $c_1/B$, largely independently of $b$.

Overall $c/b$ mostly lowers as $b$ increases (converging to some constant), but with initially noticeable sawtooth jumps.

In an earlier question and comment to another, the OP mentions wanting to hash 40-bit messages and wondering to what degree that's vulnerable to brute force search of the message. Let's evaluate how much time the hashing (which dominates the effort) would require to cover the whole message space.

Messages are $\lceil40/8\rceil=5$-byte, thus the appropriate column of the quoted benchmark is for $b=8$-byte messages (giving the same $\lceil(b+b_0)/B\rceil=1$). With an Intel Core i7-7800X featuring $n=6$ cores running at $f=3.5\text{GHz}$, it was timed SHAKE128 at a median of $c/b=112.25$ cycles per byte. Hence with $u=1$ such CPU, the time to hash all $m=2^{40}$ messages is:
$$t=\frac{m\cdot(c/b)\cdot b}{u\cdot n\cdot f}\approx\frac{2^{40}\cdot112\cdot8}{1\cdot6\cdot3.5\cdot10^9}\approx47000\text{s}\approx13\text{h}$$
Note: In this computation we used $b=8$ of the benchmark rather than $b=5$ for the number of bytes hashed, because we are trying to compute $c$ as $(c/b)\cdot b$ in a situation where $c$ is approximately independent of $b$. If we hashed a long message, we'd use the much lower $c/b$ benchmarked for that condition, and the $b$ for the message hashed, since we'd be in a situation where $c$ is approximately proportional to $b$. In between, we can compute the $(c/b)\cdot b$ quoted for the two benchmarks with the closest sizes, deduce the two corresponding $c$, and interpolate for our $b$ per a $c=c_0+c_1\lceil(b+b_0)/B\rceil$ model.
Note: The "Base" value of $f$ is what matters rather than the higher "Turbo", since the later can't be sustained for multiple cores, at least within manufacturer specs.

That search is easily feasible for an individual with a single computer. Further, a rainbow table would allow to make that computation only once, then invert any hash of a 40-bit message in seconds with e.g. a mobile phone.

The task is so easy that using CPU(s) is adequate (they are easiest to program). For larger attacks, after an initial coding effort, GPUs would be more effective on speed, or/and cost and energy (their superior performance comes from $n$ being many hundreds for each GPU). FPGAs and ultimately ASICs are even superior (they have potential to decrease both $c$ and additional investment per added hashing capacity, by exactly tailoring the circuitry to the task). That's how the aggregate of bitcoin miners gets a hash rate over $2^{82}$ SHA-256 hashes per day (May 2018, per that source reporting SHA256d hashes comprising two SHA-256).

  Core i3 has a higher hash rate than Core i7 for SHAKE128

After noting that hash rate is in cycles/byte, that observation amounts to: in a comparison, a core of a CPU with a higher digit following "Core i" in its Intel marketing designation happens to have the desirable property of requiring less clock cycles than the other one.

This is far from a general rule, as (for the Intel x86 line) $c/b$ depends much more on how recent the CPU is. The stated difference is largely attributable to architectural improvements increasing IPC between Q1'11 when the Core i3 referenced was introduced, and Q2'17 when the Core i7 referenced was.

The values of $b$, $u$, $n$ and $f$ have more essential influence on hashing performance of a computer, which is $m/t=u\cdot n\cdot f/c$ hashes per second, with $c$ proportional to $b$ for large $b$.


"123456" and "password" as crack standards I know that when we encrypt, we use standard encryption technologies and to store data it's often stored as a hash.

By encrypting a common password, for example

  "password"

using MadeUpHashingTechnology it will always equate to

  "awregk;4"

this becomes a standard to use in identifying my hash. Now crackers can look at MadeUpHashingTechnology-Dictionary.com for the most common hashes and see my data more easily.

If I identified n-common or low-strength passwords and simply left them unencrypted (or used a distinctly different encryption) would that help in reducing dictionary attacks? (I'm assuming my password database has been compromised in this scenario)

Would the database need to be compromised for a dictionary attack to be useful?

Using several different encryption algorithms, and not disclosing which is used in each particular case would require password verification to try all possible algorithms. Feasible only when using just a few algorithms.
Truecrypt does this, for example.

This could strengthen security, when implemented properly - but it is much more difficult to implement.

Proper solution - salt.

Do not use MadeUpHashingTechnology without salt.
Do not use  MadeUpHashingTechnology ever, use public, verified crypto.


If my server utilises an RSA based certificate, why does firefox think I am using Diffie Hellman? I am not a beginner in crypto, but not that far from it, so please be gentle.

I look after a web server app that I generated the SSL certificate for, and I used an RSA public/private keypair.

When connecting to the web app via firefox 40.0.3, it doesn't let me, with Error code: ssl_error_weak_server_ephemeral_dh_key

As I understood it using RSA or Diffie Hellman for session key exchange did similar things, but were entirely separate.

So how can I have Diffie Hellman vulnerabilities if I am not using it?

P.S. The web app is HP Network Automation 9.20, which is based on jboss.

Sorry if this is the wrong exchange, the other questions I see look more pure maths based than applied crypto.

There are two different ways a RSA certificate can be used by a SSL/TLS server.

In the "classical" RSA ciphersuites the client randomly picks a secret value, encrypts it with the public key from the server certificate and sends it to the server. The server uses the private key to decrypt it. So the client and server now have a shared secret.

The downside of this approach is that it does not provide "forward secrecy", if the server's private key is later stolen then all previous sessions can be decrypted.

To solve this problem the "ephemeral" cipher suites were introduced where the keys used for the key exchange are generated for a given session and then thrown away. In principle an epheral RSA ciphersuite is possible, but no modern ciphersuite uses that technique for performance reasons (generating RSA keys is computationally intensive).

So in modern "ephemeral" cipersuites the clients agree a shared secret using an epheral DH or ECDH exchange. The RSA (or DSA or ECDSA) key in the certificate is used to sign the key exchange so that the client knows it is communicating with the correct server. These ciphersuites have names like TLS_DHE_RSA_(something) or TLS_ECDHE_RSA_(something) .

The strength of the DH or ECDH keys used in the key exchange itself is independent of the strength of the RSA key used to verify the key exchange. Some older servers default to 1024 bit or worse 768 bit DH parameters.

The preffered option is to set up your server to use 2048 bit or stronger DH parameters. If for some reason that is not possible you should disable the DHE ciphersuites, though be aware that this may cause you to lose forward-secrecy with some clients.


Fuzzy Extractor constructor for sequence reconciliation The famous works on Fuzzy Extraction considers $set$ of inputs. I am interested in reconciliation for sequence of close data. Here order of elements are important unlike in previous one. Are there constructions focusing on sequence rather set reconciliation?

Hamming distance based reconciliation for close secrets as maintained in famous paper by Dodis et.al on Fuzzy Extraction for close/noisy bio-metric data


Scalar Multiplication for Elliptic Curve Let $\mathbb{E}$ be the elliptic curve $y^2 = x^3 + 6x \text{ mod } 11$ and consider the point $P = (2, 3)$ on it. How do I compute $3P$?

I have been able to figure out what $2P$ is, $2P = (5,10)$. However I am unsure if even knowing $2P$ is helpful, or do I just compute $3P$ from knowing the original $P$?

On standard way to compute scalar multiplication is to use Double-and-add algorithm:

The idea is to take the binary representation of your scalar $b = b_0 ... b_m$in your case $b = 3$ gives  $b_0b_1 = 11$.

First you initialize your result $Q$ with $0$.

Then for each increasing bit index $i$, you set $Q = 2Q$ (computed with the doubling formula) and if $b_i = 1$ you set $Q = Q + P$ (computed with the addition formula).

In your example you have:

$Q = 0$
$Q = 2Q = 0$, $b_0 = 1$ then $Q = Q + P = P$
$Q = 2*Q = 2P$, $b_1 = 1$ then $Q = Q + P = 3P$

It is the generalization of user94293 comment. If your implementation is critical, be careful since the algorithm above is not time constant. You may prefer the Montgomery ladder in critical cases.


How should I treat a new cipher release like Spritz? I have been looking at both the paper as well as the sourcecode of Spritz — a spongy RC4-like stream cipher and hash function by Ronald L. Rivest and
Jacob Schuldt.

The paper states

  We have also performed extensive simulations to look for detectable statistical biases, and selected a candidate with no biases detected in our experiments. Further cryptanalytic review is recommended before this cipher is used in critical applications.

Since this is the first time I am witnessing the birth of a "new" cipher algorithm, I don’t know what to think of Spritz. Mainly, because part of it uses RC4, which seems to be known for its detectable bias, related to the state shuffling. But there’s also the "spongy" functionality in there, which reminds me of what I have read about SHA-3... but can that change be interesting enough to even think about touching it?

I am not much of an analyst, but my simple C timing function tells me Spritz is slower than RC4. Probably even slower than AES too. (I have to admit my AES implementation is not the fastest around.) No one seems to have cryptanalysed Spritz yet. And the distant sound of biased RC4 doesn’t provide comfort either.

This leaves three basic options for me to choose from:

Ignore it completely and wait until someone provides a good reason to use it (good reasons not to use it seem to be: RC4 related, slow,...)
Have fun with it while trying out my first baby-steps trying to apply some basic attacks to learn from the experience without really hoping to actually be able to break anything
Be exited and wait because there might be a dozen of smart people that are already pulling it apart from all sides to find out if it is secure or not.

So, how should I treat a new cipher release like Spritz?

Actually I’m hoping the answer is *"have fun with it". If that’s the case, can you give me a few hints about which analysis/attack/break would be the most appropriate to try on a cipher like Spritz? I have just started learning about linear and differential cryptanalysis, but I am willing and able to expand my knowledge if this is a chance to do so. I don’t need a list, just a hint or two... a gentle push, not a kick. ♥

Nobody can tell you not to "have fun with it" but I would strongly recommend you to first study attacks on other ciphers. Spritz (Rivest & Schuldt) fortunately mentions a lot of research on its predecessor, RC4. This makes it a rather good starting point in my opinion.

It is necessary to understand the linguistics and mathematical constructs that are used. Jumping into crypto-analysis without a good understanding of the concepts will not get you any reasonable results.

If your main competence is to create a fast/secure implementation of cipher algorithms, then go for it. In the worst scenario an attack is found or the algorithm never receives wide popularity.

I don't see the big difference between 1) and 3) outside your own state of mind. Again, nobody can tell you not to be exited :)


Block cipher's output in case of uniformly drawn input Consider a block cipher $E_k$ where $k$ is an arbitrary key. $E_k$ takes input messages from $\{0,1\}^n$ and outputs a ciphertext $c\in\{0,1\}^n$. Let $m$ be an input message which is uniformly drawn from $\{0,1\}^n$ and let $c = E_k(m)$.

My question is simple - is $c$ also uniformly distributed in $\{0,1\}^n$?

Note: I know that $c$ has to be indistinguishable from a uniform distribution, but I ask if it is actually uniformly distributed. I'd appreciate a proof (or proof sketch) in case it is.

Thanks

The answer is yes.
While I can't provide a rigorous proof (because I don't know for now how to make one for such distributions), I can give an intuitive argument, which you can formalize I hope.

The main reason is simple: $E_k$ is a permutation for all choices of $k$.
This means that essentially all the encryption function does is "re-label" the given input message, there are no collisions (which would change the distribution) and input- and output space are equal in size so, every value in the input space is mapped to precisely one value in the output space and vice-versa.

So if you have probability $1/2^n$ of drawing $m$ you have probability of $1/2^n$ of ending up with $E_k(m)=c$ and so $c$ is distributed uniformly at random.


What is the Risk of Rotating Keys This may be a difficult question

So, $C_1$ = AES-GCM($k_1$, nonce, message) where nonce = HMAC(key,message). $C_2$ = AES-CBC($k_2$, iv, $C_1$).
Now, a security breach occurs.  The adversary obtains $k_1$ and $C_2$ because they are the most vulnerable parts of my encryption scheme.  I change the keys in this instance and re-encrypt the database.
Now, $C_3$ = AES-GCM($k_3$, nonce, message). $C_4$ = AES-CBC($k_4$, nonce, $C_3$).
Then there is another data breach.  The adversary now has $k_3$ and $C_4$.

1.) If the adversary has $k_1$, $k_3$, $C_2$ and $C_4$ can he decrypt the messages?

TL,DR explanation

In my encryption scheme, I have two sets of 256 bit secret keys [$c_1$,$c_2$] used to encrypt data.  The first key is used by my customers to encrypt data using AES-GCM.  The second key is used to encrypt the data once again using AES-CBC with PKCS#7 padding before being saved on the server.  Please assume I never repeat the same 96-bit nonce when using AES-GCM.  My message length is short and the number of messages encrypted will remain well below 1 billion.

How would a worst-case scenario play out assuming the adversary already has the customer key?  If an adversary obtains the data on the database I will change the keys and re-encrypt the data using the new keys.  If an adversary then obtains all of the data once again can he break my encryption assuming he has the customers key?

$\newcommand{\AE}{\mathit{AE}}$
Let $\AE$ be an authenticated cipher (AES-GCM) and $E$ an unauthenticated cipher (AES-CBC).

Let $k_1$ and $k_2$ be independent uniform random.  Let $m$ be a message.  Let $c_1 = \AE_{k_1}(m)$ and $c_2 = E_{k_2}(c_1)$.  If the adversary knows $k_1$ and $c_2$, but not $k_2$ or $c_1$, can they learn anything about $m$?

The answer is no: the security of $\AE$ and the randomness in the initial choice of $k_1$ is irrelevant; if an adversary could learn anything about $m$ from the ciphertext $c_2$, that would violate the semantic security of $E_{k_1}$.

   In particular, if we had an algorithm $A(k_1, c_2)$ which returned $m$ with probability $\varepsilon$, we could use this as a ciphertext distinguisher for the cipher $E$ with advantage at least $\varepsilon$: pick a key $k_1$ uniformly at random, and submit challenge messages $m_0 = \AE_{k_1}(m)$ and any other $m_1 \ne m_0$; then, given a challenge ciphertext $c = E_{k_2}(m_b)$ for unknown $b$, run $A(k_1, c)$ and guess $b = 0$ if $A$ returns $m$, and $b = 1$ if not.

What if you re-encrypt the same messages with fresh independent keys?  Same deal.

There are operational issues to worry about too:

Is eavesdropping of $k_1$ and $c_2$ (and $k_3$ and $c_4$, etc.) the only power of the adversary, or can they forge and modify things too?
If the adversary can influence $c_1$, motivating the use of the authenticated cipher AES-GCM, can they influence $c_2$?  Naive use of AES-CBC may expose you to padding oracle attacks.
Rotating keys doesn't prevent an adversary from using old keys to decrypt old ciphertexts.  It only prevents them from using old keys to decrypt new ciphertexts or vice versa.  If the adversary ever records old ciphertexts, then any future disclosure of the old keys will reveal the plaintexts.
The narrow cryptographic question here—of whether $m \mapsto (k_1, E_{k_2}(\AE_{k_1}(m)))$ has semantic security or ciphertext indistinguishability—isn't affected by the additional details about key rotation.  But what is the bigger picture here—what resources do you have, what are you trying to do with them, what attack surfaces does the adversary have to exploit these resources, and what are you trying to prevent the adversary from doing?  Do you have a living design document setting all of this down?  This is bigger picture is where you should focus your efforts to make sure your whole design is sound before worrying about little cryptographic details.


Maximum Number of Blocks to be Encrypted under One Key in CBC and CTR Mode? What is the Limit on Maximum Number of Blocks to be Encrypted under One Key in CBC and CTR Mode? What happens if the limit is crossed and more number of blocks are encrypted?

CTR mode.
There's a generic birthday attack on CTR mode of a block cipher.

The idea of CTR mode is to use a PRF, or pseudorandom function family, $F_k\colon \{0,1\}^\iota \to \{0,1\}^n$ to approximate a one-time pad with a short key $k$: $$c = m \oplus (F_k(0) \mathbin\| F_k(1) \mathbin\| F_k(2) \mathbin\| \cdots \mathbin\| F_k(\ell - 1)),$$ where $\ell$ is the length in $n$-bit blocks of the message $m$ (ignoring details of partial blocks).

If instead of a PRF we have a PRP, a pseudorandom permutation family or $n$-bit block cipher, $E_k\colon \{0,1\}^n \to \{0,1\}^n$, we can use that to approximate a PRF.  But a PRP, being a family of permutations, has the property that in the sequence of blocks $E_k(0), E_k(1), \dots, E_k(\ell - 1)$, as long as $\ell < 2^n$, there are no repeated blocks.  In a uniform random sequence of blocks, we would expect to see a collision when $\ell \approx \sqrt{2^n} = 2^{n/2}$, by the birthday paradox.

When $n = 128$ as in AES, this procedure—check for a repeated block—enables an attacker to distinguish a very long but not unimaginably long CTR mode pad from a very long uniform random pad with nonnegligible probability.

CBC mode.
In CBC mode, the $i^\mathit{th}$ ciphertext block is $c_i = E_k(m_i \oplus c_{i-1})$, with $c_{-1}$ being the initialization vector.  If the adversary notices that $c_i = c_j$ then they can infer $$m_i \oplus c_{i-1} = m_j \oplus c_{j-1}$$ from which they learn $$m_i \oplus m_j = c_{i-1} \oplus c_{j-1}.$$  Turning this into a distinguisher and calculating how the birthday bound is relevant here is left as an exercise for the reader who has had more breakfast so far this morning than I have.

Recommendations.
Because of these birthday attacks, cryptographers usually sternly advise against using AES-CTR or AES-CBC for more than a few exabytes of data, or, to be conservative, a few hundred terabytes.  (It doesn't matter whether that's for a lot of short messages or a few long messages.)  64-bit block ciphers like 3DES fare even worse, to the point that they can be broken in practice.

When $n = 256$ as in Threefish-256, these attacks are irrelevant: the birthday bound is around $2^{128}$ blocks of data, which you will never see.  When it's a PRF with $n = 512$, as in Salsa20 or ChaCha, it's even less relevant—although if you pick per-message nonces at random, the birthday bound once again becomes relevant because those nonces are only 64 bits and there is a nonnegligible chance of a security-destroying collision in the nonce, which is why the extended-nonce variants XSalsa20 and XChaCha exist and why some cryptographers and standardizers are considering nonce-misuse-resistant AEAD schemes.   In sum, the birthday paradox is a versatile tool!


Why have 4th and 5th steps in Needham-Schroeder Protocol? Why have 4th and 5th steps in Needham-Schroeder Protocol? It is said "These steps assure B that the original message it received (step 3) was not a
replay.". But what is a replay here? And I don't actually get what those 4th and 5th steps do. Send some nonce?

Here is the protocol outline I am looking at (source)

  $$
\begin{array}{ccl}
   1.& A \to S \colon& A,B,N_a
\\ 2.& S \to A \colon&
              \left\{ N_a,B,K_{ab},\{K_{ab},A\}_{K_{bs}} \right\}_{K_{as}}
\\ 3.& A \to B \colon&
              \{K_{ab},A\}_{K_{bs}}
\\ 4.& B \to A \colon&
              \{N_{b}\}_{K_{ab}}
\\ 5.& A \to B \colon&
              \{N_{b}-1\}_{K_{ab}}
\end{array}
$$
  Where $N_a,N_b$ are nonces.

Notice that $N_b$ has not been seen until step 4, so it is generated by B. In step 5, A sends $N_b-1$ back to B. This proves to B that A knows $K_{ab}$ otherwise A could not have recovered $N_b$.

This is done to prevent A from replaying the message in step 3 and therefore authenticating. For example, suppose Eve sees Alice send the message in step 3 $\{K_{ab},A\}$.

B receives this message, uses $K_{bs}$ to decrypt it and sees the identifier $A$ and therefore believes that Eve is A.

I think where most people get confused with Needham-Schroeder is that they assume that after step 3, Eve does not know $K_{ab}$ (which is correct) and therefore if B starts encrypting further session information with $K_{ab}$, Eve will not be able to decrypt those message (which is also correct). The problem is there is no guarantee that the rest of the session is encrypted. Needham-Schroeder places no such requirement on users of Needham-Schroeder (as it is simply an authentication protocol and the security of it should not be tied to how an application uses resulting keying material).


On the probability of a collision in RFO-rCTR My slides show that assuming a polynomial number $q(n)$ of blocks have been encrypted by a random function oracle in the context of a CPA-game, the probability of having a collision in the input to the oracle is bounded by $\frac{q(n)^2}{2^{l(n)}}$ (cfr. Katz and Lidell, 2nd edition pages 93-94).

Then I am proposed the following: assuming that in total $e(n)$ messages are encrypted each consisting of at most $s(n)$ blocks then the probability of a collission in the input is bounded by $\frac{e(n)^2s(n)}{2^{l(n)}}$.

Is this a typo? Why are we dropping the square from $s(n)$?

Here you may see the slides I refer to (see slide 18 and 19)

The key idea here is the blocks within the same message do not collide—message $1$ will have no possible block collisions, message $2$ can collide with the message $1$'s $s(n)$ blocks, message $i$ can collide with message $i-1$'s $s(n)$ blocks or message $i-2$'s $s(n)$ blocks, etc.

In other words, the number of possibly colliding block combinations is given by
$$
\sum_{i=1}^{e(n)} (i - 1)s(n)\,,
$$
which simplifies to $s(n) {e(n) \choose 2}$. We turn this into a probability $$ \frac{s(n){e(n) \choose 2}}{2^{l(n)}} \le \frac{s(n)e(n)^2}{2^{l(n)}}\,.$$


Chosen Cipher Text Security for Double Encryption If $E_k$ is a CCA secure encryption scheme then why is $E′_{(k_1,k_2)}(M)=E_{k_2}(E_{k_1}(M))$, $D′_{(k_1,k_2)}(C)=D_{k_1}(D_{k_2}(C))$ not CCA secure when $k_2$ is known. Is there a way I can make a new cipher with keys $(k_1, k_2)$ such that its CCA secure regardless of which key the adversary finds?
My confusion here is how can I use the fact that key $k_2$ is known to break CCA security and why would that matter, because don't we treat these schemes as black-box when performing attack? What if I had $k_1$ instead, would that make any difference? And I'm quite clueless about the second part about new cipher using $k_1, k_2$ and still a secure CCA. Any idea or hint would be greatly appreciated.

To understand the case of double encryption's CCA security, I read the paper Chosen-Ciphertext Security of Multiple
Encryption by Yevgeniy Dodis and Jonathan Katz in 2005.
With the help of this paper, now I'm able to understand why for the mentioned encryption scheme it will be no longer CCA secure when the key $k_2$ is known! Do give it a read for those having issues understanding CCA multiple encryption schemes.


Zero-Knowledge proof with the paillier cryptosystem For a paillier cryptosystem how can I perform a zero-knowledge proof?

Given a set of values:

0001
0010
0100
1000

This would be for use in a voting system where we want to ensure we where given a value from the set of acceptable ballots without knowing which if the values where selected.

I have found some information suggesting it is possible but I can't find a succinct set of steps or explanation for how this could be accomplished.

Found an implementation here: https://paillier.daylightingsociety.org/Paillier_Zero_Knowledge_Proof.pdf


PKCS1 and blind RSA signatures Wikipedia's article on RSA blind signatures says that you need to raise the message $m$ to the secret exponent $d$ modulo the public modulus $N$.

Implicit within that, it seems to me, is that m needs to be less than $N$. Problem with that is that that's not a restriction imposed upon signatures.

So for blind signatures to work as Wikipedia describes them you need to set $m$ to the hash or to the output of EMSA-PKCS1-v1_5-ENCODE or EMSA-PSS-ENCODE instead of setting $m$ to the plaintext. And then you do the modular exponentiation after you've blinded $m$.

IE.: you kinda have to side-step RSASSA-PSS-SIGN or RSASSA-PKCS1-V1_5-SIGN for blind signatures to work correctly.

Is that correct?

No, that is not correct.  You appear to have a misconception about how RSA signatures work.

Here is how an RSA signature is generated:

You take your message $M$
You apply a padding function to create a value $m = pad(M)$
You then use the RSA private key to compute $m^d \bmod N$

Now, this last step isn't always done in the straight-forward manner.  With blinded RSA signatures, it's done using a random value $r$ to defeat some side channel attacks; however that isn't that important for how RSA signatures work in general.  In particular, the value that a blinded RSA computes is precisely the same as a nonblinded version; it just uses a different algorithm to get that value.  In addition, that's the only part that's different for "blinded RSA signatures"; in all other respects, they are computed precisely like any other RSA signature.

You appear to be expecting that you can skip step 2, and step the value $m$ to the message $M$.  However, that can be dangerous; one of the issues with using  RSA without padding is that the RSA operation (either public or private) preserves multiplication, that is:

$RSA(a) \times RSA(b) = RSA( a \times b )$

(where both multiplications is done modulo $N$).

What this means is that if someone gets a series of messages $m_1, m_2, ..., m_n$ with their unpadded signatures $RSA(m_1), RSA(m_2), .., RSA(m_n)$, they may be able to find a message $m_{evil} = m_1^{e_1} m_2^{e_2} ... m_n^{e_n}$ (for some set of exponents $e_1, e_2, ..., e_n$; note that some exponents may be negative).  The attacker typically can do this if some of the $m_1, m_2, ..., m_n$ values are smooth (consists of only small factors); if there are enough smooth values, the attacker may be able to find a subset that they can recombine to form $m_{evil}$.  If that attacker can do that, that means that he can immediately deduce the signature $RSA( m_{evil}) = RSA(m_1)^{e_1} RSA(m_2)^{e_2} ... RSA(m_n)^{e_n}$

Signature padding methods are designed to prevent this; the value $pad(M)$ are large values, and hence are extremely unlikely to be smooth.

Hence, it is considered a Good Idea to always have a padding method when generating RSA signatures.


CPA security of a stateless and deterministic encryption system Why can no stateless and deterministic encryption system be IND-CPA secure?

Is there a formal proof for it?

Here is the answer for why a deterministic public-key encryption scheme cannot be CPA secure.

For CPA security it is sufficient if an adversary can distinguish between encryptions of two messages $m_0$ and $m_1$. That is, an adversary gets to see an encryption $c \gets \textsf{Enc}(pk,m_b)$ for a random bit $b$ together with the public key $pk$. Now in order to figure out if $c$ is an encryption of $m_0$ all the adversary has to do is to recompute $\textsf{Enc}(pk,m_0)$ and check whether or not this value matches the given ciphertext thus breaking CPA security.


Could this alternative hash based MAC construction be as, or even more secure than an HMAC? Begin hashing (Key||Message)
Encrypt the hash state (or some part of it, such as the first 128 or 256 bits), with the key.
Add the encrypted hash state to the hash and return the result.

This could be roughly described as Hash(Key||Message||Encrypt(Previous hash state))

There are several properties about this:

It may be faster than an HMAC in practice, especially for shorter messages (modern hardware accelerated encryption is up to 5x-10x the speed of hashing).
Encrypting the hash state in stage (2) is a psuedo-random permutation, rather than just a PRF and so may have stronger security guarantees (this is the job of the more math-oriented people [i.e. you guys/girls] to try to analyze though).
A practical advantage of HMAC, though, is that it could work with arbitrary “secrets”, that are not necessarily psuedo-random, but this construction would only work if the “secret” is an actual key associated with some cipher (though the “secret” could be hashed of course, to yield a key) - this may not be a significant limitation in practice though, as in most cases it is used with an actual key.

(Also consider a “weaker” version where stage (1) only performs Hash(Message), [i.e. without the key])

[Non-expert alert: I’m not a cryptographer or even a computer-scientist, so I don’t have the knowledge or capacity for the type of percise mathemtical reasoning that’s needed to analyze this. I guess that’s why I’m asking it here..]

Security

The level of security is likely to depend on the cryptographic primitives - the actual hash function and cipher - used. It is very likely that you can construct a function that is insecure, e.g. where the cipher is used for both the hash function an encryption. So you need to prove that the hash function and the encryption primitive are not influencing the security, even though they are using the same key. It is much easier to use a single PRF or PRP and prove that secure. Using one function also greatly simplifies implementations.

Implementation issues

An implementation issue is that intermediate hash states are often not defined or clear. SHA-1 and SHA-2 do have "logical" intermediate states after a block is hashed as the hash output is basically (part of the) final state. The final state for these hash functions does not significantly differ from the intermediate state. This is not obvious for other hash functions. This is for instance the case for Keccak - the winner of the SHA-3 contest - as well as most other SHA-3 candidates. Using an intermediate hash state should therefore be avoided.

Expected properties

I'll iterate over the expected properties in order:

  It may be faster than an HMAC in practice, especially for shorter messages (modern hardware accelerated encryption is up to 5x-10x the speed of hashing).

Usually performance is less of an issue for shorter messages. I would argue that it is only faster for shorter messages; the effect on larger messages will be negligible. Even then, it would require the cipher implementation to be cached (and in the case of e.g. Java, optimized) in addition to the hash function.

  Encrypting the hash state in stage (2) is a psuedo-random permutation, rather than just a PRF and so may have stronger security guarantees (this is the job of the more math-oriented people [i.e. you guys/girls] to try to analyze though).

A hash function especially within HMAC already provides very good security guarantees. It remains to be seen if using a PRP would have any advantages; I would expect it to be less secure.

  A practical advantage of HMAC, though, is that it could work with arbitrary “secrets”, that are not necessarily psuedo-random, but this construction would only work if the “secret” is an actual key associated with some cipher (though the “secret” could be hashed of course, to yield a key) - this may not be a significant limitation in practice though, as in most cases it is used with an actual key.

One of the more annoying aspects of CBC based MAC's is the non-variable key size. This is for instance rather annoying when using the MAC as building block for a key derivation function (KDF). So this is - in my opinion - a significant limitation.

CPU hash acceleration

Note that there are also CPU level optimizations for hash functions. Well known ones live in the Intel SHA extensions, the VIA padlock security suite, the Sun Ultra-Sparks...


If ChaCha20 is being used just as a CSPRNG, is nonce needed? I'm planning to use ChaCha20 just as a CSPRNG. Key is random (taken from strong initial entropy source) and will be constantly replaced via DJB's fast key-erasure scheme. What should I use as the nonce? Does it matter? Is it safe to just use zero?

No it doesn't matter, as you won't be switching the nonce on a per message basis, just outputting a stream of random data.
However, remember, your key will only produce an output stream valid until the internal counter overflows.
Consider XChaCha20.
IETF ChaCha20 uses a 96-bit nonce and 32-bit counter, XChaCha20 uses a 192-bit nonce and 64-bit counter. The 64-bit counter lets it encrypt 1 Zettabyte of data, i.e. output a large random dataset.


What kind of adversary is a compromised party? Imagine multiple parties executing a secure multiparty computation protocol to evaluate a function securely. Let Alice be one of the parties who is intended to get all the partial results and combine these partial results into complete result at the end of the protocol.

In practice , if Alice's machine is compromised and the attacker is impersonating Alice and he has the complete results at the end of the protocol, what kind of adversary would he be in theory ?

Attacker is  not passive adversary, he is not eaves dropping all the parties.

Is attacker an active adversary ( or byzantine adversary ) ?  I believe active adversaries corrupt the parties to execute arbitrary/malicious code etc. But here attacker is not corrupting the parties to do some computation of his choice rather he compromised the party that is intended to get the results .

Is attacker an non-adaptive adversary ? attacker infact control only one party but he has complete results .

I believe what you are describing is somewhat orthogonal to typical MPC adversary models. Typically in MPC we let the adversary know all information that corrupt parties know (so if a corrupt party learns the output, the adversary is allowed to learn the output). What we care about in MPC protocols is that the adversary is not able to learn any additional information (e.g., inputs of uncorrupted parties, intermediate computation results, etc).

So, if the adversary has corrupted Alice, and Alice is intended to get the results, then the adversary is allowed to know the result and that is okay by the definition of MPC. In that case, the adversary could very well indeed be a passive adversary. You could consider it an adaptive adversary if they don't know to attack Alice in the beginning, but figure that out during execution, corrupt her, learn the output.

So, say for example we are using MPC to tally votes and the vote tally is revealed to Alice at the end of the protocol. The fact that the adversary corrupts Alice and learns the vote tally at the end is okay and still meets the security definitions of MPC. What she shouldn't be able to learn is an individual's vote.

To fix this, say let Alice learn the vote tally only if she is not corrupt, then we need some way of detecting whether or not she is corrupt.


Generate secure password hashes without access to PBKDF2 or bcrypt Given is a system, which does provide only implementations of fast hash algorithms (MD5, SHA1, SHA-256, SHA-512). There is no implementation of PBKDF2, bcrypt or scrypt available. The system does provide a generateDigest(algo, input) and generateMac(algo, salt, input) function. The system has also the ability to securely store a private key for the MAC-function. Due to some language restrictions, it is undesirable to implement one of the key derivation functions.

Despite its lack of an adequate key derivation function, the system should be used to generate hashes for given passwords and store them.

I wonder if it would be possible to do some simple key stretching by repeatedly calling generateMac() with the HMAC_SHA512 algorithm:

algo = 'HMAC_SHA512'

for (i = 0; i++; i < ROUNDS) {
    input = generateMac(algo, salt, input)
}

From a naive point of view, this does look like a feasible solution to slow down attacks on the hashes. But i do lack the experience and knowledge, if it would be a right way of doing it cyptographically.

Actually you are quite near on implementing PBKDF2. It is kind of iterated HMAC execution. So have a look here and just implement the missing parts: PBKDF2


How to sign messages using the NOISE Protocol Framework? I wanted to learn more about secure messaging and started a personal project using the libhydrogen library. From my understanding, instead of using public-key encryption, the library relies on the noise protocol framework to create ephemeral session keys shared by both parties to encrypt and decrypt messages. I was wondering if the same session keys can be used to sign and verify the messages, or should this better be done with another (not shared) key pair? Also, I couldn't find any information on how long these session keys should last. Are they intended to be used for several days, weeks, or longer, or should I think of a session key as a login to an online service that expires after 10-15min, unless you stay active?
As I said, I am new to the topic and there might be very straightforward answers. Unfortunately, I couldn't find this information myself. Thanks in advance.

If you need signatures, use the signatures API. Signing key pairs may or may not be ephemeral, this depends on your use case. You'll need some way to determine that a signing keypair belongs to whoever you think it belongs to, this can't be handled by the library alone.
Signing key pairs and key exchange key pairs are different data types (hydro_sign_keypair vs hydro_kx_keypair or hydro_kx_session_keypair) and thus can't be used interchangeably.
A session should last at most for as long as a given connection using the service lasts. That might be weeks, but is more likely only as long as a user stays active.


What does “invertibility of the cryptographic primitive” mean? source: http://www.cosic.esat.kuleuven.be/publications/thesis-152.pdf ,page 32

  Note that key recovery implies invertibility of the cryptographic
  primitive (because due to the Kerckhoffs’ principle, the corresponding
  decryption routine is available). The inverse is not always true.
  PR-CPA secure ⇒ KR-CPA secure.

What does “invertibility of the cryptographic primitive” mean?

"Invertibility of the cryptographic primitive" is just a fancy way of saying "you can decrypt things encrypted with that key." All the first sentence means is "if you can recover the key, you can decrypt anything encrypted with that key." As the second sentence points out, there are conceivably attacks where you can decrypt things encrypted with a key but can't recover the key itself; the reverse is not true, because if you have the key you can use it to decrypt things.


Proper authenticated encryption I am using AES-CBC, authenticating using HMAC-SHA512 and I was wondering whether my thought process and implementation are correct.

The message send over the network is: HMAC(64Bytes),IV(16Bytes),Ciphertext
The MAC is calculate as follows: HMAC(sha1(secretKey),Plaintext)

Is there a significant reason to use SHA-512 over SHA-256?
Should I treat the secretKey differently or generate a complete new pair entirely for the authentication of the ciphertext

I am using AES-CBC, authenticating using HMAC-SHA512 and I was wondering whether my thought process and implementation are correct.
The message send over the network is: HMAC(64Bytes),IV(16Bytes),Ciphertext The MAC is calculate as follows: HMAC(sha1(secretKey),Plaintext)

No, that's not correct.
The HMAC should be calculated over the IV and ciphertext values, not over the plaintext. If you send the HMAC over the plaintext then an attacker will be able to distinguish identical plaintext.
If this is used for transport security (as you seem to indicate) then you may be vulnerable to padding oracle attacks on the CBC mode AES. If you want to use a good scheme you could take a look at this draft RFC.
If you want to use it as application level protocol you may (also) want to read about the order of encryption and MAC. If push comes to shove you could use MAC-encrypt-MAC of course.
SHA-1 in this scheme only reduces the amount of key material if a 192 or 256 bit key is used.

Is there a significant reason to use SHA-512 over SHA-256?

Probably not for generating an authentication tag for a MAC. Note that SHA-512 is generally faster than SHA-256 on 64 bit machines, so if you can spare the bandwidth then it might be a good idea to use SHA-512. Otherwise you could use SHA-512/256 - if that's available on your target runtimes of course.

Should I treat the secretKey differently or generate a complete new pair entirely for the authentication of the ciphertext

You definitely should not put SHA-1 in the mix.
You could use the same key for encryption and HMAC if you're feeling dangerous. It's unlikely (but not theoretically impossible) that this will compromise the symmetric key.
If you want to do it nicely then you should use two keys. You could use a key derivation function such as HKDF to calculate two keys out of the master key. If that's not available you could fall back to the PRF used to generate the sessions keys within TLS.


Diffie-Hellman insecure on addition modulo $n$ Assume that the group $G$ is the set $\mathbb{Z}_{n} = \{0,\ldots, n-1\}$ for a 1024 bit integer and $+$ is addition modulo $n$. Then why would Diffie-Hellman key exchange in this group be insecure?

With addition and $\mathbb{Z}_n$, each party chooses a secret $x$ and sends $xg \pmod n$ over the wire, for an agreed upon generator $g$. Division by $g$ modulo $n$ is easily computable, and reveals $x$.

In other words, a prerequisite for DH to be secure is that the equivalent to discrete logarithm is hard in the chosen group. With $\mathbb{Z}_n$ and addition, discrete logarithm becomes totally easy.


Cracking pdf file with arabic password using hashcat I have been doing some test on password strength using arabic passwords and try to crack it using hashcat and when i used a non salted hash like a custom generated md5 hash and tried using --hex-charset parameter and it works like a charm but when i try it on pdf files it is not working i even decreased the password to 1 character

in case you are wondering:

i followed this blog http://blog.bitcrack.net/2013/09/cracking-hashes-with-other-language.html but works only for non salted hashes.
i used pdf2jhon.py to extract the hashes.
yes using the above steps it can also work for english.
--hex-salt is not supported on 10500(pdf format)

My assumptions are:

1.maybe the pseudo random salt generator takes chars from the password itself

2.the password hashing algorithm stores the password in unknown charset format when the password is from non-English chars

So my question is:

1.is there another workaround on this(is it possible)?

2.if my 2nd guess is correct please tell me what unicode?

UPDATE
after researching i found the problem is the tool used to encrypt the file uses non ASCI characters when using non ASCI characters in my case arabic i am trying to use utf-8 format like D985 can someone tell me which unicode microsoft office and adobe acrobat use when using non ASCI characters.

If you cannot get things to work with the application you can try and use the source code instead. A lot of these tools are open source. Then you can specify the character set directly and/or use an Arabic dictionary.

The password itself is not stored when a password is hashed. That means that the precise encoding details are lost - the password hashing algorithms themselves process bytes, not characters usually. Nowadays a lot of password hashes and applications default to UTF-8 though, which can encode any character set. UTF-16 and UTF-16LE can also be tried, with and without BOM header.

However, to find out which character set is used just from the hash (instead of, say, a protocol specification) you can only try.


Keeping the key and IV safe when AES256 encrypting publicly known data I am encrypting some publicly known data, and some private data using the same key, using AES256 with CBC.

An attacker does not have the ability to choose what the public data is.

Is this safe?  (It looks to be, according to: Why is AES resistant to known-plaintext attacks?)

Assume I encrypt 4096_zeros.plain (public data) and my_private_data.plain with the same key and iv, producing 4096_zeros.crypt and my_private_data.crypt.

Is it possible for an attacker to use 4096_zeros.crypt to speed up either:

the decryption of my_private_data.crypt, or
the recovery of the key and iv.

Is using (and storing) a different iv for each file sufficient?  (Am I correct in thinking that I'd need to store the iv with the encrypted data?)

If not, would adding 32 random bytes to the start of each file (which would be ignored after decrypting) be sufficient?

Take a look at this article it explains the IV can be publicly known once you have encrypted your data.

  Is using (and storing) a different iv for each file sufficient? (Am I
  correct in thinking that I'd need to store the iv with the encrypted
  data?)

Yes, as a matter of fact i would not recommend using an IV twice, just for safety.

  Is this safe? (It looks to be, according to: Why is AES resistant to known-plaintext attacks?)

Yes, like the article says they would still have to bruteforce the key to get the cipher text

So there is no problem in doing this, though if data is public why would you encrypt it? everyone knows it, why go through all the trouble?

Use a MAC, to quote the page i linked to:

  Altering the IV Before Decryption

  If the adversary can alter the IV, without detection, before the
  ciphertext is decrypted, then they can corrupt the first block of
  plaintext. If the adversary knows the first block of plaintext is P
  and the original IV is OIV, and wants it to decrypt to Z, they can
  alter the IV to be P XOR Z XOR OIV, which will cause the first block
  to decrypt to Z (since (P XOR OIV) XOR (P XOR Z XOR OIV) = Z).

  Encryption provides secrecy, not authentication or integrety. If
  encryption is used in a setting where the adversary can modify the IV
  or ciphertext, it must be authenticated. The right way to do this is
  to have the sending party apply a keyed Message Authentication Code
  (MAC), like HMAC, to the IV and ciphertext, and have the receiving
  party check that the MAC is correct before decrypting.


Is there a way to turn a PGP key into its semi-prime counterpart? From my understanding of PGP keys they use the RSA algorithms to encrypt/decrypt messages. So, I know that the RSA algorithms use a semi-prime number to encrypt/decrypt messages. So, what I was wondering is: is the PGP key that you see the semi-prime number, and if so, how do you convert it back to the number.

This is my public key (I think):

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1

iQIcBAABAgAGBQJXUCB7AAoJEKOAQvYH1iPaycIP/0e77u0QaquZD/J5njjnnwSk
+Y9byw0a3S9h556DZPBfF37Cn1vC5LEJSYK2u9nZyeUpWP8a/+P8f0eE7ViQNAJ4
leUq5k6+OS2luWylyTKzLQnBHHxlI+HS080eRV8Yo5izE8HOXHby1sgy4J70ne/3
zPrCMn0OyiCJGuGwIqlp72y1v5NscsCJkB87pKmcwVBx5sGNXqTneKHg2rfYgQrM
9JCCO9F5/Li0bWTmfYifxom1l39VdZcioCCZgCi9YV5+c1gOBWlAfqtDsKVEUv4L
z97PPSaelD2FbSlHTRV2+jkB4feSEACjCGFSMh/AIYJlZX/d2N/Z33q2AdnV6+Ud
t7STYjxmz3W+jiRjQsm3vwm8uCjpjujpPvDDw51SmqARqAzuuZg8NCK69R4jxg4T
DPEHpYWbscwIWl1F+vXD5IxAXtJNVCcOH7fzoh23faGhpX8gRAMsFbpAQAn0arbY
idaRkVE4pfBGieN0w1md5GaARYY8pUU+39D4OsXjXajcMTklhs3hYtbsATV4Z7WT
YD+0T2XXT9XAfGA/X6j7oqzZe35L2HYrVy/yOJrcvSho+gpn5V7HPhkGYGCYZQvr
VfA7iArY3OTVSJ2GNpMm9qaQVcoInV9aYaEYB7J2e8pkZjtMFr4lCe2aXCbhGMYk
ZHOMYG21JbwhtdPJdd/U =Y2jy
-----END PGP SIGNATURE-----

Sorry, if I am totally confused and actually know nothing.

The OpenPGP message you posted is a signature, not a key. As it was issued by GnuPG, I assume you're using GnuPG anyway. To export your public key, run gpg --armor --export [key-id]. --armor wraps the output in a base64-like encoding (like the signature block you provided in your question), otherwise you'll get binary output. If you don't know your key-id, you can look it up through gpg --list-keys, possibly followed by a search pattern on a user ID you added -- for example your mail address.

The public key also contains user IDs, certifications, subkeys, ... and can be rather lengthy. The beginning of my own public key export:

-----BEGIN PGP PUBLIC KEY BLOCK-----
Version: GnuPG v1

mQQNBFDaK/sBIADm2gjnw7aPoNIoCy7gj85btwZU+zGkvtGonznlLrXELdU6zR3u
VHNCn9vAl6OoU32r+suFvGdX+7MjiPbGKwJFOvICpAVh6bV55+hdqJbS02cpPmJH
1BrrUAmm6ZVEybGd+II1pTI6Mt/SAI1E/59VIBdC/1AwsxQtCTFeyaLqTdyd1FhQ
chkjcvdRHLb4cEqldAGqBL7SbiSNOP3p+vX8iwRN6PQ/erAGseawHnunuNIna+tA
t4te/MkI2uxT0KjsfF/NWHCB2aXt++egP8jGSaHRsVOlfHRVA3hHcUDlnW9DZRvG
QabHFcZvfcXAlNIRYKUzDIHEwpavAmHeGNhc2GNmDcDRF56741grVLNQT58vxK5o
dBLlC8ANckvE5ymdIKVPm+t5q10kFOAATcnmDV0oBt+15vzI3f+88yCoY904UWdY
[...]

If you want to dump the RSA primes, use the pgpdump tool (not included with GnuPG and has to be installed separately, but should be available readily packaged for all relevant distributions). To print the primes, you can directly pipe GnuPG's --export output into pgpdump (consider storing the output to a file or piping intoless`, as the output can get really long):

gpg --export[key-id] | pgpdump -i

To understand the output of pgpdump (and the structure of OpenPGP messages), read RFC 4880.


Use slow hashing to reduce digest size? I have seen this question on MD5 replacement for 128 bit digests. It is said numerous times that having a 128 bit digest is impossible today because finding a collision would only require $2^{64}$ operations, which is in the means of big organisations nowadays. However, I think that these answers miss a fairly important point.
The time to bruteforce a hash function does not only depend on the number of security bits of its digest, but it also depends on the time needed to compute a single hash. This is why slow hashing functions such as bcrypt (184 bit) can afford to have a shorter digest size compared to fast hashing ones such as SHA-256 (256 bit).
In this case, would it not be possible to have a collision-resistant 128-bit slow-hashing function to replace MD5?
Thank you for your help.

Bcrypt is a password hashing function likes PBKDf2, Scrypt, and, Argon, where in the password hashing the collision is not important, pre-images are important.
If you just iterate the $\operatorname{MD5^n}(x)=\operatorname{MD5}(\operatorname{MD5}(...(\operatorname{MD5}(x)...))$ n-times then we will have an already well-known problem. A collision in the inner MD5 is a collision for the $\operatorname{MD5^n}$ therefore simple iteration is not secure only slows the collision finding, really? Just find a collision for $\operatorname{MD5(x)}$ then you have a collision. In other words, the cost of finding collusion is not affected!
An easy fix is for the case $n=2$ is $\operatorname{MD5^2}(x)=\operatorname{MD5}(\operatorname{MD5}(x)||x))$ or similar approaches.
We don't need doubling MD5 or SHA-1 to improve security, we just need new hash functions like SHA3 and the very fast one Blake2b.
Finally, we want cryptographic hash functions to be secure and fast, not slow. Slowness is required in password hashing.

update for the comment
It turns out that hashing with MD5 is required for the identification. In this case, the pre-image attack is more important if the public keys are considered to be kept secret. In the pre-image attack, given a hash value $h$ we are looking for an $x'$ such that $h = \operatorname{MD5}(x')$. The $x'$ may be the original $x$ such that $h = \operatorname{MD5}(x)$ or not. If the attackers seek the original they need to search more. MD5 has only one pre-image attack that its practical cost is not faster than the generic pre-images search that has $2^{128}$-time.

2009 - Yu Sasaki, Kazumaro Aoki, Finding Preimages in Full MD5 Faster Than Exhaustive Search. The post is $2^{123.4}$-time and $2^{45}\times 11$ word of memory.

The collision here is only relevant for you since you don't have two or more users who have the same identity.
So you can use a modern hash function with trimmed instead of MD5.


Collision on self made hashing function I am currently designing a hashing function based on a mathematical formular to calculate the size of an arc on a circle with the radius 1.

From that I made a small hashing function which works kind of like this:

f(n) = n² * π / 180

Then I only take the decimal places and convert them to hex. I remove the first three letters / numbers and take the next three places.

I then tried to find collisions by brute force because it would not take too long.
I started with 1.

f(1) = 553

Then I tried to find collisions and I found the following:

123, 4755, 8313

I expected the last two ones because they exceed the range of the hash-length.
The first one however was unexpected and I simply cannot explain it. Is it because of bad chance or is it because of the function?

(I know about the other flaws of this design)

I greatly appreciate any answer which helps me in this endeavour.

(Actually, this is about second-preimage resistance, not collision resistance)

  I expected the last two ones because they exceed the range of the hash-length. The first one however was unexpected and I simply cannot explain it. Is it because of bad chance or is it because of the function?

Actually, even for a good hash function, that has a relatively good chance at happening.

Let us assume that our hash function $F$ with an $n$-bit output is "good", that is, it acts like a totally random function.

Then, we evaluate $F(1)$ and get a specific value $z$.

Then, we evaluate $F(x)$ for $1 < x < 2^n$, and see if $z$ happens to occur a second time.

As $F(x)$ is random, then for any particular $x$, it will happen to be the value $z$ with probability $2^{-n}$; that is, it will be a value other than $z$ with probability $1 - 2^{-n}$

So, for $F(x)$ never to be $z$ for any of those $2^n - 2$ values of $x$, each probability is independent, and so the total probability is the product of the individual probabilities, namely, $(1 - 2^{-n})^{2^n-2} \approx 1/e \approx 0.368$ (where $e$ is Euler's constant 2.718281828459...)

That is, there is an about 63% chance of $F(1)$ appearing at least once somewhere else, even if you limit the range of the input to the hash-length.


How to compute ElGamal decryption by hand Lets say that $u=3, x=5, v=2$, how do we work out $u^{-x}*v$, so $3^{-5} * 2$. I know how to work out the answer if it was $3^5 * 2$ but how do we do it with negative exponents?

We're not trying to compute $3^{-5}\ast 2$, but instead we're trying to compute $3^{-5}\ast 2\mod p$ for some prime $p$.
This is notation for $(3^{-1})^5\ast 2\mod p$, so if we can compute what $3^{-1}\mod p$ is, you can just plug that value in and do computations like you'd expect.
Note that $3^{-1}\mod p$ means the element $u\in(\mathbb{Z}/p\mathbb{Z})^\times$ such that $u\ast 3\equiv 1\mod p$.
For example, because $2\ast 2\mod 3 \equiv 1\mod 3$, we have that $2^{-1} \mod 3= 2$.
Or, because $2\ast 3\equiv 1\mod 5$, we have that $2^{-1}\mod 5\equiv 3$.
The quantity $u^{-1}$ ends up being uniquely defined (when it exists --- $2\ast 3\equiv 0\mod 6$ means that $2^{-1}\mod 6$ can't exist), but note that it depends on both $u$ and $p$.

A computationally inefficient (but conceptually simple) way to compute $3^{-1}$ is via Fermat's Little Theorem, which states that:

  If $a\in\mathbb{Z}$, then $a^p\equiv a\mod p$

If $a\neq 0$, this is equivalent to $a^{p-1}\equiv 1\mod p$, and therefore $a^{p-2}\equiv a^{-1}\mod p$.
So we can compute $3^{-1}\mod p\equiv 3^{p-2}\mod p$, which you can do by hand.
If $p$ is large this might be annoying, but there are some tricks to speed it up (known as exponentiation by squaring).

A more computationally efficient way to compute this quantity is the Extended Euclidean Algorithm. This requires more explanation though, and if you want to know more about it you can probably find some resources online explaining it (it's a standard topic in elementary number theory courses).


State of the art RSA key generation I would like to know if there is an algorithm to generate a RSA key at the state of the art of the present cryptanalysis.

Beside the key lenght I know there are some weakness in the choice of prime numbers that could help an attacker to factor the modulus $N$.

The standard key generation, as far as I know, generate a random number of the right lenght, tries to factorise it dividing it by small factors (say $\leq 10000$) and then one or more primality test (as Fermat and Miller-Rabin) until the confidence level is high enough.

But what about risks that $p-1, q-1$ are with small factors?

There is consensus that it is safe to use random primes $p$ and $q$ when generating 2048-bit (or wider) RSA public moduli which two prime factors $p$ and $q$ are about half the key size. That is sanctioned by FIPS 186-4, appendix B.3; specifically, wording in B.3.1 item A:

  Using methods 1 and 2 [yielding provable (1) and probable (2) random primes],
  $p$ and $q$ with lengths of 1024 or 1536 bits may be generated;
  $p$ and $q$ with lengths of 512 bits shall not be generated using these methods.
  Instead, $p$ and $q$ with lengths of 512 bits shall be generated using the
  conditions based on auxiliary primes.

Even though FIPS 186-4 requires (in the second part of this quote) that $p-1$, $q-1$, $p+1$, $q+1$ have at least one known large prime factor when generating a 1024-bit key which two prime factors $p$ and $q$ are 512-bit, many regard this as an unnecessary complication.

The rationale about requiring that $p-1$ (and $q-1$) has at least one large factor is to insure resistance against Pollard's p-1 factoring. The standard rationale that such precautions become pointless past a certain size is that we have factoring algorithms (including GNFS and ECM) with a much better asymptotic run time; that becomes rigorous (thus true) if we add: for any fixed odds of success [Pretty much the same applies to requiring that $p+1$ (and $q+1$) has at least one large factor, which would be in order to guard against Williams' p+1 factoring; and when we do not need to guard against Pollard's p-1, we do not need to guard against Williams' p+1, thus I disregard the later].

Determining quantitatively when we can dispense of precautions against Pollard's p-1 is not trivial!

There's a line of thought that if parameters make us safe enough from ECM, we are also safe from Pollard's p-1. This argument is wrong (which does not preclude that it leads to correct conclusions), at least when we consider generation of many keys in a context where an adversary would be content with factoring any of $k$ keys, rather than a certain key (e.g. the adversary's objective is to pass some signature check, and she knows many public key certificates of entities that can emit valid signatures, which is common in machine-to-machine applications). Counter-argument: Pollard's p-1 is better than ECM from the standpoint of the ratio $\text{odds to factor}\over\text{computing effort}$ for low computing effort when factoring random integers (for this reason, in GMP-ECM, a significant time is spent in Pollard's p-1, with great success); that extends (with comparable advantage) to factoring integers that are product of random primes of specified size; and that ratio is what matters as long a the number $k$ of keys does not become the limiting factor.
There's a line of thought that GNFS is so much better than ECM that it transcends any advantage Pollard's p-1 may have over ECM for parameters of cryptographic interest. That argument works (past some point depending on the previous consideration) for RSA modulus $N$ with two prime factors of about equal size. But it does not apply when $N$ has one factor $p$ much smaller than half of $N$, which is the case in multi-prime RSA (see PKCS#1), and unbalanced RSA as in RSAP and SPAKE/ALIKE, which e.g. consider a 1248-bit $N$ with a 352-bit $p$, expected to provide 80-bit security [for some definition of that; these parameters are supposed to balance GNFS and ECM].


How long should a HMAC cryptographic key be? In the top answer to this question the answerer says 'with a sufficently long key'.

I am using a SHA1-HMAC (may switch to SHA256-HMAC) algorithm to verify cookies sent to clients as authentication tokens haven't been tampered with. The cryptographic keys are rotated with a new one being generated every 24 hours. Keys are valid for 3 days (i.e. there are 3 keys used to sign cookies active at any one time) meaning if a user doesn't login for 3 days then there authentication token is invalidated.

I am using 32 character long random alphanumeric strings as the cryptographic keys, would this be considered 'sufficiently long enough'?

Hashes and therefore HMAC do not take alphanumeric characters as input. You'd first have to convert the textual "key" into bits. I've put "key" in quotes because keys for HMAC should consist of bits in the first place.

The recommendation for HMAC is (indeed) that the key size is identical to the output size (and the intermediate state for Merkle–Damgård based hashes). Now lets presume that the characters in the key are completely random and that a large enough alphabet is used, say base 64. In that case you'd have 32 * 6 = 192 bits of randomness. That's larger than the required 160 bits of randomness.

If we'd use a single byte per character encoding such as ASCII or Windows-1252 then you'd get 32 bytes. This is much smaller than the ipad or opad used in HMAC. This means that additional hashing is not required before XOR'ing the key with ipad or opad. You would even be able to use UTF-16 as long as you don't use characters that require more than 2 bytes to encode. Anything longer than 64 bytes will require an additional hash calculation.

Below the security requirements for the key, taken from section 3 of RFC 2104:  HMAC: Keyed-Hashing for Message Authentication:

  The key for HMAC can be of any length (keys longer than B bytes are
     first hashed using H).  However, less than L bytes is strongly
     discouraged as it would decrease the security strength of the
     function.  Keys longer than L bytes are acceptable but the extra
     length would not significantly increase the function strength. (A
     longer key may be advisable if the randomness of the key is
     considered weak.)

  Keys need to be chosen at random (or using a cryptographically strong
     pseudo-random generator seeded with a random seed), and periodically
     refreshed.  (Current attacks do not indicate a specific recommended
     frequency for key changes as these attacks are practically
     infeasible.  However, periodic key refreshment is a fundamental
     security practice that helps against potential weaknesses of the
     function and keys, and limits the damage of an exposed key.)

Where H is of course the hash function, B the block size (64 bytes for SHA-1) and L the intermediate/output size (160 bits or 20 bytes).

Notes:

HMAC doesn't break in any terrible way if your key has somewhat less entropy; anything above 128 bits is probably OK.
Switching to SHA-256 is a good idea, even though it is not required to replace SHA-1 from a theoretical standpoint.


TLS false start / early data How often such mechanisms are used by application.
Is it real requirement to support these features for TLS ?

There is a push by browser vendors to reduce latency. It seems that, in their measures, the initial latency by the TLS handshake is large enough to be detrimental to the perceived user experience. It is true that a complete TCP handshake + TLS handshake can have a large latency (three round trips, which may add up to a significant time, in particular when considering links through geostationary satellites).

Old theory is that TLS handshake latency does not matter since you can keep the connection open, so you just pay for it once. However, the modern Web user does not engage with Web sites like he does with a local application; he will jump from site to site. Also, Web sites are now complicated assemblages of scripts that load other scripts, possibly from other servers, and all the latencies just add up.

This has led browser vendors to explore other strategies, including the false start / early data thing for TLS, to reduce latency. At Google's, they even decided to dispense with the TCP three-way handshake by defining QUIC to use UDP instead.

You may note that all of the above is about Web browsers. Requirements for applications vary quite a lot, depending on context. The modern Web has a combination of many short-lived connections and impatient human users, which may explain the quest for a reduced latency.

Of course, these modifications are not purely a matter of optimization. For instance, with TLS "false start", the client sends its data before having verified the Finished message from the server: at that point, the client does not have any guarantee that it has been talking with the intended server(*); it only knows that what it sends won't be intelligible to a fake server.

The "0-RTT" feature of TLS 1.3 is inherently vulnerable to replay attacks, and it is quite hard to know when 0-RTT can be used safely. TLS 1.3 draft 23, section E.5, gives some guidance, but (characteristically) uses the term "idempotent" without defining it, leaving the reader a bit nonplussed as what is meant there.

It can be expected that, when TLS 1.3 is finally deployed beyond some specific Web browsers and servers, 0-RTT will be activated in unsafe contexts, because developers and administrators just want "more speed".


Is there (this) a case in which salting is dispensable? tl;dr this is not a duplicate of "what is a salt/why use salt?" question. Instead it is specificly asking when salt may not be necessary for hashing securly? (i.e. when the data being hashed is already as high-entropic as that chances for duplicates is very very low)

Reasoning underlying the question
To my currently best understanding, it is that

salting is prevention against the usage of rainbow tables. (and only that)
rainbow tables are stored up precomputed original-data,hash-value pairs for a set of more or less frequently occuring original-data (i.e. the 100,1000...10^x most often used passwords)
rainbow tables are increasingly useless, the more and more random/entropic the original-data is. (The sum of all passwords used today may be very well smaller than 2^64 and hence less entropic than a truly random 64bit value)

My question is, that given that my assumption 3. above holds, then I would expect that salting (given 1. holds) becomes an decreasingly necessary endeavour.

Can this be confirmed or contradicted, please?

This is not only an academic question, but I have stumpled upon it in real life™ and maybe this serves as a way to bring this question also to a practical and henceforth more understandable / answerable level.

The case is that looking back at some work I have started prior to become crypt.stackexchange.com user I see with shock that I have stored data in a database in a plaintext fashion, that is used for authetification. In the very case it is a nonce created for an email verification (which is sadly anyway an unsafe channel, yet not in my power to prevent and not the issue here).
The nonce is unique and created from /dev/urandom. With hashing I would prevent that somebody having access to the database can access the nonce. If it was a password I would use a salting when storing it (because as mentioned I prevent rainbow-tables).
I think a rainbow-table for my 128bit value seems to defy its purpose as and I really wonder if I need to salt the unique nonces?

Passwords should use a password hashing function. Password hashing functions are different from basic cryptographic hashes, though they use cryptographic hashes as part of their construction. Password hashing functions must use salt. (Password hashing functions can also tune their time and/or memory usage, cryptographic hashes generally can't.)

So for your case, you probably don't strictly need a password hashing function. More importantly you probably want to not store the nonce in the database at all.


How is injective, inverse, surjective & oneway related to cryptography? Just researching cryptography concepts and finding it really hard to absorb them. I would love to know how these functions (injective, inverse, surjective & oneway) are related to cryptography.

Note that  I am just looking for a brief answer. Something that makes sense to someone researching Crypto for the first time. I surely don’t expect a full-fledged (too broad) explanation.

In mathematics these terms have very specific meanings. In cryptography these meanings do not really change, however the terms used to describe them have more specific meanings or examples.

One way function

A one way function is a function that processes the input in such a way that there is not an easy way to get back to to the input using only the output and knowledge of the function. When I say easy, I mean less than the expected security provided by the function to be practical, which may still be quite hard. It may take $2^{-10}$ seconds to compute, but require at least $2^{54}$ to "uncompute" using the same hardware.

For example, a cryptographic hash function is a one way function, and to get an input from an output, you can either brute force it, or try to attack the hash function and find a preimage, which may or may not match the input you are looking for.

Bijective function

A bijective function is one which is a 1 to 1 mapping of inputs to outputs. These would include block ciphers such as DES, AES, and Twofish, as well as standard cryptographic s-boxes with the same number of outputs as inputs, such as 8-bit in by 8-bit out like the one used in AES.

A bijective function is an injective surjective function. The codomain of a function is the set of possible outputs due to the size of the set. The image of a function is the subset of the codomain in which the output of the function may exist. In a bijective function, the image and the codomain are the same set.

Surjective function

A surjective function is one which has an image equal to its codomain, this means that if the set of inputs is larger than the set of outputs, there must be more inputs than outputs. These may include the general cryptographic hash functions.

In the case of SHA-1, we have $2^{160}$ possible outputs of a 160-bit function, but it is not proven that all outputs of SHA-1 are possible. Out of the real set of possible SHA-1 outputs, there are substantially more than $2^{160}$ possible inputs. Therefore SHA-1, IF computing all $2^{160}$ outputs for all possible inputs is possible, is a surjective function. If all outputs are not possible, it is not surjective.

Injective function

An injective function is kind of the opposite of a surjective function. Injective functions are one to one, even if the codomain is not the same size of the input.

An example of an injective function with a larger codomain than the image is an 8-bit by 32-bit s-box, such as the ones used in Blowfish (at least I think they are injective). These have 256 inputs, a codomain of $2^{32}$, and an image set size of 256.

Inverse Function

This is exactly like it sounds, the inverse of another function. This would be the decryption function to an encryption function. An inverse of a function may or may not have the same computational requirement as the forward function, and if keyed, may or may not use the same key. A keyed encryption algorithm that uses the same key for its inverse is a symmetric algorithm, whereas one that needs a different key is an asymmetric algorithm.

I would not consider an algorithm that returns multiple possible inputs of function $f()$ for a given output to be the inverse function of $f()$, but others may disagree. This would include hash function preimages, where the algorithm may continue processing and return multiple preimages, resulting in a set of possible inputs to $f()$ that generate the desired output. Only when the algorithm could return the entire set of preimages would I consider it the inverse.


Effect of tail cutting and precision of discrete Gaussian sampling on LWE / Ring-LWE security How does tail cutting and precision of discrete Gaussian sampling implementations affect LWE / Ring-LWE security? Is there a rule of thumb or guideline for choosing the tail cut and the precision for a given standard deviation?

Tail cutting refers to chopping off the “tail” portion of the distribution ($|x| > \beta \sigma$) which has negligible total mass.

In this paper from 2015, the author recommends tail-cut at $|x| > 9.2\sigma$ and 64-bit precision for 128-bit security. However, it seems too conservative, since many of the NIST PQCrypto submissions are using smaller tail-cuts and much lower precision. For example, FrodoKEM uses tail-cut at $\approx 4\sigma$ and 16-bit precision. Also, FrodoKEM is using the Renyi divergence, instead of the statistical distance, between the theoretical and the quantized distributions, as a measure of accuracy of sampling.

Tail cutting and precision refer to the problem of distinguishing the actual distribution used in your scheme and the distribution used in the proofs for the scheme. You want to somehow argue that an adversary cannot get any advantage from these two distributions being slightly different.

As you already mentioned, there are currently two more or less widely used approaches in lattice crypto. The traditional way is bounding the statistical distance (SD). Which really computes the difference between two distributions. The second approach is the Renyi divergence (RD). The Renyi divergence computes something like a weighted difference (depending a bit on which one you take). The best thing to do is to really read the paper which proposed this. They also discuss the different orders of Renyi divergence. There are now several follow up papers which improve this approach. Just ask your favorite search engine.

In general, there is not really a rule of thumb to estimate the outcome of such an analysis using either SD or RD.

However, when it comes to the tail cut it is comparatively easy though as the difference between the two distributions is typically known. If the total probability mass in the tails is something like $p = 2^{-k}$ for security parameter $k$, then the statistical distance between the distributions with and without tail is just $p$ and hence negligible. Which means that an adversary cannot distinguish the two distributions better than with probability bounded by $p$. Consequently, the difference in the success probability of any adversary attacking the scheme with one or the other distribution must also be bounded by $p$.

When it comes to the question of floating point precision everything gets more tricky. Here, the difference depends on the algorithm used and the way it is implemented. Hence, you need a new analysis for every implementation.


Hash multiset to point on elliptic curve where $A = 0$ I want to hash a multiset to a point on the elliptic curve $y^2 = x^3 + 3$ over a finite field of some 254-bit prime order, where $P = 3 \pmod 4$. Moreover, I want this hash to be incremental, in that the hash of the union of the multisets should be the same as the elliptic curve group sum of the hashes of each multiset.

The basic strategy for achieving this is to hash elements of a multiset using some hash function into the elliptic curve group, and then compose the multiset hash using group operations.

There is an elliptic curve multiset hash in the literature, but it relies on a deterministic Shallue-Woestijne encoding of field elements into EC group elements. In general, there are a number of deterministic encodings of field elements for elliptic curves which are "safe" assuming the hash function used for the elements of the multiset is a random oracle, but they all either apply to curves over fields with characteristic $2$ or $3$, or require the curve equation $y^2 = x^3 + ax + b$ to have $a \neq 0$ (I was looking at this paper).

I'm also can't just take a generator $g$ in the EC and produce $\operatorname{hash}(elem) \cdot g$ as the hash of {elem}, as a generalized birthday problem may be employed to find collisions between multisets (assume the inputs to the hash are public).

My question is how safe against multiset collisions is hashing {elem} by just setting $x = \operatorname{hash}(elem)$, and incrementing $x$ until $x^3 + 3$ is a square? SW encoding was used in the paper for ECMH mentioned earlier, but if timing/determinism isn't an issue, can this simpler approach be used instead? This approach is called MapToGroup in this paper.

I also found a multiset hash similar to what is described in the post here, with $b = 7$ and some $256$-bit prime field.

The short answer: MapToGroup can be used securely in this context. It reaches at least half the points on the curve (and much more if another bit from the hash input is used to determine the parity of y). Moreover, this encoding is "well-distributed" enough to act as an ideal hashing function, assuming the input is from a random oracle. Maitin-Shepard writes:

  I believe the try-and-increment encoding is fine from a security perspective, you just lose a few extra bits of security due to the larger bound on the size of the preimage of the encoding function.

The encoding in the ECMH paper caps the preimage size of points to three, and though I don't know of a bound for MapToGroup (which involves finding the longest sequence of non-residues in the base field), it doesn't seem to be a practical security concern.

Moreover, since about half the elements in the field mentioned earlier will be quadratic residues (see Counting Squares in $\mathbb{Z}_n$ by Stangl), an implementation of MapToGroup can expect about two trials on average to find a point. The average preimage size of points is less than two.

However, Aranha pointed out that an article Indifferentiable Hashing to
Barreto–Naehrig Curves exists which describes a deterministic encoding precisely to the curve being described in the question, and which is "secure" in this context.

The downside is that although the running time may be fixed, the implementation requires more computation on average than MapToGroup when using a BN curve. Moreover, there could be a side-channel leak from computing quadratic characteristics, which can vary in running time according to the input. This may be mitigated by "blinding" the computation of characteristics using inputs from a source of randomness, but is definitely an important implementation detail if the ECMH is being used on any private information.

Probably a good bet would be to go with the setup in the paper if there is support for binary curves, and otherwise consider whether any private information is being hashed.


Are Iphones' content encrypted? Recently I heard that the content of an Iphone is stored in encrypted form meaning that if I were to take apart the Iphone and managed to extract the memory and read it, I wouldn't be able to get any information out of it.

I find this hard to believe because an Iphone can be unlocked and opened in a mater of seconds, the decryption of 16 gigabytes of data in that short a time seems too fast to me. I would like to know what is happening exactly.

Is the memory not actually encrypted, is decryption actually just that fast or is there something else happening.

Just to be clear, my impression was that when you unlock the phone (not just when you turn it on initially) everything is decrypted. obviously turning on the phone provides more than just a few seconds of time to decrypt the phones content.

Additionally, I would be interested not only in Iphone encryption but also the encryption of Androids and other smart phones.

The iPhone is built with encryption inserted automatically when writing to flash memory and decryption inserted automatically when reading from it. This happens with all files, all the time. There is no concept of "decrypting a file and then opening the decrypted file", as there would be on a PC.

No file can be decrypted without the proper key. Some files (such as the ones needed to start up the phone) are decrypted with a key that is always known to the encryption/decryption machinery. Other files are decrypted with a key that is only provided to the machinery once the phone has been unlocked.

That is why unlocking the phone is fast. All that happens is that an additional key is made available to the decryption machinery, so that it is able to decrypt files encrypted with that key.

All this is an over-simplification, since there are more levels of keys than this. The absolutely authoritative source, which is also remarkably easy to read, is Apple's own iOS Security Guide.


In $\mathbb Z/p\mathbb Z$, is $(a+b\cdot r)$ a random value for fixed $a,b$ and random $r$? Let $p$ be a prime number.
Consider two fixed values $a,b\in\mathbb Z/p\mathbb Z$, where $b\neq0$, and a uniformly random value $r\leftarrow \mathbb Z/p\mathbb Z$.

Is $v=a+b\cdot r$ a uniformly random value in $\mathbb Z/p\mathbb Z$?

Yes. For fixed $a\in\mathbb Z/n\mathbb Z$ and $b\in(\mathbb Z/n\mathbb Z)^\ast$ — note that $b$ must be invertible modulo $n$, which need not necessarily be a prime (but if it is, invertibility is equivalent to $b\neq0$), the map
$$ f\colon\;\mathbb Z/n\mathbb Z\to\mathbb Z/n\mathbb Z,\; r \mapsto a+br $$
is a bijection, hence it preserves uniform distribution. That is: If $R\colon\;\Omega\to\mathbb Z/n\mathbb Z$ is a uniformly distributed random variable, then $f(R)\colon\Omega\to\mathbb Z/n\mathbb Z$ is as well.

The direct argument is: If $\forall y\in\mathbb Z/n\mathbb Z.\;\Pr[R=y]=1/n$, then for any $x\in\mathbb Z/n\mathbb Z$,
$$ \Pr[f(R)=x] = \Pr[a+bR=x] = \Pr[R=b^{-1}(x-a)] = 1/n \text, $$
therefore $f(R)$ is uniformly distributed on $\mathbb Z/n\mathbb Z$.


Theoretical pi-based stream cipher Let's pretend that all digits of pi are known and arbitrarily long sequences of digits are trivial to get. Further, some mathematician proves that there are no patterns in pi. We could create a stream cipher by grabbing a piece of pi as long as our plaintext and combining the two with some function (such as XOR or modulus addition.) The key would be the starting position in pi.

Would this be equivalent (in terms of security) to a one-time pad? To what sort of attacks would it be vulnerable?

The problem with this approach is that it literally gains you nothing. In order to choose a random subsequence of a needed length from $\pi$, you need to generate a cryptographically random number of at least the same length of the desired key to use as the offset. But then you may as well just use that number as your secret key.

Other than that, yes, it's exactly the same as a one-time pad. Just with a silly and pointless key derivation protocol which cannot mathematically increase the security of the system, but could conceivably weaken it.

Edit: As Thomas points out in the comments, the distribution of digits of $\pi$ are not random, and so this mechanism of key generation actually discards a significant amount of entropy that had been generated while choosing a random offset.


Encrypting a JPG, where the output is a scrambled JPG Is there an algorithm or program that can take an image, be encrypted, still be opened by an image viewer, but is restored when decrypted?

Basically I want the ability to secure images but still have them seen as "image files".

I wrote several papers on such a topic. I called it end-to-display encryption. But it is more commonly called "pixel-domain encryption" There are several easy ways to do this. My way included adding a header with RSA encrypted AES Keys.

In essence, you take the picture, extract the pixels, XOR with the bitstream created through AES in Countermode, increase the counter with every iteration, convert that to pixels, save as PNG (important, not jpeg or any other lossy compression, you lose bits with that, and decryption needs every bit to work properly). Thats it. And the same way back.

But sorry, no tool available. But its easy to implement.

I may extend on the thing with the JPEG in the question. Encrypting JPEG in the pixel domain will not work properly. The compression is lossy, so you lose information. There are compression methods on JPG, but they are much more complex, because they work mostly on the DCT factors, not on the pixels itself. These can also be viewed as pictures. That said, its another application field, as i wanted to decrypt pixel streams in the HDMI cable, that would not have worked as intended, or only with much more complex systems.


Proof of $\sqrt{\pi/2}$ in birthday paradox? I had found in the past a publication in a crypto conference (in 80s if i am not mistaken) which I believe was the first proof why for example a random function $f:X\rightarrow X$ with $\#X=2^n,$ is expected to have collision in $\sqrt{\frac{\pi}{2}\times 2^n}$ iterations. I can't find it, anyone has the reference?

The paper you are looking for is:

"Random Mapping Statistics" by Flajolet and Odlyzko, first published in  Advances in Cryptology — EUROCRYPT ’89. EUROCRYPT 1989. Lecture Notes in Computer Science, vol 434.

It is freely available via SpringerLink and via Archives-Ouvertes (PDF).

The relevant statistic you are looking for is probably the rho-length, which specifies the specifies the average length of a cycle to be $\sqrt{\pi n/2}$ where $n=2^k$ in your case.

The abstract reads as:

  Random mappings from a finite set into itself are either a heuristic
  or an exact model for a variety of applications in random number
  generation, computational number theory, cryptography, and the
  analysis of algorithms at large. This paper introduces a general
  framework in which the analysis of about twenty characteristic
  parameters of random mappings is carried out: These parameters are
  studied systematically through the use of generating functions and
  singularity analysis. In particular, an open problem of Knuth is
  solved, namely that of finding the expected diameter of a random
  mapping. The same approach is applicable to a larger class of discrete
  combinatorial models and possibilities of automated analysis using
  symbolic manipulation systems (“computer algebra”) are also briefly
  discussed.