Which is stronger: Threefish 1024-bit, SHACAL-2 512-bit, or AES-256? I found some App in the Google Store, and there were features only for the PRO version: Threefish 1024-bit and  SHACAL-2 512-bit. Meantime, AES-256 was available in the free version of app.

So I concluded that the Threefish 1024-bit and SHACAL-2 512-bit algorithms are stronger, and I did a little research and discovered that AES-256 was invented in 2001, Threefish 1024 in 2008, and SHACAL-2 512 was also invented in 2001.

SHACAL-2 512 - I have read that this algorithm was something like "partly hacked for 50%" but for now considered as solid and unhackable.

Threefish 1024-bit - in the opinion of the authors who invented this algorithm it is more effective than AES. And it has a 2.9 security index, while AES has only a 1.7 security index (bigger is better).

Neither SHACAL-2 nor Threefish are "more" secure than AES because it's a case of "meh cannot break" with all of them.

All three ciphers are unbroken and all three use keys larger than 128-bit* meaning the bigger numbers in the key size have no value except to impress people with being bigger and with the company being able to waste computation time. Also note that in the most rares cases it is actually the crypto (and especially unlikely the block cipher) that is broken but rather the implementation and especially the data handling implementation.

Now for a bit of discussion on each cipher:

SHACAL-2. It is based on SHA-2's compression function and from what I can tell turning it into a block cipher was a case of "we did it because we could". It's practical deployment is absolutely negligible and cryptanalysis results are sparse, so I wouldn't trust it more than AES.
Threefish. Threefish was the block cipher underlying the Skein submission to the SHA-3 competition. It has some well-reputed names behind it and is a very useful tool block-cipher with a large block size that is especially hardened against related-key attacks and side-channel attacks. I would actually prefer Threefish over AES if you don't have a well-hardened implementation of AES available and you are on a 64-bit platform and you don't have hardware-accelerated AES available. This is because Threefish only uses additions, rotates and XORs (ARX) which makes it quite easy to implement securely and with solid performance. Analysis-wise it has seen quite a bit during the SHA-3 competition and a bit afterwards, but as Skein wasn't selected it hasn't seen much analysis since.
AES. AES is an excellent block cipher which has with-stood nearly two decades of intense cryptanalysis. Not only hasn't it been broken in this time, but we have also figured out how to implement it securely and it has wide hardware support these days, making it the performance- and security-wise best choice if available. If not, using a more modern ARX based cipher is also appropriate, but especially on a modern phone secure AES implementations should be available.

On this topic, also see the mandatory blog post by Matthew Green.

