Is this a good Pseudo-Random Number Generator? I discovered what appears to be a good quality pseudorandom number generator, but I have not subjected it to any statistical tests beyond bit frequency, bit pair frequency, and least-significant bit frequency tests. It generates a block of bytes by evolving deterministically, starting with a seed state. I'm new to Stack Exchange, so please bear with me.
Here is the process (test example):
start with a 32-byte sequence (256 bits) and an integer variable k, and for each byte X(i),

$s = 7 - (X[i+1]+X[i+2]) \bmod 15$
$X[i] = ((X[i] + k) * 2^s) \bmod 255$
$k = k + X(i)$

and I implemented this process in C as follows:
    #define CYCLES 1 // full cycles per byte of the seed size per evolution
    unsigned int i, j;
    unsigned char a, k;
    int s;
    for (i = 0; i < 32*CYCLES; i++) {
        a = X[i%32]+k;
        s = 7-(X[(i+1)%32]+X[(i+2)%32])%15;
        for (j = 0; j < abs(s); j++) {
            if (s<0) {
                a = ((a&1)==1)?((a>>1)+128):(a>>1);
            }
            else {
                a = ((a&128)==128)?((a<<1)+1):(a<<1);
            }
        }
        X[i%32] = a;
        k += a;
    }

The C implementation of modular multiplication by powers of uses bitwise operations and differs in only one way from an algebraic method: when a = 255, the output is always 255. This is essentially a rotation of the byte abs(s) times to the left when the sign is positive, and the right when it is negative.
If I initialize the array X with a seed value such as "ABCDEFGHIJKLMNOPQRSTUVWXYZ012345" and evolve it 32 times, then map out the resulting bits or do basic tests for randomness, it appears to be very similar to true randomness. Am I missing something, or is this a good PRN generator?

What could possibly be an advantage of your method from directly sampling the bytes from the prime number distribution?
Like:
Start at some integer $k$ and sample the 8 bits as: $k*30+\lbrace -13,-11,-7,-1,1,7,11,13\rbrace$, each time when it is a prime number, you set the bit at that position to 1, otherwise to 0. If your sampled Byte is $<= 64$ use k-= Byte, otherwise use k+= Byte for the next sample.
Isn't this much simpler than your method, or am I missing something of importance?


Key generation on rebalanced RSA-CRT Key Generation Method: Take $s \le n/2$ bits.

Generate two distinct random $n / 2$-bit prime numbers $p$ and $q$ with $\operatorname{gcd}(p-1, q-1)=2$ and
calculate $N= p*q$;
Generate two $s$-bits random numbers $d_p$ and $d_q$,
such that $\gcd(d_p, p-1)=1$, $\gcd(d_q, q-1)=1$
and $d_p= d_q \bmod p-1$.
Calculate one $d$ such that $d= d_p \bmod p-1$ and $d= d_q
\bmod q-1$.
Calculate $e=d^{-1} \bmod \varphi(N)$,
Public key= $(N, e)$,
Private key= $(p, q, d_p, d_q)$.

On the 3rd step of key generation, do I need to select between $d= d_p \bmod p-1$ and $d= d_q \bmod q-1$ or do I make the $d_p$ and $d_q$ to make same $d$ result?

It is okay to use small prime because I use $p = 41$ and $q = 59$ for study purposes.

Please help me to find the $d$.

The paper on which the question is based describes Rebalanced RSA-CRT with $d_p=d_q\bmod(p-1)$ as stated in the question's step 2, but is wrong in doing so. Notice that when $s<n/2$, that condition implies $d_p=d_q$, and that goes squarely against generate two $s$-bits random numbers $d_p$ and $d_q$ also in step 2 (further step 3 can become $d=d_p$, ans $d$ is $s$-bit only).

That's confirmed by looking at the paper's source: M. J. Wiener's Cryptanalysis of RSA with short secret exponents (IEEE ToIT, 1990), which section 8 open problems states [emphasis added]:

  A useful technique for reducing the secret key exponentiation time is
  to take advantage of the knowledge of $p$ and $q$ (rather than just the product $pq$). Using this technique, two half-sized exponentiations are performed. The first exponentiation gives the result modulo $p$ using exponent $d_p=d\bmod(p-1)$, and the second gives the result modulo $q$ using exponent $d_q=d\bmod(q-1)$. These two results can be combined easily using the Chinese Remainder Theorem to obtain the final result modulo $pq$. One could reduce the secret key exponentiation time further by choosing $d$ so that $d_p$ and $d_q$ are short. An interesting open problem is whether there is an attack on RSA when $d_p$ and $d_q$ are short, but not equal.

Wiener clearly knew that short $d_p=d_q$ would be unsafe (his paper conclusively proves it when $s\le 0.125n$).

I thus suggest that the key generation procedure for Rebalanced RSA-CRT should be:

Generate two random $n/2$-bit primes $p$ and $q$ (that are nearly certainly distinct for sensible choice of $n$), optionally such that $\gcd(p-1,q-1)=2$ ;
calculate $N=p\cdot q$ (which will be $n$-bit or one bit less).
Generate two $s$-bits random integers $d_p$ and $d_q$ (that are nearly certainly distinct for sensible choice of $s$), such that $\gcd(d_p, p-1)=1$ and $\gcd(d_q, q-1)=1$.
Calculate (using the CRT) one $e$ (possibly: the lowest) such that $e\equiv d_p^{-1}\pmod{p-1}$, $e\equiv d_q^{-1}\pmod{q-1}$, and $0<e<(p-1)(q-1)$.
[or we could explicitly compute $d$ then deduce $e$ as in the question]
Public key = $(N,e)$,
Private key = $(p,q,d_p,d_q)$.

but I caution against using it:

We know that it would be insecure to use $s<0.146n$, thanks to D. Boneh and G. Durfee's Cryptanalysis of RSA with private key $d$ less than $N^{0.292}$ (first version in proceedings of Eurocrypt 1999)
These authors caution the bound could further be improved to $d<N^{0.5}$, thus $s<0.25n$; so we should probably stick to prudently larger $s$, and a conservative Rebalanced RSA-CRT is thus bound to a speed improvement smaller than a factor of two.
Further, when using RSA-CRT (rebalanced or not) to compute $x\to x^d\bmod N=y$ , it is customary and useful to check that $y^e\bmod N=x$ in order to guard against fault injection; in which case having a large $e$ (as in Rebalanced RSA-CRT) much more than offsets any speed gain achievable by lowering $d_p$ and $d_q$.

Example with $n=40$, $s=13$ (which are too small to be sensible choices)

$p=768941$, $q=825443$, $N=634716965863$
$d_p=4231$, $d_q=6779$
$d_p^{-1}\bmod(p-1)=634271$, $d_q^{-1}\bmod(q-1)=670801$
$e=303057573891$.

For RSA key generation, one usually first selects $e$ and generates primes $p$ and $q$ such that $\gcd(e,p-1)=\gcd(e,q-1) = 1$.  The advantage of doing so is that one can use a small value for $e$.  Common values for $e$ are $e = 3$, $e = 17$, or $e = 2^{16}+1$.

If you insist to first generate the decryption key then, upon generation of primes $p$ and $q$, you need to choose a random $n$-bit integer $d$ such that $\gcd(d, p-1) = \gcd(d,q-1) = 1$.  Next, define $d_p := d \bmod (p-1)$ and $d_q := d \bmod (q-1)$.


Acceptable assumptions when proving security Considering the output of a cryptographic primitive, like an encryption scheme (CBC, ...), a hash function or even the output of any schemes based on number theoretic assumptions, is it reasonable (acceptable) to assume that these outputs are random when proving the security of a protocol/algorithm which relies on the use of such a primitive? Is this a good starting point?

The answer is "it depends". There are two fairly commonly used sets of assumptions, the so-called standard model, and the random oracle model. In the standard model, hash functions are one-way functions. In the random oracle model they are random oracles. The random oracle model isn't actually true, but it is useful and many protocols inspired by it are in fact secure as no one has been known to attack them.

For ciphers the usual model is PRP, pseudo-random permutation, although the ideal cipher model is also used, but generally PRP is realistic and strong enough to prove things secure.

Number theoretic primitives do not output random strings. For instance DH never produces all zeros. You should use hashing to make this truer.

For protocols usually a game is designed where an adversary tries to get bad things to happen. Showing that the game is lost if the cipher is a PRP implies that a real version will be secure if the cipher behaves like a PRP, and so is generally considered a proof of security. However, the constants involved matter: if you haven't read DJB "Non-uniform cracks in the concrete" you should before embarking on any sort of provable security work.

The answer I normally see is the protocol's documentation will reference the strength of the underlying algorithm. You don't have to assume it's perfect, just adequate.