* If you believe that large-scale quantum computers will exist at some point, you need 256-bit symmetric keys to force $2^{128}$ quantum operations (thanks to Grover's Algorithm) which all three cipher support.

AES is enough, but the security of the encrypted data depends almost of all about how you want to use.
You can use AES in CBC mode and you are ok.


Can I say "I have encrypted something" if I hash something? As I understand it, a hashing algorithm is some kind of encryption, just a specific kind of it. So is it wrong to say "I encrypted this value." if I "only" hash it?

I understand that it gives the wrong impression, but I think it is not absolutely wrong, or is it?

Encryption algorithms and hash algorithms both belong to the realm of cryptography but are two different things: Encryption doesn't contain hash functions.

As stated on Wikipedia:

  In cryptography, encryption is the process of encoding a message or information in such a way that only authorized parties can access it and those who are not authorized cannot.

An encryption algorithm turns some data into a ciphertext which can later be decrypted again to its original content by using the encryption key.

If you generate a hash of some data it can't be "reversed" back into its original content, because a hash function is (theoretically) a one-way function with loss of data.

Typically we require encryption be reversible, so it can be used as a communication system.

Mathematically, when we talk about a cryptographic system, we are focusing on invertible functions.  This change in viewpoint is important, because it opens up the possibilities for how we can encrypt information.

For example,  we can use a linear function (affine transformation) as an encryption system:

https://youtu.be/1S92scw5zIg?list=PLKXdxQAT3tCssgaWOy5vKXAR4WTPpRVYK


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.

If it were possible to compute digits of pi from an arbitrary location (to generate the stream) in constant time, then it would be an excellent cipher. Unfortunately, this isn't possible.

Maurer suggested using the surface of the moon for a source of random information instead: link


What's the difference between confusion/diffusion and mode of operation? I understand the concepts of confusion (substitution) and diffusion (permutation).

My understanding of what a mode is that it's an algorithm that lets us encrypt arbitrary message size. i.e. AES is a mode of operation, and confusion/diffusion are what we use to achieve a certain mode.

But that doesn't sound right.

AES is a mode of operation, and confusion/diffusion are what we use to achieve a certain mode.

AES is a block cipher, which replaces one fixed-length block of bits (plaintext) with another fixed-length block of bits (ciphertext) according to the key. A block cipher is not a mode of operation.

Confusion and diffusion are a description of how AES behaves to ensure that given a/many plaintext-ciphertext pairs, you cannot recover the key, as well as given a ciphertext, you cannot recover the plaintext.

"Confusion" basically means that the equations that represent the ciphertext are too complicated and cannot be worked with, while diffusion means that each bit of the plaintext influences many (half) of the bits of the ciphertext. These two properties help to ensure that extracting the key from plaintext-ciphertext pairs is difficult or infeasible.

Since AES only operates on blocks of 128-bits, you require a mode of operation to encrypt plaintexts of size > 128 bits. So a mode of operation is a way of using a block cipher to encrypt (effectively) arbitrary length messages.

Since for a fixed key AES is deterministic, a mode of operation also provides a means to randomize plaintext-ciphertext pairs, so that multiple encryptions of a plaintext cannot be distinguished from each other. This is necessary to properly provide confidentiality of the plaintext.

In Diffusion the statistical structure of the plaintext is dissipated into long range statistics of the cipher text. This is achieved by having each plaintext digit affect the value of many cipher text digits. Which is equivalent to saying that each cipher text digit is affected by many plaintext digits.

Confusion seeks to make a relationship between the statistics of the cipher text and the value of the encryption key as complex as possible. Thus even if the attacker can get some handle on the statistics of the cipher text, the way in which the key was used to produce that cipher text is so complex as to make it difficult to deduce the key.


Is it safer to encrypt twice with RSA? I wonder if it's safer to encrypt a plain text with RSA twice than it is to encrypt it just once. It should make a big difference if you assume that the two private keys are different, and that the only way used to crack it is brute force. I submitted these theories to my teacher, but he claims that a double encryption doesn't make it any safer. I didn't follow his arguments entirely, so I decided to ask here.

So, if I encrypt a message with one key once, and the encrypt the resulting cipher text once more with a different key, does this make the encryption simpler?

EDIT:
My teacher said that "it doesn't get safer with a double encryption, at least not if n is the same and e is different.". This is the part I don't follow, since you'd still need both p and q to derive the two different private keys that this would produce. I have made a few calculations and I do not quite understand. Why would the particular statement my teacher sent me mean that it doesn't get safer?

Well, think about it this way. If breaking one encryption with brute force will take longer than the lifetime of the universe, are you any safer with an encryption scheme that will take twice the lifetime of the universe? No. The first encryption cannot be broken. Adding a second encryption just adds computation overhead with no real benefit.

Think about it this way, if it is estimated to take 500 years for a prisoner to chew through the bars on his prison cell to escape, is the public any safer if we add a second set of bars so that it will take 1000 years to chew through the two sets before the prisoner can escape? Not really.

UPDATE
Given the update in the question, I thought I'd update.

So, you fix an $n$ and choose $e_1$ and $e_2$ as public exponents and compute $d_1$ and $d_2$ as the private exponents.

To encrypt, you are proposing $(m^{e_1})^{e_2}\bmod{n}$ and wondering why this is not stronger than just $m^{e_1}\bmod{n}$ in a brute-force attack[*].

So, you haven't given detail as to what the "brute-force" attack is, so let's look at two options.

Factoring $n$. If I factor $n$ using a brute-force attack, I then use the factorization to compute $d_1$ and $d_2$. Computing both $d_1$ and $d_2$ is not much more than just computing $d_1$ since you broke the factorization.
Instead of factoring $n$, what if you try to brute force $d_1$ and $d_2$. Recall that $d_i$ is chosen such that $e_i d_i\equiv 1\bmod{\varphi(n)}$. Furthermore, $(m^{e_1})^{e_2}=m^{e_1e_2}$. Raise that to $d_1d_2$ and you get $m$ back. Therefore, you really need to bruteforce $d_1d_2$ instead of $d_1$ and then $d_2$ (or vice-versa). If you assume each of the $d$s are $l$ bits, brute forcing $d_1$ then $d_2$ would be like brute forcing $l^2$ bits. Brute forcing $d_1d_2$ on the other hand is $2l$ bits. One could argue that this is harder, but asymptotically it isn't.
Brute force only $d_1$ then factor. It turns out if you know $d_1$ you can easily factor $n$ then use the factorization to compute $d_2$. (This comes from @CodesInChaos comment).

Any other brute force options you had in mind?

[*] My description of double encrypted RSA here is assuming textbook RSA. For padded RSA (which is what you find in the real world), points 1 and 3 are still valid, 2 however is not.

Assuming that you use a IND-CPA,CCA secure assymetric enncryption scheme that leaks some kind of information from the ciphertext. By re-encrypting the message is like you encode into a different form and you achieve all-or-nothing security. That means that the attacker in order to reveal 1 single block he should break the message in its entire form. A second point is that you actually re-encrypt sth if you have an intermediate node that transforms messages of key k1 into messages encrypted with key k2. This is so callade proxy re-encryption and is done for delegation of operations and transitivity purposes.


Deciphering the RSA encrypted message from three different public keys I have three different 1024-bit public keys with common exponent $e$ but different moduli. A message $m$ is encrypted (without padding) using the three keys, which results in three different encrypted messages.

Given the three pairs of public keys $(N_i,e)$ and the encrypted messages $c_i=m^e\bmod N_i$ , how do I decipher the original message $m$ ?

In the question, the same message is directly encrypted to three different public keys using textbook RSA. This has dire consequences, including the following (with 1./2./3. not using the multiple public keys, and the answer likely thought at 5. or its extension 6.):

It severely limits the size of the message (to less than 128 octets).
A guess of the message can be checked by anyone with a public key $(N_i,e)$ and the ciphertext $c_i$, which by a standard assumption in cryptography includes adversaries. They simply encipher a guess of $m$ with $(N_i,e)$ and check it against $c_i$. Poof goes confidentiality if the message is a name on the class roll, a guessable password..
If $m$ is less than say $2^{70}$ , there is a good chance that there exits $r<2^{30}$ and $s<2^{40}$ with $m=r\cdot s$. In that case, regardless of $e$, there's a meet-in-the-middle attack recovering $m$: the attacker computes $c_0/r^e\bmod N_0$ for all candidates $r$ and store that for quick search (10 GiB of RAM for hash tables and 128 GiB of seldom used disk will do); then for each candidate $s$ computes $s^e\bmod N_0$ and searches that; it there's a match, $m$ is found as $r\cdot s$ .
If $e$ is small, and/or the message $m$ is small enough (less than about $2^{1023/e}$ ), then $m=\sqrt[e]{c_i}$ (where $i$ is the index of the largest $N_i$ and it is used straight, not modular arithmetic). Even though the $c_i$ are distinct, this attack could still work in the case at hand, when $m$ is close enough to the limit $\sqrt[e]{\max(N_i)}$ . Further, that eth root attack can be easily extended to like $m<2^{1060/e}$, and much more when we consider the multiple encryptions, see 6.
If $e=3$, the system is plain vulnerable to the archetypal RSA broadcast attack (also the simplest form of Håstad's broadcast attack). $e=3$ is a common choice in textbook RSA, because that allows the fastest encryption, using modular squaring and one modular multiplication; and is as safe as can be when $m$ is essentially random in an interval like $[0,N_i)$ and chosen independently for each encryption (contrary to the situation at hand where the same $m$ was used thrice).

We should first check that the three $\gcd(N_i,N_j)=1$ for $0\le i<j<3$. Otherwise, the GCD is a non-trivial factor of $N_i$ and $N_j$, and we have factored $N_i$ and $N_j$ (at least in two-factors RSA), and can compute a working private exponent and decipher, per the normal way in textbook RSA. Succeeding in that way is not supposed to happens, but does here and there, due to Random Number Generators that are not true, and gave the same results on different platforms, when they should not; and in academic exercises.

Having thus checked (or blindly assumed) that we can invoke the Chinese Remainder Theorem, we use it to solve for $x$ the system of 3 equations $x\equiv c_i\pmod{N_i}$ for $0\le i<3$ with $x\in[0,\prod N_i)$. That goes:

$x\gets c_0$
$N\gets N_0$
For each $i$ with $1\le i<3$

$x\gets(((N^{-1}\bmod N_i)\cdot(c_i-x))\bmod N_i)\cdot N+x$
$N\gets N\cdot N_i$

At that point $N=\prod N_i$, and $x$ is the desired solution.

Then we computes $m=\sqrt[3]x$ (which will be an exact integer); this is a non-modular cube root, and thus easy. This will always work because $m<\min(N_i)$, thus $m^3<N$, thus $m^3=x$ since by the CRT, there's no other $m$ with $m^3\equiv c_i\pmod{N_i}$.
Attacks 4. and 5. combine and can work for some $e>3$. If $m<\sqrt[e]{\prod N_i}$ , then after computing $x$ just as above it comes $m=\sqrt[e]x$ (which will be an exact integer).

This can be extended to $m$ up to about $(3072+k)/e$-bit with with $O(2^k)$ work; with $e=5$ perhaps $m$ up to $\approx78$ bytes (out of the maximum capacity of $<128$ bytes). An idea is to scan integers $r$ with $0\le r<2^k$, until $\sqrt[e]{r\cdot N+x}$ is an exact integer.

Further, we can save significant computational work in this search by reusing an approximation of $\sqrt[e]{r\cdot N+x}$ in order to test if $\sqrt[e]{(r+1)\cdot N+x}$ is an integer, and computing an approximation of $\sqrt[e]{(r+1)\cdot N+x}$.

And perhaps that attack can get even better; see this answer wondering about extending the eth root attack by combining Coppersmith's theorem with lattice methods.

Conclusions:

Do not use textbook RSA without random encryption padding, unless enciphering a mostly random $m$ nearly as wide as the public modulus, and enciphering that $m$ only once.
Rather, use a sound random padding for each RSA encryption, and hybrid encryption for the whole thing.
Do not conclude that a large $e$ like $e=65537$ will always save the day; it does not. Apply the above!

If $e$ is low, you can do next:
Solve system of three equations $x_1=c_1 \bmod n_1$, $x_2=c_2 \bmod n_2$, $x_3=c_3 \bmod n_3$ using Chinese Reminder Theorem. You should obtain result like $x=a \bmod n$.

Then calculate e-th degree root of $a$.

This works with low exponents, because it's hard to compute n-th degree root.


How come Public key cryptography wasn't discovered earlier? I became interested in crypto lately and read about symmetric and public key crypto algorithms. I understand how crucial the discoveries of the 1970s like RSA, DES and DH were in advancing the technology.

I just don't understand how public key cryptography as an idea just came less than 50 years ago while it was a highly desired solution throughout history and kingdoms/countries/intelligence services would pay handsomely to whoever discover this simple yet revolutionary idea.

Things like integer factorization and elliptic curves were studied since the 19th century, how come nobody thought of using such known mathematical problems to create strong crypto systems, especially in WW1 and WW2 where confidentiality and integrity of data could decide the fate of a whole nation, instead of relying on centuries-old futile crypto techniques?

I am sure that this wasn't a lack of human resources, every European country had lots of geniuses, so why  wasn't public key cryptography discovered until so late?

If you read about Merkle's experience with bringing the subject to the mainstream, you might be surprised. His professor rejected his initial proposal and show little interest in any further developments:

...We were required to submit two project proposals, one of which we would complete for the course. I submitted a proposal for what would eventually become known as Public Key Cryptography -- which Hoffman rejected. I dropped the course, but kept working on the idea.

He showed it to a different faculty member and was encouraged to publish it. His proposal to the Communications of the ACM was rejected:

... I showed an early draft to Bob Fabry, then on the faculty at Berkeley, who immediately recognized it as both novel and valuable and said "Publish it, win fame and fortune!" I then submitted it to Susan Graham, then an Editor at the Communications of the ACM in August of 1975. As I was to learn, Fabry's response was rare.
Graham sent my submitted paper out for review and received the following response from an "experienced cryptography expert" whose identity is unknown to this day:
"I am sorry to have to inform you that the paper is not in the main stream of present cryptography thinking and I would not recommend that it be published in the Communications of the ACM."
"Experience shows that it is extremely dangerous to transmit key information in the clear."
With this blanket rejection of public key cryptography by an "expert", she rejected my article. She "was particularly bothered by the fact that there are no references to the literature. Has anyone else ever investigated this approach. If they consider it and reject it, why?"

Novel concepts that aren't "mainstream" can be difficult to accept:

I had failed to provide any references to the prior work on public key cryptography, and the reasons previous workers in the field had rejected it as impossible. I should have looked up "public key cryptography" on Google before submitting my paper. My defense is feeble: there was no Google, the term "public key cryptography" did not yet exist, and there were no previous workers in the field. There were no words for what I had done, and looking up a concept to show that no one had previously thought of it is difficult. This is not a unique problem: it illustrates a problem faced by anyone trying to explain a new idea to an "expert" who expects a properly referenced article anytime anyone tries to explain something to them. The more a new idea is unrelated to any prior idea or concept the more it must appear as a squawling bastard, naked and alone, appearing de novo and lacking any respectable pedigree or family to vouch for its acceptability.
... CACM eventually published the paper, though only after almost three years of delay, and only after others (who were better able to persuade their editors to publish in a timely fashion).

Conclusion
While the utility of public-key cryptography is obvious to us, this was not always the case. Encryption that is secure when you know the key almost sounds like something that can't exist because it would be too good to be true. So you can certainly forgive people for not pursuing the idea seriously.

Temporarily setting aside public key crypto specifically, I want to expand on a tangent from @fgrieu's answer.

Frankly, before digital computers the need and use for what we now consider strong encryption was minimal.  Asymmetric encryption is particularly vulnerable but not alone in this regard.

Functionally, breaking crypto is about effective keyspace. To put that in to practice there are three steps:

Determine the method used.  One of the desired properties of an encryption scheme is signature reduction.  It goes without saying that you want to avoid cryptographic weaknesses that leave artifacts in the cipher, but going further than that you also want to avoid leaving leaving indication of what cipher was used in the first place.

A perfect cipher would be indistinguishable from random noise for anyone not in possession of the full decryption settings, or to put it another way, the only way to validate a cipher's integrity is to decrypt it.  If you can't tell which of 10 ciphers I used then I've multiplied the work you need to do to break it by 10.
Identify the weakest points. No cipher should be assumed perfect, at best we can say there are no known attacks.  Trying to find attacks on the cipher itself is an important part of cryptanalysis, both from the desire to break the cipher and for proving its strength.

Equally, people's application cryptography can't be assumed perfect.  People tend to be dumb about these things.  The more human involvement there is in the process, the more chance they'll mess something up and make your life easier by weakening things.
Compute through whatever keyspace is left.  Unless you get really lucky, chances are you've still got more than 1 permutation left to try. So you'll need to try decryption with each permutation left in your keyspace.  Maybe you'll find an working set of inputs after 1%, maybe it'll be at 99%.

So here's the thing.  You don't need an especially large keyspace when the computers are people with paper, that's why combination locks (kinda) work.

From the actual key perspective, a 3 digit combination has a keyspace of 1000 combinations.  From my experience with a particular type of 3 wheel combination lock I figure about 20-30 minutes on average to get the code purely by exhaustive search. Finding a good weakness or mechanical speed up will reduce the effort needed by at least an order of magnitude and often far more.

Even as recently as WW2, Enigma was sufficient.  Actually, properly used Enigma is still hard to crack.  Ciphers that require fast computers to use effectively aren't practical without said computers.  Ciphers based on mechanical implementations that are hard to optimise mathematically or computationally, those are the ones we wanted for a long time.

So, why are asymmetric ciphers particularly vulnerable?  Well it depends on what your goal in choosing it is.

In one case, asymmetric encryption is good for adding an authenticating factor to the message.  With symmetric encryption possessing the key means you can forge the messages as well as intercept them.  If you're using an asymmetric scheme you can only impersonate or receive the key you have.  Yeah, this does work but you can achieve the same thing in other ways without the drawbacks of using 1:1 messaging schemes when broadcasting information.

In the other case, the public part of public key refers to using the ability to publish the key to enable a more secure exchange of another (usually symmetric) key.  Exactly how and what is exchanged in the process varies.  The issue is that most of the benefit requires real time communication and extra work and using separate mechanisms for the sending and receiving portion.

A modern analogy for using PKI for the first purpose is PGP and its family, where asymmetric encryption and PKI is used both for authentication and securing messages.  You can maybe follow why it's less effective by considering a mailing list where everyone is sending PGP encrypted messages.

The second purpose, is what most people think of when talking about Public Key encryption... it's what makes HTTPS and SSH work.  Imagine if, every time you wanted to make a phone call, you had to read out a 10 digit number, write one down, punch the new one in to the phone, and then hope you can both understand each other.

The biggest problem with PKI specifically, going back to the three stages I talked about above, is that to effectively perform stage 3 you ideally need to have done stage 2, and to do stage 2 effectively you need to have done stage 1.  PKI, by nature and design, publishes not only part of the cipher settings but what cipher you're actually using.  With computers in the picture you can compensate for exposing that information by just making the key space many many orders of magnitude larger.  Still, if you can, it's always preferable to reduce how much you information you reveal to an adversary.

So, given the issues, and the fact that it only really becomes useful with the advent of trust infrastructure, electronic computation, fast high quality telecommunication and key exchange algorithms... it's actually not surprising that it didn't become notable earlier, evidenced by the difficulties mentioned in the answer from @ella-rose.


Using error-correcting codes for the bootstrapping procedure of Fully Homomorphic Schemes In the context of Fully Homomorphic Schemes, we use a technique called "bootstrapping" to refresh the ciphertext, by evaluating homomorphically the decryption circuit with an encrypted version of the private key.

I was wondering if it was possible to consider this approach, of reducing the error size, by using an error-control code instead (eventually designed for our FHE scheme).

I am not concerned about the efficiency of such a scheme right now, but would it be feasible to design a scheme such that we can apply an "error-reducing code" reducing errors instead of correcting all of them. I don't think there have been researches to this idea so far so it is maybe completely unthinkable but I wanted to discuss it with other people..

I think not, because the two types of error correction are doing fundamentally different things.

Conventional error correction schemes, for instance Reed-Solomon codes, expect the value to be near some codeword.  To correct an erroneous value, they change it to the nearest codeword.  You can picture it as a space where some points in the space correspond to correct values, and each of those points is encircled by a region of incorrect values that belong to that point.  The assumption of error correction is that value started at a correct point and drifted a little, but stayed in the point's own region.

With LWE, you are mixing the correct value with a ton of error, and secretly you know some way to unmix it later (bootstrapping).  You can't use less error and still have security.  In terms of the point analogy above, the incorrect values have to be all over the space.  They can't stay close to their correct value in any obvious way.  Otherwise anybody could see what the correct value is - it's the nearest correct point.  I doubt that you can use any conventional error correction without having obvious regions of some kind.

Error correction doesn't do much for the bootstrapping either, I think, because once you unmix the value, you can just throw away the error part.


Multi Factor Encryption? I got an alert last night to the keywords above and was curious, so took a look at the tor site flagged which is the following one:
http://nsrz5iogimqwgeax3clpp6hvfy6viom2woy7dghgxes4sqk63r7svoqd.onion. Obviously you need TOR to access it or a service like Tor2Web though reachability is spotty.
I'm asking SE because these guys are claiming to offer a cipher strength I've never heard of. I'd like to ask if you think it's even possible.
This question is about the encryption scheme "Blobby" presented on their site and the security claims surrounding it.
The first notation they use is $10^{yM}$ which I didn't get, but just below is an example $10^{41485806}$, which seems obscene with the unit to of the previous number being "operations", which can be inferred from them stating a relative strength of $10^{38}$ for AES-128 which is roughly $2^{128}$.
Now that I've have longer to look at it, it feels less impossible (though still a stretch), I think the key size and password length are important, but I suspect they're using a third mutagen.
The key claim of novelty for this encryption scheme is that both a nearly-arbitrary sized password (20-$2^{12}$ chars) and an arbitrary sized key ($2^{16}$-$\infty$ bit) are necessary for symmetric operation yielding "multi-factor security" with their custom encryption scheme. The precise quote is

Blobby is fundamentally different, the password is used in conjunction with the key, meaning that each is useless without the other, and attacking the key's password won't get you any closer to the message password.

If their claim is solid, would this be quantum resistant?
I have now downloaded the 3 sample files and looked at them, they are clearly encrypted. I've been trying the first sample for over 24hours now with not a whisper of joy.

Oh boy. Snakeoil at its finest.

This question is about the encryption scheme "Blobby" presented on their site and the security claims surrounding it.

Inventing and selling completely new symmetric encryption? One of the best indicators for snakeoil.

The first notation they use is $10^{yM}$ which I didn't get, but just below is an example $10^{41485806}$, which seems obscene with the unit to of the previous number being "operations", which can be inferred from them stating a relative strength of $10^{38}$ for AES-128 which is roughly $2^{128}$.

It seems they use big numbers for the sake of using big numbers and impressing people. For all practical purposes nothing beyond 256-bit security matters unless you want to invest the entire energy of the sun for most of its lifespan into breaking it. Double that number if you want to go "sure" against quantum computers thanks to Grovers provenly optimal search algorithm.

If their claim is solid, would this be quantum resistant?

It could be that their scheme is quantum-resistant. Symmetric crypto is rather easy to get quantum-resistant. But we don't know until they actually publish a description and even then we might not know because people won't care enough to analyze this scheme.

I'd like to ask if you think it's even possible.

Yes, you can build multi-factor encryption and you can build it nicely out of standard cryptographic primitives.
Now for the actual question you are probably having: "Ok, this is all snakeoil they're trying to sell me and you're saying that we don't need this, so how would you do it in practice?"
Well turns out people already did look at this problem, i.e. how to combine something that you know (like a password) with something that you have (i.e. a pre-generated key, a key-file or a security token).
My favourite three examples for this are the softwares VeraCrypt, BestCrypt and KeePass, which all handle this in a different way.

VeraCrypt will essentially mix your keyfile(s) with your password using their funky custom hash function and then run this through standard password-based key derivation. A random salt from the ciphertext will still be used.
BestCrypt will hash each of your keyfiles individually and then sort the hashes and prepend the hashes to the salt before key derivation.
KeePass will hash your keyfile and concatenate it with your password before feeding that into the password-based key derivation. A random salt from the ciphertext will still be used.

Obviously you need both inputs in all three cases to mount a brute-force / dictionary attack. Also note that any attack that would allow you to recover the password-based key derivation input without actually doing the forward iteration would be considered a major publication-worthy break. And yes there are publications that show that for standard password-based encryptions the optimal strategy is to search the password space or guess a secret symmetric key, the best one of which is probably by Bellare, Ristenpart and Tessaro (Theorem 3.4).

@Greeny: To answer your questions.
1: Yes the numbers are possible.
Justification:
A BasicHex(0-F) Grid 16x16 gets you 16256 or in decimal 1.797x10308
A BasicHex(0-F) Grid 32x32 gets you 161024 or in decimal 8x101232
The formula we provided on the site, was simple enough, CharTypeCount(BlockSize x BlockCount).
Does anyone disagree with the structure of this math?
The sample files burned over 100,000 blocks each, and we use more than just basic hex char’s.
But in truth the numbers are irrelevant, see answer 2.
2: Yes it should be quantum resistant.
https://en.wikipedia.org/wiki/One-time_pad
How is the One Time Pad (OTP) perfectly secure?
Both of the above links consider the OTP to be ‘Perfectly Secure’ , it was however abandoned in favor of modern ciphers for 2 reasons:

Key transportation became impractical as data volumes increased.
Truly random keys are incredibly difficult to produce.

We solved the first by improving the efficiency of block generation/usage, and quite by accident appear to have solved the second as well (NO we are not claiming to have created a next gen RNG, this we would have published) .
That said we’ve been testing it for some months now without any persistent patterns being detected. Still, we accept that without a lot more testing, any claim to have completely solved the random challenge would be pointless.
3: No. Joe public has no real need for it, unless they’re involved in the sort of activities where they probably shouldn’t have it. As we state on the site, it’s intended for players with data that NEEDS, to stay secret for a protracted period, be that on storage or in transit.
Lastly we would ask you to remove the second tag from the thread:
Why?

Blobby doesn’t claim to be a new cipher, it’s a new engine. One based on OTP instead of the Boolean of modern ciphers.

It works! The sample files are provided as proof, it might also be worth noting that a 10KB key (+PW) encrypted 5MB of data using OTP principles, and it did it without repeating.

If it’s snake-oil, why make it clear from the beginning that it is not suitable (overkill) for 90% of the market?


Why can't we use a hash with no collision to compress data reliably? According to wikipedia, a hash maps digital data of arbitrary size to digital data of fixed size.

For all practical measures, a hash is a unique signature of a big chunk of data. But there is such a thing as a collision free hash, I "heard".

Other than being able to decompress back, arguably the main difference between compressing and hashing is precisely that collision factor - but what if the hash has no collisions?

Why exactly can't we "just" get that "perfect" hash and use it as a compressing method instead? Wouldn't it be able to generate way smaller files?

I see how I must be just missing something, so it's just my way of trying to understand what's the underlying difference between hashing and compressing! :)

Mathematically speaking, there is no such thing as a collision-free hash. Practically speaking, there is.

Cryptographic hash functions in good standing have no known collisions. That's one of their defining properties. They do have collisions, but there isn't enough computing power on Earth (if not in the whole universe) to find one, given current mathematical knowledge. A SHA-1 value is 160 bits, so we know that there exists a pair of 161-bit strings that have the same hash, but the best-known techniques to find one are out of range of current computing power (not out of range of imaginable computing power, though, which is why we're moving away from SHA-1).

Intuitively speaking, if it's hard to find collisions for a hash, the hash is hard to inverse. If there was a known algorithm to invert a hash, then at some point the algorithm would have to decide which of the possible preimages to go for, and we could run it with both decisions to find a collision.

It is possible to use a hash as a compression function. But since there is no way to calculate the original text from the hash, this compression method can only be used when the original text is available. Sounds useless? Not quite. In fact, that's one the basic reasons to use hashes! Cryptographic hashes are used when there are two storage or communication mechanisms, one that's secure but supports only a small volume of data, another that's insecure but supports a large volume of data. Store the hash on the small, secure storage and the actual data on the large, insecure storage. Then, when you need the file, retrieve the data, retrieve the hash, and check the hash. In this way, the secure storage mechanism uses the hash as a compression function; the decompression function makes use of the insecure storage, but guarantees the security of the outcome. (You'll not that something is lost, however: if the insecure storage is corrupted, this will be detected, but cannot be corrected. The “decompression” mechanism guarantees integrity (if you get the data back, it's the right data) but not availability (you might not be able to get the data back).)

Seen another way, a cryptographic hash can be used as a compression mechanism, but this requires that each time a new file is stored, the decompression function is somehow modified to remember the original file content. This is clearly impractical, but it is of theoretical interest — this basically describes a random oracle, which is a sort of idealized version of a cryptographic hash.

A perfect hash is a different kind of beast: it is mathematically collision-free, but it achieves that by restricting the possible inputs to a finite (usually small) subset of all possible inputs. The decompression function for a perfect hash is usually stored as a table from hash values to the corresponding original data (for example using an array if the hash values are small integers).

If you have enough computing power to crack a hash, you can send big files over the internet almost instantly, reducing the need for expensive and powerful network infrastructure, you would have to crack it faster than it takes to download the file to be worth it at least time wise, it may be physically, economically and technologically inefficient or even impossible to have a smartphone/computer the same size and price you have but fast enough to be able to crack hashes like a supercomputer can, or even every supercomputer on earth and universe combined can't.
If you find a way to crack hashes instantly with a portable quantum computer for example, then it would be a good way to reduce network load and make the internet almost instantaneous or you can find a way in the middle that you would be able to compress files using more than a hash, perhaps a hash and many parameters in a text file, to guide the cracking algorithm the right way, in password cracking for example it takes a very long time to bruteforce a password when you have absolutely no information about the length or character set of the password, but if only you had the length and character set of the password it would significantly reduce the time used to crack the hash.The same thing could be done with larger files/information.Here is a small example :

Hash and parameters :
sha1:  19f054f1f448ff152f1d586be39a56f179fe80c9
Lowercase letters only : yes
Words in a dictionary : yes
Length : 13

Result : stackexchange


Are all public-key encryption protocols based on one-way functions? Are there any public-key cryptography protocols which don't rely on one-way (or trapdoor) functions?

RSA and Diffie-Hellman cryptographic protocols both rely on one-way functions (prime factorization and discrete logarithm). Lattice-based cryptography is based on the Shortest Vector Problem which is NP-hard, but is it a one-way function?

Yes, all public-key cryptography based on one-way functions. Every one-way function builds on some hard problem. There is many one-way functions in lattice-based crypto, that based on SVP. For example, NTRU one-way function, LWE one-way function, etc.


ZKP: Asymmetric encryption with confidential message and known hash I'm searching for a ZKP package that supports asymmetric encryption so I can implement the following scenario:

Carol encrypts message $m$ with Alice's public key and sends the ciphertext to Alice. Bob and Alice both know $\operatorname{hash}(m)$, but because $m$ is encrypted by Alice's public key Bob doesn't know $m$--only Alice knows $m$.

Here is the part that needs ZKP: Alice wants to prove to Bob that this ciphertext is actually the encryption of a message whose hash is $\operatorname{hash}(m)$.

In other words, I want to be able to prove that I have a value whose hash is equal to y = hash(a), and whose encrypted form is z = enc(a), but I don't want to reveal a.

I searched in ZKP packages thoroughly, but none of them can implement encryption, so I take it that ZKP isn't the solution.

Do any of the available packages support what I am trying to do?

If you wanted to prove a statement like hash(a) = y, I would recommend you to use a generic  zero-knowledge protocols which proves the computation of a boolean circuit using a witness w like presented here and here. The authors first paper even published a reference implementation of SHA256 on github. Even though it's not impossible to additionally prove a statement like z = enc(a), I would recommend you not to do that for several reasons:

The performance will likely be poor due to the expected circuit size and depth.
Considering the adversary model you want to be secure against and the algorithm you choose, it may be still possible to create attacks if you don't pay attention.

If possible, just wrap the message (in your case - the $hash(m)$) with HMAC which is used for authentication.

According to wikipedia:

  In cryptography, an HMAC (sometimes expanded as either keyed-hash message authentication code or hash-based message authentication code) is a specific type of message authentication code (MAC) involving a cryptographic hash function and a secret cryptographic key. It may be used to simultaneously verify both the data integrity and the authentication of a message, as with any MAC

There are plenty of HMAC implementations so it will be easy to find a package suitable to your needs.


DES and AES cryptography I have a question that I can't answer:

  A plain text has been encrypted 3 times in a DES method with 3 different keys 56 bit each, after it the text was encrypted for the forth time using a AES method using a 128 bit key, an attacker is planning to decrypt the text using meet in the middle method, how many encryptions and decryption approximately he need to do.

  $2^{56}$
  $2^{112}$
  $2^{128}$
  $2^{168}$
  $2^{184}$
  $2^{240}$
  $2^{296}$

Assuming this is ECB mode encryption, the workload of a known-plaintext meet-in-the-middle attack will depend strongly on the plaintext here.

If the plaintext contains some non-identical 128 bit blocks that partly coincide on a DES-block, the adversary can reverse the final AES encryption with $2^{128}$ AES decryptions work factor. They can then execute a standard meet-in-the-middle attack on 3DES using parallel collision search (easy compared to the preceding step). See van Oorschot/Wiener for details on the techniques used.

If the plaintext consists only of non-identical 64-bit blocks, the adversary can use the same idea (look for collisions of 64-bit blocks in the ciphertext after AES decryption) to at least rule out some AES keys. They should be able to rule out the vast majority of AES keys when the size of all encrypted plaintexts significantly exceeds the birthday bound for a 64-bit block cipher.

If the plaintext is short and does not contain repetitions of DES blocks that are not also repetitions of AES blocks, there may be no better idea than to perform a meet in the middle attack between 3DES and AES using parallel collision search. This should be doable in time about $\approx 2^{212}/(\sqrt{w} m)$ on a machine with $2w$ AES blocks of memory and $m$ processors (see again the parallel collision search paper).

I believe the the MITM attack for 3DES is $2^{112}$, so if MITM attack is between the 3DES and the 4th AES, the most expensive brute force attack between the two is the AES one, which is $2^{128}$.

So all it takes is $2^{128}$ encryptions / decryptions.

Note that I am trying to learn this myself too!


What is the exact purpose of length padding in Merkle–Damgård hash functions? Is a length padding technique in a hash function used to avoid length extension attacks ?

Hash functions are defined to work on an arbitrary integer number of blocks. The minimal quantity of data that can be processed by an hash function is a single block.

So, if the message size is not an integer multiple of the block size one has to pad it to the right size.

One needs also to make the message + padding have one and one only interpretation, otherwise it would be simple to create collisions. Therefore adding the padding lenght gives an unique way to interprete the message+padding couple.

As example: let's imagine that one pads addings just zeros to achieve the right lenght. Therefore message $m$ and message $m||0$ have the same hash image.


How should I calculate the entropy of a password? If part of the password is a whole regular English word, does the entropy of that part depend on the number of English words in existence, the number of English words known by the choosing algorithm, the number of English words assumed by the attacker?

Does the language matter, is the average entropy per word in German, French, Italian, or Spanish significantly different from the average entropy in English?

Does a numeric digit always have an entropy of $\log_2(10) = 3.321928$?

Entropy is a measure of what the password could have been so it does not really relate to the password itself, but to the selection process.

We define the entropy as the value $S$ such the best guessing attack will require, on average, $S/2$ guesses. "Average" here is an important word. We assume that the "best attacker" knows all about what passwords are more probable to be chosen than others, and will do his guessing attack by beginning with the most probable passwords. The model is the following: we suppose that the password is generated with a program on a computer; the program is purely deterministic and uses a cryptographically strong PRNG as source of alea (e.g. /dev/urandom on a Linux system, or CryptGenRandom() on Windows). The attacker has a copy of the source code of the program; what the attacker does not have is a copy of the random bits that the PRNG actually produced.

Entropy is easy to compute if the random parts of the selection process are uniform (e.g. with dice or a computer with a good PRNG -- as opposed to a human being making a "random" chance in his head). For instance, if you have a list of 2000 words and choose one among them (uniformly), then the entropy is $S = 2000$. Entropy is often expressed in bits: an entropy of $n$ bits is what you get out of a sequence of $n$ bits which have been selected uniformly and independently of each other (e.g. by flipping a coin for each bit); it is a simple logarithmic scale: "$n$ bits of entropy" means "entropy is $S = 2^n$" (and the attack cost is then $2^{n-1}$ on average).

If you think of a password as two halves chosen independently of each other, then the total entropy is the product of the entropies of each half; when expressed with bits, this becomes a sum, because that's what logarithms do: they transform multiplications into sums. So if you take two words, randomly and independently (i.e. never ruling out any combination, even if the two words turn out to be the same), out of a list of 2000, then the total entropy is $2000\cdot2000 = 4000000$. Expressed in bits, each word implies an entropy of about 11 bits (because $2^{11}$ is close to $2000$), and the total entropy is close to 22 bits (and, indeed, $2^{22}$ is close to $4000000$).

This answers your question about digits: a decimal digit has entropy 10, as long as it is chosen randomly and uniformly and independently from all other random parts of the password. Since $10 = 2^{3.321928...}$ then each digit adds about 3.32 extra bits to the entropy.

If a human being is involved in the selection process then calculating the entropy becomes much more difficult. For instance, if a human chooses two digits and the first digit is '4', then the probability that the second digit is '2' is quite higher than $\frac1{10}$. It could be argued that it is also difficult for the attacker: he will also have more work to do to sort the potential passwords so that he begins with the most probable. But this becomes a psychological problem, where the attacker tries to model the thinking process of the user, and we try to model the thinking process of the attacker: it will be hard to quantify things with any decent precision.

The entropy for a randomly generated password is based on the character Library space (i.e. range of valid characters) and then the length of the passwords (i.e. total number of characters in the password), and with no other constraints (i.e. ability to have a random message that produces a password of all the same characters even if it is unlikely for that to occur).

In such a setup, the entropy will be the
$log_2{(Library^{length}}$), see below for examples and Claude Shannon's formula.

The entropy "H" of a discrete random variable "X" is defined as:

${\\H(X) = -
\sum_{i=1}^{n}
 P(x_i) \  log_b P(x_i)
}$

If the English word is a mnemonic and represents some underlying index value or other code value such as ASCII or UTF-8, then I don't think there is a difference so long as it was chosen randomly, as its entropy will depend entirely on the range of words or letters that it was chosen from. There is a difference though between the user choosing a word, versus randomly chosen letters that "happen" to equal a word when read from left to right etc..

Here is a simple explanation regarding password entropy, and depending on what needs to be measured. Let's first assume two following two points:

The password has a specific "length" (consisting of its
number of characters, some of - or all of which - may be
duplicate/identical and/or repeat consecutively).
Any character in the password has been chosen from a single common library or "range" of unique characters and chosen randomly using a cryptographically secure process.

Formula:

Log2(Possible combinations)= overall password entropy
Range^Length=Possible combinations (can also be rounded as 2^overall password entropy)
Log2(Range) = Entropy per character
Entropy per character * Length = overall password entropy

Example Test:

Range = 2048 unique character values (or 2048 unique words)
Length =12 characters (or 12 words, some or all of which may repeat)
Possibilities = 5444517870735015415413993718908291383296 or 2048^12
Overall Entropy = 132 or log2(possibilities)
Entropy per character (or per word if words are used) = 11 or log2(2048)

Another way to double-check roughly (depending on precision available if dealing with decimals and not whole number results): 2^(log2(Range)*Length) == (2^Entropy)

In Python3: 2**(int(math.log2(2048))*12) == int(2**132)

P.S. I think frequency analysis is useful here in two situations, one) the password was chosen deterministically without a crypto-secure process, and/or two) the characters in the library are either not distinctly unique (i.e. one or more duplicates exist, or many characters share strong similarities) or other unknown leakages of information in the library set.


SHA-1 collisions - what about practical attacks? I understand the theoretical problem with hash collision but when it comes to practice, I get very confused.

Suppose a attacker would like to forge a certificate (or any kind of structured piece of file) using hash collisions, I wonder how it is possible to find a collision (already unlikely) and moreover, this collision is "found" from relevant structured input bytes (dates, common name, dns attacker).

It sounds very strange for me, I can't understand how one can found a hash collision which helps as an attack, I can only think about a random raw bytes which could generate a same hash, but it would not be parsed (ex: x509 certificate hash collision find by an attacker, but the x509 malicious content is random bytes not understandable by browser).

The question asks how a collision in a hash such as SHA-1 could become a practical concern, with focus on the case of a public-key certificate à la X.509.

I'll first give an example involving executable code signing. I'll assume an attacker in a position to write bootstrap code (like, the supplier of a development toolchain, or someone who compromised that toolchain), and enough resources to perform one single attack finding two distinct 128-byte colliding messages on SHA-1 with a small change: the value of the (arbitrary) 160-bit initialization value. The later is possible

by brute force with expected effort less than $2^{81}$ hashes (about the effort devoted to bitcoin mining in a year according to that source) using Paul C. van Oorschot and Michael J. Wiener's Parallel Collision Search with Cryptanalytic Applications (in Journal of Cryptology, January 1999, Volume 12, Issue 1; free slightly earlier version available from the first author's website);
or with less effort using complex specialized methods exploiting weaknesses in SHA-1's compression function, with an estimated effort comparable to

$2^{69}$ hashes, per Xiaoyun Wang, Yiqun Lisa Yin, Hongbo Yu: Finding Collisions in the Full SHA-1, in proccedings of Crypto 2005),
$2^{63}$ hashes, per Xiaoyun Wang, Andrew C Yao, Frances Yao: Cryptanalysis on SHA-1, rump session of Crypto 2005; see also Martin Cochran: Notes on the Wang et al. $2^{63}$ SHA-1 Differential Path, in IACR eprint archives, 2007),
$2^{61}$ hashes, per Marc Stevens: New collision attacks on SHA-1 based on optimal joint local-collision analysis (in proceedings of Eurocrypt 2013, also freely available from the author's website).

Suppose an executable file format consisting of

: 4-byte magic value 0x4D6F4546 (My own Executable Format)
: 4-byte length of bootstrap code, allowing to locate section 4
: bootstrap code with entry point at offset 8
: 4-byte length of section 5, allowing to locate the signature
: (anything)
: PKCS#1v2 RSA-4096 signature of the SHA-1 hash of 1-2-3-4-5.

The attacker writes or adapts bootstrap code 3 so that the executable is

: 4-byte magic value 0x4D6F4546 (My own Executable Format)
: 4-byte length of bootstrap code, allowing to locate section 4
: bootstrap code with entry point at offset 8

: code that gets the value of $k$ from section 3.4, then jumps to section 3.6 or 3.5 according to if $k^\text{th}$ bit of section 3.3 is 0 or 1
: filler data so that 3.3 is aligned to a 64-byte boundary
: 128-byte data block
: 4-byte $k<1024$ such that the two values of section 3.3 differ in the $k^\text{th}$ bit
: code performing whatever the attacker wants to perform
: code performing whatever the bootstrap is supposed to perform

: 4-byte length of section 5, allowing to locate the signature
: (anything)
: PKCS#1v2 RSA-2048 signature using SHA-1 hash of 1 / 2 / 3 / 4 / 5.

The adversary needs to

know 1 / 2 / 3.1 / 3.2 when starting the attack
apply enough rounds of SHA-1 to deduce the 160-bit SHA-1 state after hashing 1 / 2 / 3.1 / 3.2, giving the 160-bit initialization value of the SHA-1 variant attacked
perform one of the costly attack at the beginning of this section
having found two 128-byte colliding data blocks, determine a bit index $k$ where they differ, and label the colliding blocks A and B according to if $k^\text{th}$ bit of the block is 0 or 1
construct two version 3A and 3B of the bootstrap code 3, differing only by containing block A or B in section 3.3; notice that 3.5 and 3.6 can be changed without performing the costly attack again;
plant version 3A of the boostrap, which does as it is supposed to perform
let an unsuspecting developer create an application with bootstrap 3A, and getting it signed;
obtain that signed original;
create a forgery by changing section 3.3 to block B, so that version 3B of the bootstrap is in place;
arrange for the forgery to be used on target machines, using the reputation of the application developer.

The forgery pass signature verification because the SHA-1 hash of 1 / 2 / 3 / 4 / 5 is unchanged, but when launched executes the code of section 3.5 performing whatever the attacker wants to perform, when the signed original did not.

Further, it is possible to encipher the code of section 3.5 using the block of section 3.4 as key, making it impossible to analyze the exact behavior of bootstrap 3B from the knowledge of bootstrap 3A. And code of section 3.1 can be of the form decipher-then-execute, so that the intention is less apparent.

Similar tricks can be pulled with some "data" format that are executables in disguise; e.g. that trick has been pulled with postcript and MD5.

Back to certificates in X.509-like format: consider a simplified certificate format with

: identity of the certificate holder, in ASCII on 44 bytes right padded with spaces
: public modulus $N$ of a 2048-bit RSA key, on 256 bytes (big-endian)
: (other certificate data, including public exponent, attributes..)
: PKCS#1v2 RSA-2048 signature using SHA-1 hash of 1 / 2 / 3

and one of two relevant attack models

An attacker legitimately purchases from an honest certification authority a certificate with her identity Alice and a public modulus $N_a$, modify it into a certificate with the identity of Bob and public modulus $N_b$, and holds the private keys $d_a$ and $d_b$ corresponding to $N_a$ and $N_b$ ($d_a$ is necessary to obtain the certificate; $d_b$ allows Alice to impersonate Bob);
A rogue certification authority knowingly supplies to Alice a certificate with the identity of Bob and a public modulus $N$ with factorization known to Alice (and perhaps having relatively easily found prime factors, making it more plausible that the above attack occurred), allowing Alice to impersonate Bob; and if word ever leaks that Alice impersonated Bob using a certificate issued by this authority, pretends that it has fallen to the above attack.

Note: something close to one of the above things has actually occurred with MD5-based X.509 certificates, per the evidence given here. This had been publicly described circa 2009.

In order to actually perform the attack, Alice

searches one SHA-1 collision between two 64-byte data blocks $M_a=I_a\|J_a$ and $M_b=I_b\|J_b$ with the first 44 bytes $I_a$ and $I_b$ corresponding to Alice's and Bob's identity; and 20 other bytes $J_a$ and $J_b$ arbitrary except for having the first bit set

the brute force Parallel Collision Search referenced earlier allows that with expected effort less than $2^{82}$ hashes: the function iterated can map a 160-bit value to a 64-byte block with either Alice's or Bob's identity in $I$ according to one bit; and map the other 159 bits to the unconstrained bits of $J$; when a collision is found, there is a 50% chance that it will be between a 64-byte block with different identities, thus usable;
it is conceivable to adapt some specialized methods exploiting weaknesses in SHA-1's compression function (in particular Marc Steven's publication referenced earlier describes a chosen-prefix collision attacks with expected effort about $2^{77.1}$ hashes);