Brute forcing an elliptic curve encrypted key I've been reading about ECC, and what I've established so far (correct me if I'm wrong) is that:

pubKey = privKey * G

where G is some special point on the secp256k1 curve.

Doesn't this mean we could attempt to brute force a private key by using:

privKey = pubKey/G

for all potential values of G.

I know it would require some unfeasible amount of attempts, but what if by chance that one of the first few attempts happened to have the correct value?

Doesn't this mean we could attempt to brute force a private key by using:
  $$\mathit{privKey} = \mathit{pubKey}/G$$
  for all potential values of $G$?

There seems to be a misunderstanding here: $\mathit{pubKey}$ and $G$ are fixed and publicly known, so there's nothing left to brute-force. The operation of "dividing" $\mathit{pubKey}$ by $G$ is (to the best of current public knowledge) computationally infeasible; this is the elliptic-curve discrete logarithm problem (ECDLP).
However, of course, one can brute-force by trying all possible values of $\mathit{privKey}$ and checking whether $\mathit{privKey}\cdot G=\mathit{pubKey}$ holds.

  what if by chance that one of the first few attempts happened to have the correct value?

This is very much related to this recent question. The bottom line is: Yes, that could happen, but the probability is so incredibly low it is never going to occur in practice. (And in any case, if we're worried about someone just guessing our secret keys by pure luck, there's nothing anyone could do against it anyway.)

primitive methods defined here
curve domain parameters available here
check whether public_key_xy = scalar_mult(private_key,curve.g) matches expected target


Is there a string that's hash is equal to itself? I was wondering if there's any string that has a hash equal to itself, so that – when using any (none specific) hash function – the hash would be equal to that string?

so that:

hash(x) = x

Note that this is not an assignment or anything. I’m just curious and couldn't find any specific answer or reference. And I’m not sure how to go and prove/disprove that to myself!

I restrict to hash functions $H$ with an output of some fixed size $n\ge1$ bit(s), accepting as input some strings, including all $n$-bit strings; MD5 (resp. SHA-1, SHA-256) is an example of such function for $n=128$ (resp. $n=160$, $n=256$).
Whether there exists a solution to $H(x)=x$ depends on the particular hash function. If $H$ is a random function (as MD5, SHA-1, and SHA-256 aim to be), the answer is YES with odds next to $63.2\%$ for practical values of $n$.
More precisely: $H(x)=x$ can hold only if $x$ has exactly $n$ bits. There are $2^n$ values of $x$ that satisfy the later condition, and restricting $H$ to such $x$ there are $(2^n)^{(2^n)}$ different $H$ functions, of which $(2^n-1)^{(2^n)}$ such that $H(x)=x$ has no solution. Therefore, if we choose one $H$ uniformly randomly, odds are exactly $1-{(2^n-1)^{(2^n)}\over(2^n)^{(2^n)}}=1-(1-2^{-n})^{(2^n)}$ that we picked $H$ such that $H(x)=x$ has a solution. As $n$ increases, this converges very fast to $1-1/e\approx0.632$ (where $e\approx2.718$ is the base of the natural logarithm).
This does not tell if MD5 has the property that there exists a solution to $\operatorname{MD5}(x)=x$ (which would be a 128-bit bitstring $x$). The best we can say is that it likely holds, with odds about to 63%, but determining if the assertion is true or false is beyond our current computing power (the best method we have is exhaustive search, and if the answer is no it would require $2^{128}$ hashes; otherwise it is still likely to require over $2^{126}$ hashes, which is beyond reach).
PHP specific: if md5($string) === $string had some solution, that would be a 32-character string of hexadecimal lowercase characters; we are not hashing the same $2^{128}$ candidates as above so the question is not equivalent, but the reasoning can be adapted, and again the best we can say is that it is likely there's a solution, with odds about 63%.
Further, the original question asked if there is a string such that md5($string) == $string. To answer this, we must take into account how the == operator works in PHP due to type juggling (it holds that "0042" == "42", and "20e2" == "   +002000"). It is overwhelmingly likely that there is a solution (just consider that among the $2^{200}$ strings consisting of 200 space or tab and an additional final 0, we expect about $31\cdot2^{72}$ hash to one of "00000000000000000000000000000000", "000000000000000000000000000000e0" .. "0e000000000000000000000000000000"); however we can't exhibit one.

It is easy to define a hash function $H$ such that $H(x)=x$ has no solution: for example, define
$$H(x)=\begin{cases}x\oplus1&\text{if }\operatorname{MD5}(x)=x\\\operatorname{MD5}(x)&\text{otherwise}\end{cases}$$

It is also easy to define a hash function $H$ such that $H(x)=x$ has at least one solution: for example, choose some arbitrary 128-bit constant like $k=\text{af5d2bc6c9181f76f3161f43f41f6aeb}$, and define
$$H(x)=\begin{cases}k&\text{if }x=k\\\operatorname{MD5}(x)&\text{otherwise}\end{cases}$$

There can be no $x$ such that for all possible hash functions $H$, $H(x)=x$.
Proof by contraposition: assume there is such $x$, a function $H$ with $x$ having that property, and consider the function $\tilde H$ defined by $\tilde H(x)=H(x)\oplus1$.

With any hash function as you ask:

No.

If you write a Hash-function wich calculates the Hash-value in some way, and then append a t to the result (because you like the letter), then no matter what your input string is, the hash result will be different from your input.

For specific hash functions:

Sure, it could be; especially with a "bad" hash-function like "first 3 letters of the String".

Since a clarification (see comment) pointed out that the question only targets mature hash functions, please refer to user2351586's answer for MD5 specifics.


What is the threat to a PKI when the root CA certificate is generated using SHA1? We have thousands of servers that have been issued certificates signed by our CA using SHA256 but the our root CAs own certificate was generated using SHA1. Assuming SHA1 is no longer secure for our purposes what exactly is the threat to our infrastructure if our root CA certificate was signed using SHA1?

None.

You don't trust the Root CA certificate because it was signed by anything - you trust the Root CA because you (or someone on your behalf) placed it in your trust anchor store.

A Root CA certificate has a signature simply because it is mandatory within the X509 specification - it serves no other purpose.

Technically, the trust anchor doesn't have to be a certificate, but most (all?) operating systems have taken the decision to use the X509 certificate format to store the trust anchor - there are others defined (RFC 5914) that don't have a signature, but as far as I'm aware, they are not used.

SHA1 deprecation has been in the limelight lately.  If your subordinate CA certificates or your end-entity certificates are signed by SHA1, browsers will complain.  However, if you sign your Root CA certificate with MD5 or MD4 (or even something earlier if you can find the tools to do so) then everything will still work.

If you take a look at Google, Facebook, Microsoft (and no doubt many more) you'll find that they still have SHA-1 signed Root CA certificates.

The signature of a message is applied over its hashed value. If it is computationally hard to generate a collision for a given hash function, it offers the same level of attestation and it generates a constant size digest that is way shorter than most signed documents.

However, if a way to generate collisions is discovered for SHA-1, it would be theoretically possible to generate a rogue certificate that produces the same hash value and, as a result, is verified by the same signature.

As a practical remark, I would expect two kinds of implications: the technical one, where attackers would create rogue certificates to impersonate other entities, and a legal one. If the binding property of a certificate is questioned, the legal binding of any digital signature produced with the certified key can be plausibly denied.


How can I prove/disprove that a construction yields a secure PRG? Let $G:\{0,1\}^{*} \mapsto \{0,1\}^{*}$ be a secure PRG. Prove or disprove that the following construction also yields a secure PRG.
$$G'(k) = G(k||0),$$
where $||$ denotes the concatenation of two strings.

I understand that proving/disproving such constructions usually involves a proof by reduction or a counterexample. Intuitively, I would say that $G'$ is a secure PRG, since we only fix a bit of the input, which should not make the output distinguishable (in polynomial time). However, for some reason I can't finde the right reduction, since I don't see how a $w \in \{0,1\}^{*}$ and a distinguisher $D'$ for $G'$ can be used to construct a distinguisher for $D$ for $G$.

So is $G'$ a secure PRG? If yes, how can I construct a valid reduction and if no, how does a distinguisher for $G'$ work?

I don't know if it is appropriate, but I would prefer hints, which point me in the right direction instead of complete solutions.

If there exists a secure PRG, then there is a secure PRG

whose last bit of output is always equal the last bit of its input.

If the last bit of G's output is always equal to the last bit of G's input, then the

function G' constructed as described in the question will not be a secure PRG.


How confident can we be that nobody will crack a 128-bit key? In a context involving a block cipher like AES-128, excluding quantum computers, cryptanalytic breakthrough on AES and implementation attacks (poor TRNG, DPA..), and wrench, how confident can we be that by key search, "nobody will crack a 128-bit key" until 2100. Assume business as usual for humanity, use of 1 year worth of global production of electricity, 1 year worth of industrial production for the gear (used over a multi-year period).

Full disclosure: I'm trying to challenge my own half-baked opinion.

Updated: I leave it open if we allow multi-target attacks, where the same known plaintext is available enciphered under many random 128-bit keys. That makes a huge difference, but specifics of the block cipher become less important, which is good.

Note: we have a related question there; but it was considering a 256-bit key size, the methods adequate for that size need not be precise, and have not led to a definitive or even clear conclusion on 128-bit; plus answers are nearly 6 years old, and much more SHA-256 have been performed since then than I would have predicted at the time.

Note: We have another related question there at the 128-bit key level, but it restricts to currently available technology. Here, we must account for foreseeable technology more plausible than quantum computers usable for that cryptanalysis.

Note: 2100 and other limits have been set (instead of the original in the future of humanity as a species) for the sake of making a quantitative answer more falsifiable. Say, global apocalypse on that March 1 because a military subcontractor goofed on the leap year rule.

This question seems to be asking us how fast will computers grow. No cryptanalytic breakthrough and no quantum computing essentially means no attack faster than brute force.

So will humanity at some point in the future with significant resources be able to brute force 128 bit key?
I would answer, maybe. 256 bit key Almost definetly not.

Obviously predicting is hard especially the future but assuming humanity will not self destruct it will continue to progress and it is not unreasonable to assume it will come close to the limits of what is possible.

The main discussion on theoretical limits of brute force is in minim energy requirements. I suspect we may be short on physicists on crypto stack exchange so I will try.

Brute forcing a key requires enumerating the keys. And that requires changing bits. Each bit change erases some information and there is a minimal amount of energy required for that. Lauder's limit
https://en.m.wikipedia.org/wiki/Landauer%27s_principle

For brute forcing a 128 bit at room temperature this comes out 262.7 Twh(the annual electricity consumption of Spain) that is a lot But not something humanity can't achieve.  By lowering the temperature we can improve on this. And some say we could build another type of computer which doesn't erase information and this limit won't apply to it. Though such a computer might go against the spirit of the question which excluded quantom computers.

So we don't actually have any good theoretical limits to prevent humanity from brute forcing a 128 bit key eventually. Which leads to my answer. Maybe.

For 256 bits the same energy limit would put brute forcing well outside the realm of the possible.

It is a 99% certainty that any AES key of any size will be cracked, perhaps within our life times.

It is complete nonsense to suggest that we'll have to boil lakes or build Dyson Spheres to recover an AES key. All those  back of fag packet estimates are for brute forcing a key. It is extremely likely that we won't have to. Differential analysis came along and revolutionized cryptography. Technology and science will inevitably advance further and key recovery will become possible.

It is extremely naïve to predict the future with such blind arrogance. Do you remember those doom sayers that prophesied with such certainty that a man's lungs would explode if we travelled above 6 mph? And those German cryptographers who orchestrated the War of the Atlantic confident of total secrecy? Were they wrong!

There is a simple mathematical test to determine whether any encryption can be broken. If (message entropy) > (key entropy), the encryption can be  broken theoretically. The longer the message, the greater the redundancy and the lower the theoretical security. Just because we can't recover an AES key today /tomorrow, doesn't preclude it's recovery next week or next decade. If anyone says otherwise, I suggest that they retire from poorly paid cryptography and either go into the stock market to make a killing or Tarrow card reading.

There is an interesting consequence of the breakability formula. True random number generators are relatively simple to build. When the Up side of our Dyson sphere is at war with the Down side, strategic communications may again revert to using ancient one time pads that obey the breakability equation.


Using RSA encryption with OpenSSL library: secure? I'm working on a small program (in C) that writes encrypted log files, but there are a lot of articles out there that say you should avoid RSA whenever possible. However, most of these articles also seem to refer specifically to home-cooked algorithms involving RSA, because in such cases inexperienced crypto-devs tend to pick insecure parameters.

In my case I'm simply using the OpenSSL library and its RSA_public_encrypt() function, along with OAEP padding. The plaintext is received over the network and never fed directly to the program, any error messages will be reported only to people having local access to the machine it's running on. The private key can be either 2048 or 4096 bits long and will be stored offline and far away from the public key. The key pair is generated outside of the application, but also through OpenSSL:

openssl genpkey -aes-256-cbc -algorithm RSA -out foo.key -pkeyopt rsa_keygen_bits:4096
openssl rsa -pubout -in foo.key -out bar.pub

Is this setup:

Considered cryptographically secure? I know you could still attach a debugger and just read the plaintext strings from memory, but in that case you have bigger problems anyways so it's not really relevant for this question.
Future-proof (i.e. do I need to migrate it over to something else sooner rather than later)?

New systems should not use RSA unless interoperability requires it. See for example this twitter thread for current zeitgeist: https://twitter.com/veorq/status/1148258833896263680

With RSA, the recommendation is to not even have a mode where data is encrypted using RSA directly, even if it fits. Always use hybrid encryption to not have two code paths. The symmetric encryption part should use a modern AEAD, and unless the performance difference between AESGCM (up to 5GB/s) and ChaPoly (up to 2GB/s) is important, use the ChaPoly since a random implementation of ChaPoly is more likely to be secure than a random implementation of AESGCM.

Instead of RSA-OAEP, I would use Curve25519 ECDH in ephemeral-static mode. Meaning you create a Curve25519 keypair, store the private safely offline and copy the public to the system that will encrypt.

Every time it needs to encrypt a file it generates a new Curve25519 keypair, writes the public into the beginning of the encrypted file, does ECDH between the private and the destination's public to get a shared secret, forgets the newly generated Curve25519 keypair, uses KDF over the DH shared secret, and uses the result of the KDF to generate key and nonces for the AEAD. If the cleartext is long, use chunks.

To decrypt, use the private key stored offline to do the ECDH with the ephemeral public, KDF, AEAD.

Oh wait, I'm describing libsodium. Use libsodium. It is the embodiment of 20 years of lessons learned in cryptography and misuse resistant crypto API design, it is production quality, it is portable, it is fast, etc.

If large quantum computers ever happen, both Curve25519 and RSA would be broken. Details about the future quantum computer are not available to judge whether using larger RSA would give you more safety margin (unless you use post quantum RSA, which is a joke).

That should be secure for the time being.  I'd max out the RSA key size if I were you (future proofing) as 2048 will not survive quantum computers (neither will 4096 in the long run, but it gives you more time) AND because the bigger the RSA key size the more data you can encrypt.  Remember that the max data you encrypt with RSA is your key size minus padding/header data so going with 4096 gives you 256 more bytes of data that can be encrypted.  And if you were thinking of encrypting multi MB or GB files with RSA then you should rethink that.  Use hybrid encryption where you generate a random key and encrypt that, along with some other useful information, with RSA.  You encrypt the actual data with the random key you generated.  This is how things like PGP and S/MIME work.


Designing a hash function from first principles rather than depending on heuristics Is there a general method to design a cryptographic hash function (with desired properties) from first principles? That is, is there a general process for constructing such functions? I get the impression that Merkle–Damgård construction simplifies the process by allowing collision-resistant compression functions to be used, but are there any general ways of finding "good" compression functions other than by using trial-and-error?
In the entries to the most recent NIST challenge, it seemed to me as if the teams were using very different approaches based on different heuristics, and then essentially testing their functions against many inputs, tweaking parameters, and after that iterating until all evidence pointed to their functions as being secure.

To what extent is this an accurate summary of their approaches? I would really appreciate a reference to a thesis or other publication on this subject.

You should design your hash on the bit level.

Regardless how you design your hash, at the end of the day you have a $m$ booleans functions for each output bit from an arbitrary $n$ bits of input.

Some properties of boolean functions

All your output bits will be some boolean function of your input bits.

All boolean functions can be turned into the so called algebraic normal form (ANF), which means your input bits are combined using AND and XOR operators only.

XOR operator is just addition modulo 2. AND operation is just multiplication modulo 2. And these operations are usually denoted with multiplication and addition respectively. In modulo 2 arithmetic addition and subtraction are the same operation, so don't be surprised when I use + when talking about differences.

The modulo 2 arithmetic forms a field, which means all your usual algebraic identities you know are true.

So now the operation of your cipher is just a system of $m$ equations for $n$ bits of input.

Due to nature of modulo 2, a lots of things cancel. Powers cancel: $0^n = 0$, $1^n = 1$. Even coefficients cancel: $x + x = 2x = 0$.

This means the equations for the output is simpler: The only possible coefficient is 1 (or 0 which means a missing term). And all of them is on the first power.

Nonlinearity

If you try to make a cryptographic hash function that only uses XOR and shifting, the equations will be linear even after infinitely many rounds, now the analyst is just a single Gauss elimination away from solving it and now they have the ability to create arbitrary preimages.

In order to avoid that, you need to make your equations non-linear by using the AND operator. Hashes do all sorts of shifting and XOR-ing but this non-linear step is what makes them secure.

But having non-linear terms are not enough. You must make sure the attacker cannot effectively cancel out the non-linear terms out of your equations by fixing some inputs to 1 or 0. Also you need to make sure the terms will not cancel if the attackers takes the difference of two equations. If you have the formula $xy + x + y$ for one and another formula $xy + y + z$ for another bit. Adding these two will give $x + z$ which is now linear and allows the attacker to solve it to get the relationship between two out bits.
Every independent linear equation an attacker can create will reduce the security of your hash with 1 bit. One way to mitigate this is making sure all the functions for the output bits contain different terms. In the previous example if we replace the $xy$ to $xz$ to the second formula. Adding together will not yield linear equation then. But if the attacker fixes the $x$ to a constant value then it becomes a linear equation. This is probably the most challenging part of designing your hash.

Balance

Another thing to consider is balance. You want your hash behave like the so called random oracle. This is important if you want your hash useful as a cryptographically secure random number generator for example. You should make sure all your bits in the resulting hash have 50% chance to be 1. The XOR operator have a very good property that makes it possible: in $a + b$, if either term have 50% chance to be 1, the entire expression will have 50% chance to be 1. To prove this let's consider $A$ and $B$ the probability that $a$ and $b$ are 1 respectively. The probability that $a + b$ is 1 is: $A(1-B) + B(1-A)$. That is either $A$ is 1 and B is 0, or $A$ is 0 and $B$ is 1. If we expand this we have: $A + B - 2AB$. Substituting 0.5 for $A$ gives: $0.5 + B - B = 0.5$. So as long as you can ensure there is at least one term in the final equations that has 50% chance to be 1 independent from other terms, then that will ensure your function is balanced. The simplest way to achieve this, is making sure at least one first order input bit term appears in the functions of all output bits and it will anchor the 50% chance.

Strict avalanche criterion

The next thing to consider is the strict avalanche criterion (SAC).  This means if you change any bit (or more generally any bit pattern) in the input, all bits in the output must have 50% chance to change. Failing to do so can give information to the attacker about the input, and makes your hash vulnerable to differential cryptanalysis. Let $H(x)$ the original hash, let $H(x + \alpha)$ the hash of the changed input. In $H(x) + H(x + \alpha)$ the changed bits will be set. You must make sure this function is balanced too so any bit has 50% chance to be set. Let's se what it means. Let x be the bit we changed. Let $xy + xz + yz$ the expression we test. Let $\bar x$ be the flipped $x$. So the test expression will be: $(xy + xz + yz) + (\bar xy + \bar xz + yz) = xy + xz + \bar xy + \bar xz = (x + \bar x)y + (x + \bar x)z = y + z$. Basically terms that doesn't cointain $x$ will be removed, and $x$ will will be removed from terms that contain $x$. This implies that in order to reach SAC it's a necessary condition that  every output bit depends on every input bit. If there is an output bit that doesn't depend on some input bit, your hash will fail to demonstrate SAC if that bit is flipped.

So now how can you make sure that $H(x) + H(x + \alpha)$ is balanced? There is a class of boolean functions that ensure that. They are the so called bent functions. The simplest bent function is just $xy$ where $x$ and $y$ are independent bits. These bent functions can be combined together by adding them up, so $ab + cd + ef + gh$ will be a bent function too ($a$-$h$ are independent bits). There are other more complex construction too (but I didn't find good examples). So if you want to have SAC, use bent functions. But bent functions come with a drawback: they can't be balanced. There will be a $2^{-n/2}$ bias releative to the 50%.
But this bias approaches zero as the number of bits reaches infinite.

My summary is no way exhaustive.

As the time passes and more and more attacks are discovered so new hash designs need to satisfy more and more conditions, balance, SAC and nonlinearity is a good starting point but probably not enough (I don't know all attacks).

Designing something from first principles just requires inspiration, genius and madness.  Look at:

SHA1("Hello wil3"/0x0a) = a45cc70b69b168e6010b6d1fe2fc9fd358b031ff

The main requirements are simply that it's one way, collision and preimage resistant.  There's nothing fundamentally linking the two sides of this equation otherwise.  There's also nothing (so far) in quantum or gravitational theory (essentially everything) that suggests a hash has to even have a block.  Nothing at all. A stream cipher doesn't and that's cryptographic.  No block means that the need for Merkle–Damgård disappears in a puff of logic.

The best cryptographic example of invention I can think of is the sponge. Read about PANAMA and RADIOGATUN which led to the evolution of innovative spongy hashes. Although to understand the thought processes, you'd probably need to interview the team members.

Parameter tweaking through heuristic rules is commonplace.  This is one of the best examples I've seen of an evolved (rather than procedural) design.  It's an antenna (honestly):-

It's glaringly apparent that this was incrementally evolved, rather than designed by a white collar radio engineer with a slide rule.  It even looks like the route of a hill climbing technique.  Such optimisation was also used to design S boxes, and had positive results. The main issue with these approaches is the danger of local optimums within the value function.  Adding more and more bits to the SHA block width is still not as optimal as the completely different approach of Keccak.  That leap requires a human.  There's an interesting and vaguely similar discussion in From hash to Cryptographic hash.

But on the substantive issue, no, there aren't any short cuts to invention. I'll suggest a biography of  Leonardo da Vinci, Alan Turing or Isaac Asimov.  You're asking for a reference on how to create.  Generally that's reserved for God, but there are a very few lucky individuals.


Why does TLS do Authenticate-then-Encrypt instead of Encrypt-then-Authenticate? Encrypt-then-Authenticate (EtA) seems to generally be considered the better option, compared to Authenticate-then-Encrypt (AtE) (see this Crypto.SE question, for example). The people writing the RFC for TLS 1.2 seem to have been aware of this, but have chosen to use AtE anyway.

Is there a reason why this is the case? Is this a case of "Someone standardized something at some point and now we're stuck with it for backwards compatibility, even though we know it's bad", or is there a good reason why AtE is better for TLS?

Clarification, because this wasn't very well-written originally: I am referring to the actual encrypted channel after the handshake has finished. It's clear that you have to authenticate the server and perform a key exchange before you can perform any useful form of encryption.

SSL was designed long ago when encrypt-then-MAC wasn't that popular yet. Even TLS 1.2, published in 2008, is pretty old by now, and while encrypt-then-MAC was preferred by then, the practical risks were underestimated for a long time. Padding oracles attacks became well known after several high profile attacks in 2010.

With stream ciphers, MAC-then-encrypt is safe and easy to implement correctly. With CBC it's trickier, but technically the way it's used in TLS is provably secure if you ensure that the attacker doesn't learn anything about the cause of a detected manipulation (invalid padding vs incorrect MAC etc).

The choice of MAC-then-encrypt has lead to several weaknesses over the history of SSL and TLS, including POODLE and Lucky 13.

Lucky 13 was a timing attack, which gave an attacker information about why decryption failed, invalidating the proof.
POODLE was an attack against SSL 3.0 (and some careless TLS  implementations) which didn't have as strict padding validation requirements as newer versions of TLS.

In response to these attacks TLS implementations were carefully written to avoid side channel attacks, working around these weaknesses.

There is a draft TLS extension (Encrypt-then-MAC for TLS and DTLS
               draft-gutmann-tls-encrypt-then-mac) to use encrypt-then-MAC, but it didn't gain much traction and still hasn't been finalized.

TLS 1.3 will only support AEAD suites, where each suite is responsible for ensuring both confidentiality and authenticity, instead of combining MAC and encryption at the protocol level. So in TLS 1.3 this problem will finally be fixed.

if you do encrypt first you have to have pre-shared secret keys between client and servers? once master secret is generated then Record protocol job is to encrypt/decrypt.


Security concern with TOTP I am pretty new to cryptography and I have been studying up on TOTP (Time Based OTP) and while I have learnt how the computation works, I'm unable to figure out why using TOTP makes a system more secure.

Here's what I have understood. TOTP is used for 2FA, so the first factor would be your username and password. This as we know is not very secure in itself and hence we use the second factor, here the OTP.

So with TOTP, there is a secret key that both the server and the client have. So my question is that if an attacker has gained access to this secret, would he not be able to generate the OTP just as easily as the client software on my system because HOTP(key,counter) will remain the same for all? So to ensure TOTP is helpful, I have to make sure that the secret key with the client is safe? Let's say I'm making a software that is to be used by the public which uses TOTP based authentication. So will I be attaching a different secret to each of the clients and maintaining a database on the server end to match the secret server side?

If not, what's a safe way to have the same secret on both client and the server in this case?

So my question is that if an attacker has gained access to this secret, would he not be able to generate the OTP just as easily as the client software on my system because HOTP(key,counter) will remain the same for all?

Yes, if an attacker learns your shared secret, he can calculate OTPs whenever she wants. But this is very unlikely, since every secret is unique (no reuse, like with a password) and never transmitted (apart from the initial agreement) a direct hack of the server or the client's token is the only possibility of obtaining it.

  So to ensure TOTP is helpful, I have to make sure that the secret key with the client is safe?

Correct.

  Let's say I'm making a software that is to be used by the public which
  uses TOTP based authentication. So will I be attaching a different
  secret to each of the clients and maintaining a database on the server
  end to match the secret server side?

Yes. Every user has a different key on your service. If you store it in a database or obtain via some deterministic calculation from a master secret is up to your implementation.

OTPs need a shared secret key between client and server and if an intruder learn the secret key he can calculate the OTP in the same way clients do. So you need to keep the secret key secret.

Nevertheless there are still ways to give extra protection even in the case of the secret key were stolen. This could be done using what in the crypto community is called "obscurity" which means to hide the details of the algorithm used for the OTP. In this way, if an hacker enter to a web server and steal the table containing all the OTP's secret key for the client, he could not use it until he learn how the algorithm works.


Proving the existence of a pseudorandom function I've been reading the Introduction to Modern Cryptography book by Katz and Lindell as part of my own learning and have come across this exercise which I am not sure how to approach. The exercise is: (exercise 3.8)

Prove unconditionally the existence of an efficient pseudorandom function
$F:\{0,1\}^* \times \{0,1\}^* \mapsto \{0,1\}^*$ where the input-length is logarithmic
in the key-length (i.e., $F(k,x)$ is defined only when $|x| = log |k|$, in which
case $|F(k,x)| = |k|$).

There is also a hint which states that you should use the fact that any random function is also pseudorandom.

This is my initial train of thought:

We require the pseudorandom function to be indistinguishable from a function chosen uniformly at random from the set of functions that map $log|k|$ bit strings to $|k|$ bit strings (let's say this set is called $Func_{log\,|k|\, \mapsto |k|}$). I'm guessing that we need to work how many functions in this set in order to work out the probability of picking a random function, $f$, from this set.

I know that the set of functions $Func_{n \mapsto n}$ mapping $n$ bit strings to $n$ bit strings contains $2^{n*2^n}$ functions. However my first obstacle is calculating how many functions are in $Func_{log\,|k|\, \mapsto |k|}$ since the functions in this set are not bijective as they are in $Func_{n \mapsto n}$.

If I could calculate this value then I would approach the rest of the problem by calculating the amount of possible pseudorandom functions (clearly given by $|k|$ since $k$ is chosen uniformly at random). I was then hoping, if there was a similar number of functions in $Func_{log\,|k|\, \mapsto |k|}$ (although I speculate there is way more than $|k|$ functions in this set), then eventually try to show that it would be hard for any ppt distinguisher to tell between the pseudorandom function and the randomly chosen one.

I have no idea if this is along the right line and I also don't really know how to bring the hint in to play. All I can think is that it may turn out to be easier to prove that $F$ is indistinguishable from another pseudorandom function which also happens to have been chosen at random.

If anyone could provide a hint as to how to calculate the amount of functions in $Func_{log\,|k|\, \mapsto |k|}$ or pointers for how to approach this then that would be great. As I said, I am doing the exercises for my own good so I'm not massively keen on being given a full solution straight away.

Though this is an 4-year old topic, it seems the following should work:

We can construct a function $F_k(x)$ with output length $l_{out}(n)=l_{key}(n)/2^{l_{in}(n)}=n/2^{O(\log n)}$.

Didivde the key $k$ into $2^{O(\log n)}$ blocks with equal length, denoted by $k_i$ with $i=1,2,\dots, 2^{O(\log n)}$. Because $k$ is uniformly distributed in $\{0,1\}^n$, so is $k_i$.

$F_k(x)= k_x$ is the pseudorandom function.

Preface: of course the following tests alone are not unconditional tests. See below for clarification.

Interesting post Alex. Dan Boneh from Stanford and the Coursera classes Cryptography I and II discusses the statistical test of PRG's which are related to PRF's in terms of an algorithm as the following:

$\{0,1\}^n$ bit strings such that $A(x)$ where $x$ is the input string--outputs $0$ or $1$. Where $0$ = not random and $1$ = random. As Katz discusses too PRF's are indistinguishable from a truly random function.

Examples include $A(x) = 1$ iff (if and only if) the # of $0$'s in the given string $x$ and the number of $1$'s in the string $x$ is not very different. #$0(x)$ - #$1<= 10 * \sqrt n$.

Here is a second example from Boneh: $A(x) = 1$ iff the number of consecutive 0's is the difference between $00x$ and $n/4<= 10*\sqrt n$. $n/4$ just represents the 25% chance from the uniform distribution.

In Boneh's third example we now see logs:

$A(x) = 1$ iff max-run-of-0$(x) <= 10* log_2 (n)$

In order to begin to actually test for a secure PRF/PRG we must look at the concept of advantage:

Where $G:K--> [0,1]^n$ is a PRG and A a statistical test on $[0,1]^n$ then we can define the following:

adv PRG [A,G]= Pr [A(G(k)) = 1 K<--R K - Pr [A(r) = 1] r<-- R {0,1}^n  where we are calculating a specific probability of summing to 1 within the seed space and how likely an output from a ST outputed from a generator and 1 from a truly random string.


Public Randomness-Based Random Number Generator using Mobile Phone? I have an idea to create a True Random Number Generator that use randomness source from a smartphone sensors. My idea is to collect sensors data from a lot of smartphone using mobile apps and then the data is sent to the server to be processed using an algorithm to generate random number.

Is it a good idea to use that method to generate random number? and will it be better using a lot of device rather than just using one device only to generate random number? Can I call that method as Mobile sensor network?

Be careful about the phrase “True Random Number Generator”. There's a bit of hype in that phrase. You do not need to use a TRNG directly to do things like generate cryptographic keys — in fact, you should not, because all TRNG have biases, because even if the underlying physical process has a truly uniform probability distribution, it's impossible to build a perfect measurement apparatus. A good random number generator for cryptography is always hybrid: a cryptographically secure pseudo-random number generator ((CS)PRNG, also called a deterministic random bit generator ((CS)DRBG)), which is seeded by one or more entropy sources. A physical device whose purpose is to serve as an entropy source is sometimes called a “TRNG”, but a less misleading name is HRNG (hardware random number generator).

An entropy source needs to have two properties:

It needs to be unpredictable. It needs to depend on a physical process whose outcome cannot be predicted in advance. This is typically a either a chaotic physical process or a process with physically theorized unpredictability such as radioactive decay.
It needs to remain unpredictable even after the fact, i.e. its output needs to remain secret. An entropy source is no good if it's public. If your adversary can construct the same system state as you because they can read the same entropy sources, then they can generate the same keys that you're generating.

Obtaining entropy from outside is dodgy because it violates the second property. You have no way to know that the data you're collecting from smartphones is actually coming from a HRNG, and even if it is, you have no way to know that it's only sent to you and not leaked to anyone else.

Fortunately, if you do things right, then when you mix entropy sources, a bad source (not sufficiently random or not sufficiently secret) doesn't hurt: it'll contribute 0 to the total entropy of your system, but it won't nullify other, good entropy sources. So assuming that your server-side code is perfect and that at least one of your entropy sources is good, then the result is ok. The flaw in this argument is that code is never perfect.

All modern server hardware has a built-in HRNG. (If you don't trust it, you have no reason to trust the rest of the processor. So “I fear a backdoor in the processor's RNG” is not a valid argument.) Collecting additional entropy from outside has no benefit. It's a lot of infrastructure, meaning a lot of failure points and a large attack surface, for no benefit.

Gathering entropy in a distributed way like this does have a benefit for a very specific application: when you want to generate a public value which should be demonstrably random. In that case, allowing everyone to contribute their entropy, and using a public, deterministic way to combine all the submissions, does result in a demonstrably random value.

In theory yes it can work. There is precedent for this with:

True random numbers generated by sensors
Entropy of Androids motion-sensor data
Towards True Random Number Generation in Mobile Environments (PDF)

So you can use the camera, accelerometer, compass and speaker.  It think that there's even a  horizontal level sensor in some phones.  But there are three main obstacles that you'll have to overcome.

A golden standard true random number generator requires that (entropy in) > (entropy out).  And usually by a lot more, say a factor of 4.  Measurement of entropy is hard.  There is NIST Special Publication 800-90B, Recommendation for the Entropy Sources Used for Random Bit Generation.  See section 6. You'll spend for ever trying to use it properly, and in the end it's easier to simply use a compression tool like a PAQ derivative and divide by a safetly factor of 2.  If you can't measure it, you can't manage it.
With initialisation, you get a form of warming up of the entropy sources.  The entropy rate will measure as a lot lower until the sensors (and the person sporting the phone) settle down in some sort of routine.  This will make restart testing a nightmare if you follow section 3.1.4 from the above NIST document.
Entropy sources have a nasty habit of slowly changing their parameters wrt time.  The entropy generation rate will change drastically depending on whether the phone is at an exciting football match or in a quiet room whilst you meditate.  Or the sensors can simply break   when you drop the phone or get beer in the microphone.  Don't forget that accelerometers are actually flexing mechanical devices (albeit made from semiconductor), with similar frailties to any moving instrument.

In summary, no one uses a mobile phone as a reliable TRNG.  I guess it would be okay to generate one AES key after a day's play on a bouncy castle (get it?), but otherwise it will be very unreliable.  Interconnecting several phones into a network will be equally unreliable as you'll have little control over what all the phones are doing.  One might be down the toilet bowl.  And you'd also have to transmit the entropy over the airwaves which are easily intercepted by either the network provider, or covert police network towers.  Never transmit your entropy to no one.

Stick to a few Zener diodes and an Arduino.  A reliable 10 kbits/s of true ransom bits is achievable with a little wiring and a few components.  This is more than sufficient for personal one time pads and all the AES keys you'll ever need.


Pseudocode for constant time modular exponentiation I'm looking to implement modular exponentiation (for RSA) in constant time, but most of the examples I've found are more mathematical descriptions of the operations. Are there any references with descriptions in psuedo-code, which are understandable (and implementable!) by someone without much of a math background?

No.  If you don't have a strong math background, implementing RSA yourself is a  bad idea (and perhaps even if you do).  There are many ways to go wrong, which can open up subtle security weaknesses.

Instead, you should use a well-vetted RSA implementation from a standard crypto library, and a well-vetted protocol -- or hire a cryptographer who does understand the mathematics, if you don't think you can trust any existing implementation or need help selecting one that is suitable.

The follows may be helpful:

compute:$ M^e $ (mod n)

  $ e=e_{k}e_{k-1}...e_{1}e_{0};$
  $ c=1 $

  for $ i=k $ downto 0
      $c=c^{2} \pmod n$
      if $ e_i = 1 $ then $ c=c*M \pmod n$

  return c


Nothing-up-my-sleeve numbers standard Premise
Several cryptographic primitives employ randomized numerical constants. To avoid suspicious that the designer selected such constants in order to plant a backdoor, "nothing-up-my-sleeve numbers" are used. These are numbers constructed from the first digits of some important constants, like $\pi$, $e$, $\sqrt{2}$, ... so that they do not appear to be well-crafted to hide a backdoor.
The Problem
However, designers of different systems use different constants. Below some examples copied from the wikipedia's page:

Small roots of small integers (SHA-1, SHA-2)

$\sin 1, \sin 2, \dots$ (MD5)

$e$ (DFC)

$\pi$ (Blowfish and many other)

$1/\pi$ (ARIA)

0x123456789ABCDEFFEDCBA9876543210 (KASUMI)

ASCII string "expand 32-byte k" (Salsa20)

But with enough degrees of freedom, it is clear that nothing-up-my-sleeve numbers lose their purpose. For example, who does guarantee that the sentence "expand 32-byte k" was not selected among thousands of similarly innocent ones ("expanding 32-byte k", "expansion of 32-byte k", "32-byte expanded k", ...) in order to hide a backdoor? Likewise for numerical constants.
The Question
In light of the previous considerations, was a "nothing-up-my-sleeve numbers standard" ever proposed? If not, why not?
A very simple standard could be: "A cryptographic primitive employing a randomized constant $C$ (if there are more randomized constants, $C$ is their binary concatenation) must fix $C$ to be the first digits of the binary representation of $\pi$."

A (probably weak) reason not to use a standard is that some nothing-up-my-sleeve numbers may serve some sort of purpose.  As an example, you cannot change Salsa20's constants to anything, it must be sufficiently asymmetric.  It's feasible to presume that another cipher may have a different set of requirements
As per this answer:

Salsa20 has strong rotational symmetry. The main point of these constant is that they're not invariant under rotations, introducing an asymmetry. The precise value isn't very important, as long as it's sufficiently asymmetric.

The answer goes into further detail, quoting DJB himself on the matter.
This answer also details several cryptographic constants, and the padding constant for HMAC is similarly designed to be asymmetric:

The padding constants for HMAC, 0x36 for ipad and 0x5C for opad, are repeated (for the hash function's block size) and XORed with the key to generate the prefixes for the two hashing steps. 0x36 = 0b00110110 and 0x5C = 0b01011100 - these two values are about "as different as possible", to avoid any attacks which rely on a similar hash state after the key block for inner and outer hash. This is mainly a heuristic, as far as I understand.

There's also a very good reason that no one will want to.
A 'designer' gets to choose the initialisation constants for their new primitive/what have you.  But there are only few people in the world with sufficient qualifications to do so if their baby is to be adopted into general use. To wit, the designer's have the power.
Logically you're correct, just settle on $\pi$ digits. Yet you've also listed $\frac{1}{\pi}$. Why? Why all that load of $ \sin(\mathbb{Z}) $? And more exotically, there's NewDes which draws upon the US Declaration of Independence. I wouldn't be surprised to see something in the future with constants based on the names of the characters in the extended Sesame Street universe.
Why? Philosophically, because it's a signature. It's hubris, showmanship and bravado. An artist (even a mathematically focused one) does not want to repeat others' work. I wouldn't. That's why there are so many different mechanisms for creating them, progressively getting more imaginative/weirder.

"But with enough degrees of freedom,..."

You're right. "expand 32-byte k" does sound a little suspicious even if it's not. That segways directly to:-

"I no longer trust the constants."

-Bruce Schneier.
But you do have to trust Elmo, Grover and Kermit.


Is there a definition of the pseudo-random sequences like PRG or PRF in cryptography? I have learned the definition of PRGs and PRFs. As I know the meaning of pseudoreandomness. I think that the pseudo-random sequence and the truly random sequence are indistinguishable.

I did not find a definition of the pseudo-random sequences. And I think the definition should describe some possible collections of "pseudo-random sequences" (e.g. M-sequence).
Follows are my approaches which may be helpful.

Let a sequence $\alpha = (a_{1}, a_{2}, \ldots, a_{n}, \ldots)$ is a sequence over a finite set $\Sigma$ ($|\Sigma| > 1$), where $a_{i} \in \Sigma$. It is truly random if $a_{i}$ is chosen uniformly in $\Sigma$.

Let $\beta= (b_{1}, b_{2}, \ldots, b_{n}, \ldots)$ be a sequence over $\Sigma$. It is pseudo-random sequence if for every PPT algorithm $A$, there is a negligible function $\varepsilon$ such that

$$\left\vert \Pr \left[ A(b_{1} \Vert b_{2} \Vert \cdots \Vert b_{n}) = 1 \right] - \Pr\left[ A(a_{1} \Vert a_{2} \Vert \cdots \Vert a_{n}) = 1 \right] \right\vert \leq \varepsilon(n)$$

Or can we consider that it is unpredictable? Let $\beta= (b_{1}, b_{2}, \ldots, b_{n}, \ldots)$ be a sequence over $\Sigma$. It is pseudo-random sequence if for every PPT algorithm $A$, there is a negligible function $\varepsilon$ such that

$$\left\vert \Pr \left[ A(b_{1} \Vert b_{2} \Vert \cdots \Vert b_{n}) = b_{n+1} \right] - \frac{1}{|\Sigma|} \right\vert \leq \varepsilon(n)$$

I think that the pseudo-random sequence and the truly random sequence are indistinguishable.
And I think the definition should describe some possible collections of "pseudo-random sequences" (e.g. M-sequence).

Congratulations, you have a very good intuition! You're almost there.
A key to understanding the definition of a pseudorandom sequence is that there is no such thing as a pseudorandom sequence. If you have a specific sequence, then there's no randomness involved! Instead, the useful concept is that of a pseudorandom sequence family, more usually called pseudorandom function family (but abbreviated PRF). In a nutshell, a pseudorandom sequence family is a family of sequences such that given some data that may or may not be part of a sequence in that family, and bounded computational power, there is no way to know whether the data is from a sequence in the family or was generated uniformly at random. In other words, a pseudorandom sequence is indistinguishable from a random sequence.
Note that “uniformly at random” here is a mathematical definition: a uniformly random bit sequence is one where the value of each bit is independent (in the sense of probability theory) from the value of other bits as well as from all other events in the world. This definition does not consider whether it is possible to perform this generation in the physical world.
The definition of pseudorandomness only considers the output of the process, not how this output is produced. Otherwise it would be a circular definition: a pseudorandom generator is one that produces pseudorandom output — “pseudorandom output” has to have some definition other than where the output come from. The definition is about what you can deduce from observing the output. A pseudorandom generator is an algorithm that transforms a seed into the element of a pseudorandom sequence family that is indexed by the seed value.
To put this indistinguishability in more mathematical terms, consider an observable property $A$ of the output. For example, “bit $3$ is 1 and bits $4$, $5$ and $6$ are not all equal”. This observable property has a certain probability $\Pr_U(A)$ of being true for the uniform random distribution ($\frac{1}{2} \cdot \frac{6}{8}$ for the example above). If you pick a random element of the pseudorandom sequence family $F$, the probability of this observable property $\Pr_F(A)$ must be close enough to the probability for the uniform random distribution: $\Pr_F(A) \approx Pr_U(A)$.
To make this definition fully precise, we still need to say what observable properties are permitted and what “close enough” means. We aren't interested in adversaries with infinite computational power, which is why we restrict $A$ to polynomial computations. And “close enough” is defined as bounded by a negligible function. That's how the equation in your question comes about. The piece that you were missing is that you don't first select specific sequences $\alpha$ and $\beta$. Rather, $\alpha$ and $\beta$ are a probability distribution over sequences: $\alpha$ is a choice of element of the function famility, and $\beta$ is a uniform choice over all possible functions.

The relevant Wikipedia entry states:-

  In the asymptotic setting, a family of deterministic polynomial time computable functions $G_{k}: \{0,1\}^{k} \rightarrow \{0,1\}^{p(k)}$ for some polynomial $p$, is a pseudorandom number generator (PRNG, or PRG in some references), if it stretches the length of its input ( $p(k)>k$  for any $k$), and if its output is computationally indistinguishable from true randomness, i.e. for any probabilistic polynomial time algorithm $A$, which outputs $1$ or $0$ as a distinguisher,

  $$\left|\Pr _{x\gets \{0,1\}^{k}}[A(G(x))=1]-\Pr _{r\gets \{0,1\}^{p(k)}}[A(r)=1]\right|<\mu (k)$$

  for some negligible function $\mu$. (The notation $x \leftarrow X$ means that $x$ is chosen uniformly at random from the set $X$.)

  There is an equivalent characterization: For any function family $ G_{k}:\{0,1\}^{k}\to \{0,1\}^{p(k)}$, $G$ is a PRNG if and only if the next output bit of G cannot be predicted by a polynomial time algorithm.

You also mention unpredictablility (as does the above definition), and indistinguishability. However I believe that is only true within a strictly limited context, whilst  looking at nothing more than the output. Holistically, a pseudo random sequence is neither, as your $ \beta$:-

Is entirely predictable and distinguishable  by $ \in (Alice, Bob, Eve)$.
It is distinguished by the fact that the cycle $|\beta| < \infty$.
Only remains secret and random for $Eve$ whilst $N \neq NP$.

The conclusion seems to be that there are multiple definitions and distinctions.


What is the most secure ECC Curve? I have for a while used Koblitz curve (sect571k1), in ECDH and ECDSA. But I have started wonder if it is the most secure. I prefer security over efficiency. So the curve doesn't have to be the most efficiency curve.

I'm not looking for a curve that is only secure today, and the next few years. The compute power increases rapidly today, and I'm looking for a curve that is secure as far as possible in the future. So if someone is able to steal my encrypted data today, they should not be able to crack it in next 20 years, hopefully longer.

There is no such thing as the most secure curve. For one you can always come up with a larger curve if you need one. For another there are many measures of security and not all curves are directly comparable.

If you wanted the curve for which the current best known attack is the slowest, then by that measure sect571k1 is actually the most secure out of the curves that are in use.

However, that is not necessarily a very useful requirement, because any curve for which the best known attack is slower than ~128-bit strength equivalent will never be broken without either advances in attacks or the arrival of practical quantum computers. Those advances need not apply equally to all curves, while quantum computers would break all curves regardless of strength.

Binary field curves like the one in question are sometimes considered more risky because better attacks are known than for prime field curves of similar size, so it is thought that new attacks are more likely. That is a judgement call.

Likewise there are other measures of security that do not apply to all curves. Perhaps the most talked about is the potential for some kind of backdoor in the parameters, which makes some distrust NIST curves in particular and any curves without a good explanation for the parameters in general. Also things like ease of secure implementation may matter in practice.

There's no @secure@ cipher : everything is crackable, it's just a question of time and resources. The "longer the key"/"bigger the block"/"more bits" - the more difficult and laborious is to crack the system. Use the longer/bigger variants.


Why are PRNG in programming languages not cryptographically secure by default? In most programming languages, there is a module or function in the stdlib for creating random output like random.random() in Python.

Because those functions use a normal PRNG that is not cryptographically secure, over all the years those generators have been used for crypto nonetheless because of the name "random".

Why do not programming languages use only cryptographically secure PRNGs in the stdlib? It's able to produce random output even if not needed for crypto and it's secure if you use crypto.

Is there an advantage of normal PRNGs compared to CSPRNGs? I'd be happy if you could explain it in a way that someone like me without any crypto background can understand, thanks a lot! :)

First, insecure PRNGs are typically faster than CSPRNGs. CSPRNGs based on /dev/urandom (if you're familiar with Linux), for example, have to call the crypto kernel module driver every time. For reference:

the BearSSL implementation of ChaCha20, which can be used as a CSPRNG, on an Intel Xeon CPU at 3.10 GHz, reaches 270.72 MB/s;

an implementation of a Mersenne Twister, which is a typical PRNG, on an Intel Xeon 5160 at 3 GHz, reaches 113.4*32/8=453.6 MB/s;

there are even faster algorithms/implementations. For example, the rand() function in the GNU Scientific Library, according to the same paper, reaches 227.8*32/8=911.2 MB/s. Xorwow, which belongs to the Xorshift PRNG family, reaches 1388.4 MB/s.

Second, writing cryptographic software, including CSPRNGs, is much more complex than writing general-purpose software.

There are also historical reasons. At least until the 1990s, developers, including some developers working on standardizing new programming languages, were afraid to deal with cryptographic algorithms, because the export restrictions on cryptography were severe and not entirely understood by them. Quoting one such developer:

  I would not have even considered putting crypto strength randomness into anything that shipped with the browser without getting a huge amount of legal advice from the MSLegal team. I didn't want to touch crypto with a ten foot pole in a world where shipping code was considered exporting munitions to enemies of the state. This sounds crazy from today's perspective, but that was the world that was.

What about more recent programming languages, such as Python?

Some people argue that baking CSPRNGs into programming languages by default would lead to a false sense of security, especially as new flaws arise and when dealing with older software. Say that now, in 2018, random is cryptographically secure. Do developers remember to check, when dealing with older versions, that the old random was actually insecure?

An interesting quote on this matter:

  Anyone writing crypto code without reading the docs and understanding what they are doing are surely making more mistakes than just using the wrong PRNG. There may be a good argument for adding arc4random support to the stdlib, but making it the default (with the disadvantages discussed, breaking backwards compatibility, surprising non-crypto users, etc.) won't fix the broken crypto code. It will just give people a false sense of security and encourage them to ignore the docs and write broken crypto code.

See this for more insight on how the Python community was reasoning about implementing a CSPRNG by default.

TL;DR. They are faster and easier to implement. In the past, people were afraid of crypto, because of heavy restrictions. Now, people are afraid of giving a false sense of security.

They are two completely different things with no overlapping purposes.

You want a uniformly distributed floating point number from 0.0 to 1.0 when you are doing things like random simulations.  The random number distribution is more important than the number of bits in the random number.  There is no notion of Entropy here.  Entropy is a well-defined number of bits of uncertainty.  The interface being satisfied is generally going to be:

func(prngState) float // from 0.0 to 1.0, ideally uniformly and randomly distributed

A cryptographic random number generator is giving you a string of bits with a known amount of entropy.  Entropy is everything in this situation.

func(cprngState) []byte // n bytes means 8*n bits of entropy in the ideal case

For every bit of entropy, there is a doubling of the space of uncertainty.  If you sha256 hash a number from 0 to 7, then there are only 3 bits of entropy -- not 256.  256 is just the number of bits of the result.  But you only need to generate 2^3 possibilities to figure out the hash input if there are 3 bits of entropy.


How to use proof of lack of knowledge? This is a purely hypothetical example but is provable ignorance useful in cryptography?

For example, let's say I have a trapdoor collision resistant function. I know the trapdoor and therefore some $x_0 \neq x_1$ such that $f(x_0) = f(x_1)$. This is however, hard to find. If someone proves they know $x_0$, I can conclude that they do not know $x_1$.

Is there any context where more complicated versions of such problems is useful?

In general, you cannot prove lack of knowledge, because even if you did know something you shouldn't, you can always pretend that you don't know it and carry out the proof as if you didn't know it.

For your specific example, consider how the prover would know $x_0$.  Did you tell them what it is?  If so, that proves nothing, since they would then know $x_0$ even if they had also learned $x_1$ from somewhere else.

Conversely, if your function $f$ is collision resistant without the trapdoor, but is not injective (i.e. potential collisions do exist), then it must also be preimage resistant.  Thus, finding $x_0$ from $y = f(x_0)$ is (at least) as hard as finding $x_1$.  Thus, paradoxically, the prover exhibiting $x_0$ would in fact be evidence that they can find preimages for $f$, and thus can probably find $x_1$ as well.

non-hearsay, eye-witness testimony of the side of a coin after a coin flip. Conversation between interviewer I and witness W, where the only "knowledge" that can permissibly enter the court record is direct eyewitness testimony:

I: did you witness the coin toss?
W: Yes.
I: Did you view the coin once it had landed?
W: Yes.
I: Can you describe the picture on the coin?
W: It was a a picture of an eagle?
I: What was depicted on the obverse side of the coin?

OBJECTION, the answer would be speculation. The witness has already dis-qualified his ability answer.


How is QKD (Quantum Key Distribution) advantageous over McEliece/AES? I don't understand the popularity of the idea of QKD (often coupled with OTP). From what I can tell, a quantum-safe key exchange algorithm like McEliece has just as much security while operating over current networks, through repeaters, and not requiring single-photon emitters. Combining this with AES seems convenient and practical.

Why would one ever choose QKD over McEliece?

The only reason I can discern is that there is some possibility that a yet-to-be-discovered algorithm may weaken McEliece or AES.

Because it's the Holy Grail of cryptography.
To be specific, it's not unbreakable as the layman's literature suggests. It's that a quantum transmission of key material cannot be intercepted without the sending/receiving parties noticing. It is the Observer Effect in physics and a fundamental part of the Universes. Knowing that you're being spied upon in many ways gives you the advantage.
And if you can securely transmit a lot of key material, you can then use one time pad (OTP) techniques for the encryption.  And OTPs are provably secure via information theory. McEliece/AES being limited key length based ciphers are not.  Just because the academic community can't break McEliece or AES, doesn't mean that they haven't already been by state actors, or will be tomorrow by Alexander Verykleverkov in his university dorm room. Perhaps Shor's 3rd improved algorithm might work against McEliece. The point I'm labouring is that you can prove photon interception/OTP security now, but not McEliece/AES. All we have is an absence of evidence for them.

The only reason I can discern is that there is some possibility that a yet-to-be-discovered algorithm may weaken McEliece or AES.

You've answered your own question :-)  Israel can keep defence-related documents sealed for 70 years.  The UK had 50. Their transmission may have been intercepted or copied and stored. You cannot guarantee that they won't be teaching McEliece/AES breaking in high schools by 2091.
That's why there is a market for QKDNs. See all the interest in this older answer, and ponder the quotation at it's end. It's incredibly alluring, and if you want one, buy one of these:-

It's a node for commercial QKDNs. Cerberis from ID Quantique.


Is it cryptographically insecure to use fixed-length AES-GCM messages? Is there any weaknesses to encrypting fixed-length messages? Should a random amount of padding be added to the message to decrease the odds of some sort of attack?

An adversary who obtains AES-GCM ciphertexts but does not know the key cannot obtain any information about the plaintexts except their lengths. This is (in a highly simplified form) the definition of the claim that AES-GCM is secure. This is true for any secure authenticated cipher.
If your plaintexts are intrinsically all the same size, this is an ideal situation, because the ciphertexts leak no information at all about the content of the plaintext.
If your plaintexts can have different sizes and the size of the plaintext leaks some information that you want to keep secret, then padding plaintexts so that they all have the same length is a possible solution. Beware that the generation of the message, the padding process, the unpadding process and the processing of the unpadded messages are likely to take time that depends on the length of the plaintext, so it may still leak through timing. Appending padding to the message may not be the best solution: depending on how the message is structured, it may be easier to construct a secure system if you arrange each part of the message to have a fixed size, and concatenate those fixed-size parts. That way the assembly and parsing of messages is less likely to reveal confidential information through side channels.
Adding a random amount of padding is unlikely to help security. In particular, if the same message is likely to be transmitted many times, an adversary can average out the lengths, which will negate the uncertainty of the random padding. However, it can help in some scenarios where you want to hide which message was transmitted for privacy (for example, to make it harder to figure out which file a user download on a server). Still, the only fully reliable way is to have fixed-size messages (in the download privacy example, this would mean padding all files to the length of the largest one).

Yes, it may be because the size of the message is directly leaked. This is the kind of thing that professional cryptographers learn at the first day and then forget about. However, it depends on the type of message that is encrypted and the context if hiding the size makes any difference.
Usually the size of the message is indicated in bytes. GCM can work on any bit string, but generally implementations require a plaintext message be build out of bytes. Adding a random amount of padding or padding up to a certain size can help disguise the size of the message.
Any encryption leaks some length information about the plaintext message, even if padding is applied. If the ciphertext is a certain size then the plaintext message fed to the cipher needs to be smaller after all, and padding won't help against leaking that kind of information.
Beware that statistical data may still reveal information about the plaintext messages before encryption, especially regarding max and minimum sizes. Adding, say, 0..10 bytes of random padding will also not help that much if your message is e.g. multiple gigabytes in size. If you can pad to the maximum message size that is best, but of course it will could create a lot of ciphertext.
Note that I would then deliberately put padding inside of your protocol, to be applied before GCM is used. You can use any padding value. Don't use one of the existing padding modes used for block ciphers and combine that with GCM. For instance, you could specify "AES/GCM/PKCS5Padding" in Java, but that really doesn't make sense at all; it may work differently in specific implementations, if it is not outright rejected.
GCM itself works perfectly fine with fixed size messages, other than the more generic issue about leaking information about the plaintext (which every mode does to a certain amount).


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

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


Why aren't zero-knowledge proofs used in practice for authentication? I read on Wikipedia that zero-knowledge proofs are not used for authentication in practice. Instead (I think) the server is entrusted with seeing a password in plaintext form, which it should then add a salt to and hash. But for a split moment, the server knows the secret. Why should I implicitly trust the server like this? It could go rogue and record my password in plaintext form. I could use that same password for other sensitive things. Aren't zero-knowledge proofs a necessity? Why aren't they used? Or are they used?

Update, an alternative: What about never reusing your password and instead generating different passwords from a master password and website name using only a program that runs on the client? It seems much simpler, because you never reveal the master password. That way, you don't need to trust the website nearly as much.

This clarifies my previous question.

Answering the question in your title (and not addressing your proposed alternative which I don't quite understand) there is a zero knowledge proof of password protocol "SRP" which is fast and effective.

SRP does not seem to have been given as wide publicity as it should get. Having implemented it, and being an advocate of its use, I don't really understand why everyone doesn't use it all the time. Some reasoning that I have seen for dismissing it are:

A belief that a server is either totally 'good', or totally 'bad', and that using HTTPS ensures you always talk to 'good' servers, which can be trusted with plaintext passwords. Real life just isn't like the movies; it is more complex. The Heartbleed debacle shows that an otherwise trustworthy site can be leaking bits of memory such that a plaintext password sent over HTTPS can be observed by 3rd parties. More common would be poor error handling in custom website code which would print out a plaintext password into a log file which can be read by an intruder who can only see the file system on the server. Large systems stream logs to a central local exactly to make it easier to look at errors in logs where many people can search for patterns.
A belief that the client is either fully secure, or totally compromised, such that an attacker can see nothing, else can record what is being typed. If an attacker can record what is being typed they can steal the password directly; SRP only protects against interception on the wire and the TLS protects the wire. In reality interception is much more routine than people realise even using well configured HTTPS. Large employers routinely decrypt and scan HTTPS to protect themselves from intellect property theft by their employees. Even if they are only doing this to protect their own digital property rights it increases the risk of bugs leaking plaintext passwords or else a rogue employee stealing passwords. Big laptop suppliers install things like superfish to decrypt customers HTTPS traffic to sell "smart ads" on pages. They might not be all bad people; but it increases the risks of bugs leaking passwords or else a rogue employee stealing them. There have also been examples of certs being compromised meaning that encrypted traffic can be snooped. All this means that it might often be the case that an attacker cannot directly record what the user typed at the keyboard; but can view anything passed over the network even when HTTPS is being used. SRP can protect against any such interception as it is a zero knowledge password proof.
A belief that SRP is an positioned as an alternative to HTTPS. SRP does not (out of the box) verify the server (upon registration) so you might be talking to a fake server. So in an "either-or comparison" of SRP and HTTPS (assuming none of the problems detailed above) then HTTPS is often judged superior. This is a false dichotomy as in practice real world HTTPS has many weaknesses which can be addressed by using SRP over HTTPS. Performing SRP over HTTPS gives you server verification which strengthens SRP. So people should always be using both together.
A lot of focus on two factor authentication as an enhancement to plaintext passwords. Companies who have identified that passwords are high risk tend to employ a second factor (say, a text to your phone). The site may still leak passwords, which users may be using on multiple sites, many of which don't use a second factor. If sites upgraded to use SRP and a second factor they would fully protect their users.

When it comes to implementing SRP there are a couple of inhibitors:

A historic lack of a pure JavaScript examples. An early authoritative demo used a Java applet. Recently after the Heartbleed debacle there has been a revival of SRP and there are now a few solid opensource JavaScript libraries and demos.
An extra round trip to login. With plaintext you send username and password in one post. With SRP you first send username to get the salt (and a challenge) and then generate the password proof to send to the server. Most web security frameworks assume that everything is sent in one round trip. This can be addressed by an AJAX call for the first round trip and posting the password proof as the password. More sites are now splitting username and password across two pages to implement ”social login”. Based on your email given at the first page they present a password page that targets the correct social login server. This two page pattern fits well with SRP and end users are becoming more familiar with it.

Having said all of that there is no good reason why every site doesn't now use SRP. So you are correct in being surprised that plaintext passwords are still in use.

Update: I still encounter quite aggressive push back about SRP from crypto experts who are arguing about TLS being sufficient. I am sure they are only hired by high security outfits that (in theory) would never make the mistakes listed above. The fact that they use their theoretical knowledge to shoot down a practical additional defence in depth strategy of both TLS and SRP is a surprise to me. I didn't become a fan of SRP for theoretical reasons. I became a fan after the online banking system I had just upgraded failed its penetration testing with perfectly configured TLS with the external tester managing to harvestest live passwords. As my grandfather told me ”In theory, both theory and practice are the same. In practice, they are not.” Passenger airlines use redundancy to keep people alive. Security practitioners should use defence in depth rather than a theoretical model of security.

But for a split moment, the server knows the secret

... and so is the wireless bug in the cable of the keyboard, the web-cam of your laptop and iPhone, the microwave microphone of the satellite eavesdropping the sound of your keystrokes, etc. If you are afraid of the server don't go in Internet (it is not the server, BTW -it is the screen memory capturing your passwords that is not getting out of the memory ... but remains traces that can be traced and captured) you may use a smart-card for hashing and salting your password before supplying it to the server.

  I could use that same password for other sensitive things. Aren't zero-knowledge proofs a necessity?

When you start using a one-time pad as multi-time breakout in the cryptography the zero-knowledge proof is your least problem. Any start up hacker on the communication line can break your 'same password' just for breakfast.


Is a random string good for an AES-256 instance I have a randomly generated string of about 256 characters long. This string is hashed to for a key and initialization vector for a program running on the .NET framework 4.8. Is this method secure from a professional point of view?

The Following Code Is Now Using The Password Derive Bytes Function, All Values Will Be Changed Accordingly
    string Password = "Example";
    byte[] IV = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
    byte[] Salt = Encoding.ASCII.getBytes("Salt Example");
    PasswordDeriveBytes pdb = new PasswordDerivedBytes(Password,Salt);
    Aes Alg = Aes.Create();
    Alg.Key = pdb.CryptDeriveKey("Aes","SHA256",256,IV);
    Alg.IV = IV;

The Code Above Is C#


Do I need to prepare plain text before encryption? When I want to encrypt chat messages (in ASCII) before sending, whether it brings some bit of security if I add some extra bytes to the message or shuffle it in some way? I can even try to make data to look like uniform distribution.

Because chat messages consist only of letters and even words, but don't contain binary data and other bytes except that from ASCII, so it gives some information about unencrypted data to eavesdropper.

But I'm afraid that some manipulations over the text could bring much more information to the attacker than doing nothing.

If you are using a modern, secure cipher, there is no reason whatsoever to perform such manipulations of the plaintext.

I'm not sure how to elaborate much more on the topic than that. The entire purpose of a cipher is to perform the exact types of confusion and diffusion you describe. Only, the approach that it will use has been designed, peer-reviewed, and cryptanalyzed by professional cryptographers. Your hypothetical algorithm has not.

At best case, it will do nothing to improve the security of your ciphertexts. At worst case, you can introduce bugs that unintentionally cause plaintexts to be unrecoverable from the ciphertext, or ones that accidentally reveal information about the plaintext (for instance, via a leak of timing information).

When I want to encrypt chat messages (in ascii) before sending,
  whether it brings some bit of security if I add some extra bytes to
  the message or shuffle it in some way? I can even try to make data to
  look like uniform distribution.

I recommend to encode your chat messages with base64 before encrypting and sending them through the chat channel. This method has advantages and disadvantages though.

Advantages:

It obfuscates the plaintext and adds more complexity and an extra layer of security, because when brute-forcing your ciphertext an attacker would be forced to guess base64-encoded strings instead of direct phrases or words from a dictionary as usual.
You can also use this very efficiently to obfuscate all your internet passwords and make them tougher and longer quite easily.

Example:

1. Plain Chat Msg = Hi there!
2. Base64 Chat Msg = SGkgdGhlcmUh (Layer 1, Encode of 1.)
3. Encryption of 2. (Layer 2)
4. Ciphertext

Disadvantages:

Base64-encoded text would be bigger in size than the original plaintext due to the conversion method. In a chat conversation it would probably be no problem since most chat messages are short anyway.
Base64-encoding is not encryption but a data conversion method of any type of data to printable ASCII characters, thus an attacker could also encode words, passwords or entire phrases from a dictionary with base64 when running a brute-force attack on ciphertexts. This way the attacker could bypass the base64 security layer.


Integer encryption preserving equality I have read too many different options for encryption that I now feel quite lost. I need a simple, secure (don't we all) scheme for encrypting integers (32-bit) with the following requirements:

Ciphertext is also an integer (32-bit) or a long (64-bit)
For integers x1=x2 then ciphertexts E(x1)=E(x2)
For integers x1<>x2 then ciphertexts E(x1)<>E(x2)
If I know E(x1) it will be very hard to decrypt x1 without the (private) key

Is there such a simple scheme?

Some of your conditions are already met by the definition of an encryption scheme:

Encryption has to be reversible, so that a ciphertext can be the encryption of (at most) one plaintext.
Your last point is basically just a ciphertext only attack. That is usually the weakest considered attack, and for todays security definitions not enough. So any scheme which is considered secure, it also includes this.

The only non-trivial part is your first point, because it is not that easy to find an encryption scheme, which has ciphertexts of 32 or 64 bit length. Of course you could use 3DES (64 bit), but that should not be recommended any more today. But there are other options:

Stream ciphers don't expand the ciphertext. When choosing a stream cipher, use a current one, and consider to use keystream btis beginning after some threshold. RC4 is popular but has quite a few security problems.
Using a block cipher in OFB, CTR (or KFB) mode of operation functions very similar to stream ciphers, and you can just drop the bits you don't need.
Format preserving encryption is a method which enables you to have that 32 bit to 32 bit relationship. But there are a lot of constructions, and quite a few build upon the other mentioned methods.

The main problems using stream ciphers for this type of encryption are 1) you should not use the same key stream more than once and 2) linear operations such as cipher-text = plain-text XOR key-stream enables indirect plain-text modification simply by cipher-text changes (toggling a bit of cipher-text toggles the same bit of plain-text).
For a better approach, have a look at https://github.com/msotoodeh/integer-encoder. It supports 32 and 64 bit integer encryption.


AES Decryption followed by Encryption, will it produce the original text? If a plain text is first decrypted (with the AES decryption algorithm) using Key K1 and then encrypted using same K1, would the final result still be the original plain text?

If you are talking about the AES block cipher acting on a one block message, then yes, with K being the actual 128/192/256 bit-key.  For a given key, the encryption E(message, key) and decryption D(ciphertext, key) functions are perfect inverses of each other.  You will always have both E(D(m,K),K) = m and D(E(m,K),K) = m by construction for any block cipher encryption/decryption functions operating on a one-block message m (for AES one block = 128-bits = 16 bytes).

That said in practice, if you use some well-written tool in a secure mode (like openssl aes-[128|192|256]-cbc) that internally uses AES as the block cipher for encryption/decryption this probably will NOT work, if you simply feed your tool a plain text message and ask it to decrypt said message with your key.

This is because your tool that uses AES as your block cipher will make various assumptions for you and does more than just apply AES to each block.  Specifically:

The tool will likely add proper padding to your message before encrypting it and will fail to decrypt if you are attempting to decrypt something that wasn't properly padded.  (Without proper padding their are attacks against multi-block AES encrypted messages).
On encryption, the tool may prepend the ciphertext with a block of a random initialization vector (IV); on decryption doesn't attempt to decrypt the zero-th block assumed to be an IV.   (Without an initialization vector, an eavesdropper can detect when similar starting messages are being sent and potentially tamper with them).
The tool also may include some sort of MAC to verify the data wasn't tampered with that will fail if you attempt to decrypt a plaintext message (as the plaintext message would not have a valid MAC that allows decryption to proceed).

The terms 'decrypt' and 'encrypt' in terms of an encryption routine are simply functions - they run an input past a function to retrieve the original content. Generally, they do the exact opposite - if the encryptor flips a bit up, the decryptor will flip the bit down. The original text doesn't matter.

When you decide to run a 'decryption' routine on any text, it'll run the opposite function on the text - but since your input isn't actually encrypted, you'll probably get a stream of absolute garbage. But again, not the point. If you encrypt this garbage output, you should theoretically be able to retrieve your input.

Tl;dr: Yes. It should be possible.


HMAC with public-private key I need a way to protect my data.

More then encryption I need a way to guarantee integrity and authenticity but I also need to be the only one that can understand integrity and authenticity.

I found HMAC to be a good way for integrity and authenticity but it is based on a single key that I should share within my software and I don't like it.

Is there a something like HMAC but with public-private key so that I can share only one key?

Consider the following system involving a message authentication code like HMAC-SHA256:

Alice generates a key and shares it with Bob, and Bob alone.
Alice authenticates a message with the key.
Bob acts on the message only if it can be verified with the key.

Of course, Alice can verify messages too, and Bob can forge messages too.  Indeed, anyone who has the key can verify or forge messages: the key necessarily grants the power to do both.  Consequently, Alice can't present a cryptographic proof to a third party that a message came from Bob, because Alice could have forged the message; and vice versa.  Thus this system has ‘deniability’, or lacks third-party verifiability.

Consider the following system involving a digital signature scheme like RSASSA-PSS or Ed25519:

Alice generates a key pair and shares the public key with Bob, and Bob alone.
Alice signs a message with her private key.
Bob acts on the message only if it can be verified with Alice's public key.

Only Alice can sign messages; anyone with the public key can verify them but not sign them.  You asked that only Bob be able to verify messages.  Can the public key be kept secret so that Bob alone can verify them?

The standard for signature security is existential unforgeability under adaptive chosen-message attack, or EUF-CMA, which means that an adversary who can query an oracle for the signature of any message of their choice nevertheless can't forge a signature for any message they didn't query the oracle for.  Nothing prevents an EUF-CMA signature scheme from simply including a copy of the public key in the signature itself, so that won't keep Alice's public key secret.

There's a nonstandard property of some public-key cryptosystems called key privacy—formalized for public-key encryption schemes, it means that given two public keys and a ciphertext the adversary can't tell which public key the ciphertext corresponds to.  Of course, this doesn't carry over naturally to signatures because if you had the public keys and message you could just verify the signature.

There's a related notion of anonymous signature schemes, where an adversary presented with two public keys and a signature but not the message can't tell which public key made it, which typical RSA-based signature schemes fail by the German tank problem to the chagrin of the Australian Department of Human Services who hoped it provided privacy it didn't.  Schnorr-type signature schemes in a standard group like Ed25519 do tend to provide anonymity in this sense.

There's another related notion of key indistinguishability (paywall-free) where an adversary presented with two public keys and a signing oracle can't tell whether the public keys have the same private key, but this is in an exotic context where a set of many users can sign messages with their respective private keys, but only one party can distinguish signatures made by the users.

Which of these do you want?  I don't know—it's not clear to me what you're trying to accomplish at a higher level, so it's hard to give more specific advice.

It's standard to encrypt the message digest with the private key - so that the receiver can verify with the public key that the message has not been altered.

What you can do, if you have a secret password in your head, is use your password as the HMAC key when computing the digest.

It's a bad idea, because it means you have to know your private password that only exists in your head in order to do the encryption.