finds a 236-byte value $K$ so that $N_a=J_a\|K$ and $N_b=J_b\|K$ (big-endian) are 2048-bit integers with known factorization, squarefree, and odd (and if necessary, with $N_a$ passing whatever other test the certification authority may perform, and $N_b$ passing whatever other test the entity to which Alice wants to represent herself as Bob may perform); given our message format, it is even feasible (though not required) to ensure that both $N_a$ and $N_b$ have exactly two large primes factors: we can choose $p_a$ and $p_b$ arbitrary primes about 900 bits, then systematically construct and explore $K$ such that $p_a$ divides $N_a$ and $p_b$ divides $N_b$, until both $N_a/p_a$ and $N_b/p_b$ are primes.
finds a public exponent $e$ acceptable for both $N_a$ and $N_b$ (there's a fair chance that the common $e=2^{16}+1$ will do) and compute private exponents per RSA as defined in PKCS#1, as $d_a=e^{-1}\bmod\lambda(N_a)$ and $d_b=e^{-1}\bmod\lambda(N_b)$, which is easy knowing the factorization of $N_a$ and $N_b$;
legitimately obtain the certificate with identity $I_a$, public modulus $N_a$, public exponent $e$ (which typically requires signing the certification request using $d_a$);
change $I_a$ to $I_b$ and $N_a$ to $N_b$ in the certificate (this will not change the SHA-1 hash, thus the forgery is a certificate that pass the verification procedure);
impersonate Bob using the forged certificate and $d_b$.

A countermeasure would be that certification services enforce the insertion of some unpredictable data in the beginning of certified data.

Let me add these paragraphs for clarity, but I still stand behind my below answer, as your question does not specifically address what you already understand Crypto-learner.

MD5 as an example of an older uses the Merkle-Damgard construction as do SHA1 and SHA2, however, MD5 have some intrinsic vulnerabilities like the chosen prefix collision attack which is more potent than a typical collision attack.

In 2005 an attack was successful placed upon SHA1 in less rounds than a brute force attack 2^69 as opposed to 2^80 for brute force. and this was made possible due to mathematical weaknesses within the first 20 rounds.Later in 2008-2009 similar vulnerabilities were found within the upgraded SHA1.

Note: no, the plaintext does not matter here, only the more abundant outputs from less inputs matter in relation to hash collisions.

Now below the overview of hash functions, tables and salting in my mind is relevant still because there are vulnerabilities in these areas too that can lead to hash collisions and digital security forgeries.

Crypto-learner good question so let's start with some basics and then delve a little deeper into the underlying structure of both hash functions and hash collisions.

First a hash function can utilize various tables for storage of a given series of data, each with specific benefits and detriments, like a rainbow table versus a normal data scale hash table. The hash function itself just maps an input string to some integer string. This input-output mapping applies an arbitrary length of input to a short output known as a digest.  Unfortunately as a result, a minimum of two issues can occur:

Two different strings will generate the same integer output.
The same name or data identifier will cause the same integer output to occur.

The so called collision is related to the mathematical problem coined the birthday problem via the pigeonhole principle within probability: as the sample size of hashes goes up representing n bit strings so too does a hash collision.

I would like to add two links if I may but I can answer any questions left after your reading them or add clarification.

http://www.codeproject.com/Articles/608860/Understanding-and-Implementing-Password-Hashing
http://research.cs.vt.edu/AVresearch/hashing/introduction.php

Salting helps make hashing less likely to suffer a collision via adding a random string for each n bit strings (passwords, names, etc...) and then hash them separately.

If the links are not clear or you feel you understand them and need more robust mathematical proofs I can write them out for you and explain them, but I do not want to assume what you understand or not until we talk this issue of hashing collisions out.


How big an RSA key is considered secure today? I think 1024 bit RSA keys were considered secure ~5 years ago, but I assume that's not true anymore. Can 2048 or 4096 keys still be relied upon, or have we gained too much computing power in the meanwhile?

Edit: Lets assume an appropriate padding strategy. Also, I'm asking both about security of signatures and security of data encryption.

Since 2000, on a given $\text{year}$, no RSA key bigger than $(\text{year} - 2000) \cdot 32 + 512$ bits has been openly factored other than by exploitation of a flaw of the key generator (a pitfall observed in poorly implemented devices including Smart Cards). This linear estimate of academic factoring progress should not be used for choosing a key length so as to be safe from attacks with high confidence (or, equivalently, conforming to standards with that aim), a goal best served by this website on keylength.
The current factoring record is the 829-bit RSA-250 in late Feb. 2020, see the summary by the CADO-NFS team. That came shortly after the 795-bit RSA-240 in Dec. 2019, see the detailed paper.
I emphasize that the above is about attacks actually performed by academics. As far as we know, hackers have always been some years behind (see below). On the other hand, it is very conceivable that well-funded government agencies are many years ahead in the factoring game. They have the hardware and CPU time. And there are so many 1024-bit keys around that it is likely a worthwhile technique to be in a position to break these. It is one of the few credible and conjectured explanations for claims of a cryptanalytic breakthrough by the NSA. Also, dedicated hardware could change the picture someday; e.g. as outlined by Daniel Bernstein and Tanja Lange: Batch NFS (in proceedings of SAC 2014; also in Cryptology ePrint Archive, November 2014). Or in the distant future, quantum computers usable for cryptanalysis.
By 2020, the main practical threat to systems still using 1024-bit RSA to protect commercial assets often is not factorization of a public modulus; but rather, penetration of the IT infrastructure by other means, such as hacking, and trust in digital certificates issued to entities that should not be trusted. With 2048 bits or more we are safe from that factorization threat for perhaps two decades, with fair (but not absolute) confidence.
Factorization progress is best shown on a graph (to get at the raw data e.g. to make a better graph, edit this answer)

This also shows the linear approximation at the beginning of this answer, which actually is a conjecture at even odds for the [2000-2016] period that I made privately circa 2002 in the context of deciding if the European Digital Tachograph project should be postponed to upgrade its 1024-bit RSA crypto (still widely used today). I committed it publicly in 2004 (in French). Also pictured are the three single events that I know of hostile factorization of an RSA key (other than copycats of these events, or exploitation of flawed key generator):

The Blacknet PGP Key in 1995. Alec Muffett, Paul Leyland, Arjen Lenstra, and Jim Gillogly covertly factored a 384-bit RSA key that was used to PGP-encipher "the BlackNet message" spammed over many Usenet newsgroup. There was no monetary loss.

The French "YesCard" circa 1998. An individual factored the 321-bit key then used (even though it was clearly much too short) in issuer certificates for French debit/credit bank Smart Cards. By proxy of a lawyer, he contacted the card issuing authority, trying to monetize his work. In order to prove his point, he made a handful of counterfeit Smart Cards and actually used them in metro tickets vending machine(s). He was caught and got a 10 months suspended sentence (judgment in French). In 2000 the factorization of the same key was posted (in French) and soon after, counterfeit Smart Cards burgeoned. These worked with any PIN, hence the name YesCard (in French) (other account in English). For a while, they caused some monetary loss in vending machines.

The TI-83 Plus OS Signing Key in 2009. An individual factored the 512-bit key used to sign downloadable firmware in this calculator, easing installation of custom OS, thus making him a hero among enthusiasts of the machine. There was no direct monetary loss, but the manufacturer was apparently less than amused. Following that, many 512-bit keys (including those of other calculators) have been factored.

Note: 512-bit RSA was no longer providing substantial security by 2000-2005. Despite that, reportedly, certificates with this key size were issued until 2011 by official Certification Authorities and used to sign malware, possibly by means of a hostile factorization.

According to Schneier's book Cryptography Engineering, n = pq

...should be around 6800 bits...

in order to

design a system that will be used for 30 years, and the data must be
kept secure for 20 years after it has first been processed.

also it states that it's not as same as symmetric keys in

...variable-sized...public key only needs to protect data 21 years,
rather than the 50 years needed for symmetric keys. Each year, you
generate a new public key, and you can choose larger public keys as
computing technology progresses.

but it was also stated that key size almost never matter, as the other parts of the system is more often than not, are weaker.


How do I create a secure encryption scheme using addition? You have a 4 number long PIN code with each number ranging from 0 to 9 which you wish to encrypt. You are then given a random 4 digit number ranging from 0 to 9999, which when added to the original PIN should give out a perfectly secure encrypted number.

Now clearly, just adding the two numbers would give an uneven distribution (a Gaussian curve), as if for example the PIN was 0000 and the random number was 0001, you can rest assured that the original PIN is either 0000 or 0001, while if both integers add up to 9999, there are 19998 possible outcomes.

So my initial thought was that applying the mod of 10000 (because there are 10000 possible combinations) to the sum should ensue an even distribution, making this encryption scheme perfectly secure. Now I honestly really don't know how to prove this, but my main question is how can you convert this somewhat meaningless number back to the original PIN? Is this actually (maybe not effective) perfectly secure? The point of this exercise is that the two users only have common knowledge of the random number, so I don't think any modulus exponent tricks are accessible.

Your idea of addition modulo 10000 is correct.  The correctness follows from the fact that $\mathbb{Z}_{10000} = \{0, 1, \dots, 9999\}$ equipped with addition modulo $10000$ forms a (finite) group.

Let $m \in \mathbb{Z}_{10000}$ denotes a PIN code.  Now choose a uniformly random element $r \in \mathbb{Z}_{10000}$ and define $c = m + r \bmod 10000$.  It is easily seen that $c$ is a uniformly random element in $\mathbb{Z}_{10000}$.

Expand the key using a pseudo random generator and then add each digit mod 10 together, similar to Vigenère cipher and OTP.


Creating a small number from a random octet string I'm trying to figure out the best way to generate a cryptographically secure random number between 0 and 200 (inclusive) from a cryptographically secure random string of bytes (ie. read from /dev/urandom or some such).

I could do random[0] % 201 but then numbers 0-54 would be more likely than 55-200 which would make the resulting number more predictable than it should be.

How can I use the random octet string to create a number in a range 0...k-1 (where k is 201)?

The method given in this other answer is correct: to choose a uniformly random integer in range $[0,k-1]$ given a string of uniformly random integers in range $[0,n-1]$ with $1<k≤n$, get one integer $x$ from the string until $x<⌊n/k⌋⋅k$, then output $y=x\bmod k$. If we have $k≤n<2k$ (as in the question where $k=201$, $n=256$), that simplifies to: get one integer $x$ from the string until $x<k$, then output $x$.

However, that's not the best method, as asked: it consumes more from the input string than strictly needed. Otherwise said, when the input string is of limited length, odds that the algorithm fails are higher than needed. If there are $m$ values in the input string, odds of failure are $(1-⌊n/k⌋⋅k/n)^m$. For $k=201$, $n=256$, $m=3$, that's nearly $1\%$. It can get much worse: for $k=129$, $n=256$, $m=3$, odds of failure are over $12\%$.

We can modify the algorithm to improve on that; and also remove the $k≤n$ requirement.

Set $r←0$, $s←1$.
Get one new $x$ from the random string, set $r←r⋅n+x$ and $s←s⋅n$.
If $r≥⌊s/k⌋⋅k$, set $r←r-⌊s/k⌋\cdot k$ and $s←s-⌊s/k⌋⋅k$, and proceed to step 2.
Output $y=r\bmod k$, and stop.

Sketch of proof of correctness: by induction, before step 2 and before step 3, $r$ is a uniformly random integer with $0≤r<s$.

The integers $r$ and $s$ never exceed $(k-1)⋅n$, and thus the algorithm does not require arbitrary-precision arithmetic. It minimize odds of failure for a given input string of length $m$, to the bare minimum possible for exactly uniform output: $(n^m\bmod k)/n^m$; that is $≈0.0009\%$ (rather than $≈1\%$) for $k=201$, $n=256$, $m=3$; or $≈0.0007\%$ (rather than $≈12\%$) for $k=129$, $n=256$, $m=3$.

The algorithm works if the input string contains bits, or dice rolls with any number of faces, including variable (just change $n$ at step 2 according to the $x$ extracted from the input string).

If we need to generate more than one output $y$, there are several options:

The easiest is to start over; but that's clearly sub-optimal, especially when $n≫k$.
We can change "stop" at step 4 to: "set $r←⌊r/k⌋$, set $s←⌊s/k⌋$ (then, if desired, change $k$ for the next output); and proceed to step 3". The resulting algorithm still produce uniformly distributed output (the recurrence in the proof sketch holds), drastically reduce the consumption from the input string when $n≫k$, but I'm uncertain about optimality is not optimal (that's blatant for $k=2$, $n=3$).
If we know the number $j$ of desired outputs $y$ in advance, we can set $\hat k=k^j$, generate one $\hat y$ uniform in $[0,\hat k-1]$ using the optimal algorithm, then split $\hat y$ into $j$ outputs by expressing $\hat y$ as a $j$-digit number in base $k$. That's back to optimal, but is not a sequential algorithm, and requires arbitrary precision arithmetic when $j$ grows, with $O(j)$ extra memory.
We can generate any number of outputs using several batches of $j$ as in the previous tweak, but using the suboptimal sequential algorithm described above. That allows using bounded extra memory, and becomes close to optimality as $\hat k=k^j$ grows. However this is not a sequential algorithm.

I now lean towards belief that any optimum algorithm is bound to require $O(\log m)$ extra memory in some worst case. However it is possible to make a sequential algorithm using bounded extra memory, much less than above, and closer to optimality. I plan to detail such an algorithm (if someone else finds a reference, or otherwise has a suitable algorithm, please tell us!).

Try to use bitmasks. For example - M is your desired high limit, so use r ?< M/n as a bit mask constructing your number. And after all XOR it with one extra number from RNG.


What are the fundamental roots of modern symmetric encryption? In academic pursuits, we often have people (and their ideas) who are considered fundamental to the subject, such as Bayes and probability.
In cryptography, it's obvious to see that the Diffie-Hellman problem is fundamental to modern key exchange algorithms.
Can modern day symmetric encryption methods be similarly traced back to particular fundamental roots or building-blocks? If so, what are they?
Is there a common grandparent (or few) that most modern symmetric crypto such as AES or ChaCha can be undeniability related to?

There are a few here.

Block ciphers like DES and its modes are based of Feistel Cipher, AES is based on Rijndael.

Others like FOX64 based on Lai-Massey scheme.

Other are are stream ciphers like RC4.

So, These are some of the schemes which are used in todays symmetric key ciphers.


How long would it take all of the supercomputers or cloud computing on Earth to bruteforce a significantly long password? I was arguing with a colleague who thinks that SHA256 (password + 64 character static salt) is "insecure." My argument is that nothing in cryptography is "secure," it's all a sliding scale, and the amount of time it would take to bruteforce such a combination would be so long (I'm thinking over 30 years) that for all intents and purposes it is "secure." His argument is that because SHA256 hashes are so quick to generate, you can crack something like this using all of the computers on Earth quite easily, and as such, it's "insecure."
I agree that using something like Bcrypt is "more secure," but I wouldn't consider the above "insecure" because of the difficulty in cracking such a thing.  If we factor in Moore's law, which argument is correct? And how about if we change that 64-character salt to a
128-character salt?
I feel like this is an argument about semantics, but it annoys me that someone can have such a black-and-white perspective that "this is insecure (SHA256 pass + insanely long salt), but this is secure (Bcrypt)". I understand that something like Bcrypt is obviously preferred and "more secure," and I could see the argument that the other approach is "less secure," but to say one is "secure" and the other is "insecure" is to me a fallacy.

A salt is supposed to be publicly available, for instance it needs to be stored in a DB next to the password hash. In that case the time it takes to recover the password is just a brute force or dictionary for the password. If the salt is static then rainbow tables may be used as well for any attack. Now if the password has an entropy of 256 bits then this is obviously not a problem. Actual passwords however only have about 42 bits of entropy on average, and this is why bcrypt is often needed to provide some additional security.
It is of course also possible to use a 256 bit pepper, which is a salt value that is kept secret. In that case "cracking" the hash will require both the password and the pepper. We cannot do that even with quantum computers because the energy requirements would be too high (cracking > 128 bit security against classical computers or > 256 bit against quantum computers is completely infeasible and forever will be).

I was having an argument with a colleague, who thinks that SHA256(password + 64 character long static salt) is "insecure". My argument is that nothing in cryptography is "secure..."

But isn't that 100% true?  There is no proof that SHAx is information theoretically secure, just as there is no proof that AES hasn't been broken by state actors. Or their code implementations. Just because low paid academics can't invert these primitives, doesn't mean by any stretch of the imagination  that they haven't been by professional intelligence operatives working for decades within an annual  ~$B80  budget.
I suppose that the real issue here is that no modern code breaking requires brute force. We just skirt the algorithm and crib/invert it through mathematics like differential do-da and re-linearisation that's not published for 25 years due to NOBUS policy. See Zerodium. So a good question but cryptographically moot because thinking goes: they don't need to.
It's just that the answer is not what most here expect.

You're going to laugh at this answer, but before you draw breath please read the NOBUS link and what President Obama said about it.

This answer excludes direct action against the cryptographer which results in code break within days.


What does it mean for a random number generator to be cryptographically secure? I've never heard a good answer. I'd like to hear details about:

What are the criteria that make an RNG cryptographically secure?
Why must your RNG be cryptographically secure? I.e., what are the consequences if it is not?
Examples of secure and insecure RNG's
Would a non-pseudorandom generator be cryptographically secure? E.g. one based on radioactive decay of a particle.

What are the criteria that make an RNG cryptographically secure?

In short, a DRBG [deterministic random bit generator] is formally considered computationally secure if a computationally-limited attacker has no advantage in distinguishing it from a truly random source.

What does this mean? Given a DRBG F and a truly random oracle G, let A be a probabilistic "attacker" that accepts F or G and outputs 1 or 0 after making queries to the function it was given. We define the attacker's advantage Adv to be |Pr[A(F)=1] - Pr[A(G)=1]|. If Adv is non-negligibly more than zero, the DRBG is considered broken. In this definition, note that it doesn't matter what returning 1 or 0 "means", just that we care only if A has a different probability of returning one or the other when given F and G.

In English, if there exists a computable function that can reliably tell the difference between a black-box DRBG and a black-box truly random function, then we consider it a break of the DRBG.

  Why must your RNG be cryptographically secure? I.e., what are the consequences if it is not?

This is probably far too broad a scope for a question like this. In some cases it doesn't have to be. In some cases even a slight weakness can cause a near-total loss of confidentiality or authenticity. The implications of a weak RNG are completely dependent upon the system and context in which it is used.

  Examples of secure and insecure RNG's

There are multiple kinds of DRBGs, intended for different purposes.

Yarrow and, later, Fortuna are algorithms that accept as input entropy sources of unknown quality, mix them, and produce entropy streams with strong guarantees as output. They have self-healing properties that resist injection attacks; even if an attacker controls almost all of the inputs, after a finite amount of time, the outputs will become indistinguishable to the attacker.

This is an extremely useful property for system RNGs such as those used by operating system kernels and provided to userspace through /dev/urandom, getentropy(2), and CryptGenRandom() (note: these interfaces may or may not actually use Yarrow or Fortuna, they are just examples of the types of system RNGs those algorithms were designed for).

Stream ciphers like ChaCha20 or block ciphers in streaming modes like CTR are really just cryptographically-seeded DRBGs. These algorithms aren't designed or intended to defend against an attacker injecting predictable inputs as the aforementioned algorithms were, but they produce nearly-infinite streams of randomness at very high speed given only a small initial random key and IV. These streams can then be XORed against a plaintext to produce a cryptographically-strong ciphertext. Even better, these algorithms are typically seekable; given a key, IV, and long ciphertext, you can generally seek far into the ciphertext and decrypt individual bits without needing to compute the entire stream.

I won't list insecure DRBGs here. There are simply too many to list, and the general assumption should be that a DRBG is not secure unless demonstrated otherwise.

  Would a non-psuedorandom generator be cryptographically secure? E.g. one based on radioactive decay of a particle

Non-pseudorandom generators are the only generators that are even capable of being information-theoretically secure, which is a significantly stronger metric than computational security. With a computationally-secure DRBG, a small seed of n bits is expanded into a larger cryptographic stream; that larger stream still is only one selection of at most 2^n possible streams.

Quantum sources of randomness such as radioactive decay and thermal noise are by physical definition truly random.

Why must your RNG be cryptographically secure? I.e., what are the consequences if it is not?

Because there's only one unbreakable cipher method — one time pad. If RNG fails to mask clear text as good as one time pad would have done, the result is more and more vulnerable to crypto analysis.


How does Fialka manage to have a letter encipher unto itself? http://www.cryptomuseum.com/crypto/fialka/index.htm

Fialka was an electromechanical rotor machine.

How does it manage to have a letter encipher unto itself. I realize it does something clever by using transistors, but it has a reflector. With direct current circuits, there has to be a negative and a positive connector. If one simply attached a positive current to itself, it wouldn't flow. So how does it work?

The reflector wheel on the Fialka incorporates a transistor switching circuit connecting pins 16, 18 and 24. In coding mode, a signal on pin 16 is connected via pin 18, a signal on pin 18 is connected to pin 24, and a signal on pin 24 is connected to pin 16.  In decoding mode, these paths are reversed.  This allows the Fialka to encode any letter as itself, overcoming one of the major weaknesses of the Enigma machine.


Passing data securely through QR codes? We have to implement a way to securely transfer data from a POS to a mobile app using QR codes.

The mobile app gets the payment parameters (amount, description, purchase_id, store_id) to create the payment intent by scanning a QR code generated from the POS,
the app passes the info to a trusted server through an API and
if the payment succeeds, it generates a QR code for the POS, including some parameters the store needs to match the payment back in the POS system.

We need to make sure that the system is secure so is not possible for an attacker to fake these QR codes.

Would this ensure the system security?

The trusted server generates a key pair and a shared secret
The commerce (POS) generates a key pair
The trusted server and the POS exchange their public keys and the shared secret
The QR code contains 2 parts: an encrypted body + signature
The encrypted body is a JSON string encrypted using the server’s / POS’s public key. The only way to decipher the body is using the private key so the structure of the message remains unknown.
The signature is a HMAC-SHA256(body, shared-key). So we can verify the integrity of the body once decrypted in the server or POS.

Does this make sense?

If the POS system is online, then its simple. Just have a purchase ID in the QR.
The POS will call your API, and "create" an unpaid purchase.
This purchase ID is encoded into an QR.

Then the customer scans this QR, and approves payment. You don't even need to display a returning QR, because the POS could poll the API at regular intervals and check when the ID is "paid".

If you want to be able to have an offline POS, its also pretty easy. You need a shared key, that is unique per physical store location (store_id must also be unique per store location, store_id is then used by the payment server to look up the correct HMAC key).

If a store accidentially leaks their shared key, they must replace it immediately, else they risk customers creating fake QR codes to get products for free.

The store have a QR code with:
amount + "-" + description + "-" + purchase_id + "-" + store_id + hmac_sha256(amount + "-" + description + "-" + purchase_id + "-" + store_id + "-unpaid-", SHARED_KEY)

You send this to server. Server validates the hmac, and then, upon payment, creates the following QR:
hmac_sha256(amount + "-" + description + "-" + purchase_id + "-" + store_id + "-paid-", SHARED_KEY)

Assuming a shared hmac_sha256 key of: SHAREDKESHAREDKESHAREDKESHAREDKE

First you create the purchase:
100-USB memory-0001-1212-475d1fa90f24e134e76ffcc075ad3e7ce2c76e1ae78c7c8408c7508882ee9952
(89 characters)

Then app sends this for payment.
When payment is done, you create the following QR:
0899dd28bb8e5cfe6d54deb0000df01cec88f65b85a0b4148d7b49dddd2453d9
(64 characters)

NOTE: The original purchase data is NOT needed in the "reply QR" - the cash register already have this data from the pending transaction, that it can use to check the reply QR. So the "reply QR" becomes much smaller and more easier to scan.

NOTE2: Even if someone learns the structure, its still a impossibility to create a valid reply HMAC from the request HMAC. Changing "-unpaid-" into "-paid-" would require knowledge of the shared key.

NOTE3: purchase_id must be unique among a single physical store location (store_id). If a store is generating duplicate purchase_id's, a customer can reuse a paid order to get products for free. If a store location has multiple offline POS not even connected with each other, the store, which also chooses purchase_id, must prepent the POS location to purchase_id, eg have purchase_id 10000-19999 for POS 1, 20000-29999 for POS 2, and so on. In my solution, purchase_id can be of any length required for the purchase_id not to roll over.

You really don't need to mix in RSA at all.

Actually, you don't need an HMAC for the request at all (but its ALWAYS required for the Response). Its just a customer protection so any scan errors or any sheninigans doesn't cause a customer to do a payment for a non-existing purchase.
The reason is that the request isn't security-sensitive, is because if the customer edits the purchase request, the response QR for the paid purchase will not validate, and the hacking customer will not get anything out of it.

But you must atleast have some error protection so not a damaged QR display or strong light falling on QR-code or the phone camera causes it to generate a purchase request, which when paid for, will not release any products, and thus cause a legit, fair customer to lose money. Thats extremely unlikely however, as QR code contains their own checksums, but feel free to add any checksum you like to the request. It can be HMAC, a md5 hash, a CRC32, whatever. Even a truncated hash suffices, if you must keep the request size down to not cause too large (and unscannable) QR codes.

The customer editing a purchase request to for example try to get products cheaper, and then getting a invalid response QR back, would be equvalient of a customer taking a 20 dollar bill, and trying to make a 100 dollar bill out of it, failing the fraud attempt, and thus losing the 20 dollar bill. So basically, any protection on the request is only for customer protection against themselves, which you can skip if your situation does not require it.


Statistical Tests for Pseudorandom Functions Say I have an implementation of a potential Pseudo-Random function and I want to test whether my implementation does at least not contain any obvious flaws. As far as I understand, in other cryptographic settings, statistical tests are employed to ensure the correctness of the encryption algorithm.
What kind of statistical tests could I use for Pseudo-Random functions?

Nobody uses generic statistical tests to verify correctness of encryption algorithms.

To verify correctness of an implementation, engineers write proofs of correctness for their code, tr running it on known-answer tests, confirm round-trips on randomized inputs, etc.

None of this involves statistical tests, since the point is to implement a specific mathematical function, not to sample stochastically from a distribution—indeed, if you did use generic statistical tests you'd have to decide what to do in the case of false alarms, which would be an absurd way to approach verification of software implementing deterministic mathematical functions.
To assess security of a cryptosystem, cryptographers study specialized statistical tests.

Assuming, following the advice of Kerckhoffs, that the adversary knows the system, what's the best they can do to attack it with that knowledge?  Generic statistical tests like $\chi^2$ tests are stupid because they don't even know the system.  For example, here's a test for distinguishing a 256-bit AES-CTR stream under a uniform random key from a uniform random 256-bit string:

Guess a key $k$ uniformly at random.
Check whether the string $s = s_1 \mathbin\| s_2$ is of the form $\operatorname{AES}_k(0) \mathbin\| \operatorname{AES}_k(1)$.  If it is, guess AES-CTR; if it isn't, guess uniform random.

This test has distinguishing advantage $2^{-256}$ (or $2^{-128}$ if you use AES-128 instead of AES-256, which I don't recommend[1]), so the best distinguishing advantage for AES can't be worse than $2^{-256}$, but a lot of smart cryptanalysts haven't found a way to do any better than that.  Obviously, you could spend more computation—try it twice, with two different keys $k_1$ and $k_2$—to raise the advantage linearly, so this number should be qualified with a cost factor.

Any putative pseudorandom function family should come either with the paper droppings of a horde of cryptanalysts demonstrating failure to find a better-than-generic distinguisher, or with a proof of a theorem relating the security of the PRF to the security of some underlying primitive.  For example, the best PRF-advantage attainable against AES by any distinguisher making $q$ queries is bounded by the best PRP-advantage attainable against AES, which cryptanalysts have studied for decades now, plus $q(q - 1)/2^{129}$ because AES is always a permutation.

So, put your generic statistical tests in the garbage.  Find the literature on the putative PRF.  Write a proof of correctness of your code.

You're right.  A random stream should be identical to a well encrypted stream  .  To test it you can pass a plain counter through it, as $F(counter)$. The output should be pseudo random. Therefore the first port of call for all RNGs should be ent.  There are few 'simple' design errors that can fool an ent test. You can test up to 2GB of data, and a typical pass result is:-

Entropy = 8.000000 bits per byte.

Optimum compression would reduce the size
of this 1073741824 byte file by 0 percent.

Chi square distribution for 1073741824 samples is 271.72, and randomly
would exceed this value 22.54 percent of the times.

Arithmetic mean value of data bytes is 127.5000 (127.5 = random).
Monte Carlo value for Pi is 3.141575564 (error 0.00 percent).
Serial correlation coefficient is -0.000034 (totally uncorrelated = 0.0).

Just be aware that you need at least 500kB of data for the result to be meaningful.  This example is 1GB from /dev/urandom. An alternative at this point in your function's evolution is the FIPS 140-2 RNG test as part of the Rng-tools suite.  It tests them in blocks of 20kb. Chances are that you'll know about $F$ at this stage.

After that, you can advance to more comprehensive tests like TestU01, Diehard(er), NIST SP 800-22, etc.  Just be aware of the required sample sizes, as some of the tests can be really greedy with Dieharder a case in point. It's worth noting that you should expect some tests to fail. Do not despair, as that's as it should be as randomness is pesky.

You might also want to look at the avalanche effect and it's calculation.  It's simple (based around xored random numbers) and if $F$ is working, you'll get a normal graph centred on 50% like:-

with (in bits) $ \sigma =  \frac{\sqrt{block width}}{2} $. As my esteemed friend points out, statistical testing doesn't address all major security aspects of $F$. However it addresses some, and it does form a very good check on the   mechanics of your algorithm.