What are the pros/cons of using symmetric crypto vs. hash in a commitment scheme?

My preference would be to use hash for this purpose.
Cons of using symmetric cipher include:

Symmetric cipher keys are shorter than hashes (128-256 bits), where as hashes are longer (160-512 bits).
When considering the length of symmetric cipher output, it is commonly short (like 128 bits). This length is often inadequate to protect against birthday attack and other attacks applicable.
In most uses of symmetric keys, related key attacks are of lesser consideration. However, in this scheme, malicious party could try to use related key attack to find key matching slightly altered message and/or different r. The strongest known related key attacks against AES are $2^{189.7}$ (AES-192) and $2^{99.5}$ (AES-256). These attack complexities are from Wikipedia.

I'm not aware of significant benefit symmetric cipher would provide in this context, except that AES is faster to execute on (many) of recent processors than hashes of the SHA family.


RSA Attack, known public key and ciphertext. Can decrypt the message m?

Some examples of answers to similar questions:

Theoretical decryption of RSA
https://crypto.stackexchange.com/questions/31433/how-to-decrypt-a-rsa-encrypted-text-file-when-only-public-key-is-known

Hint: $N = 217 =\ ?\ \times\ ?$

In the public key, $e$ is the exponent and $N$ is modulus, therefore $e < N$.
If $m$ is your message, $m^e \mod N = c$ is the cipher.
To decipher you need to find $d$, such as: $d \times e = 1 \mod \phi(N)$.
You will then be able to find $m$: $c^d \mod N = m$


What about programming your own library of, let's say AES cipher, in your language of choice?

Implementing AES yourself in a correct way isn't too hard. The specification is well-written, contains illustrations and intermediate test vectors so that essentially anyone can do that.
What is tricky for AES and the reason why it's generally ill-advised to write a production-ready implementation yourself is to write an implementation that is reasonably fast and (/or) resistant to common software CPU side-channels.
If you still want your language to have an AES implementation the usual way to go would be to use the foreign function interface to call into a C-based AES library.
As for implementing AES yourself, if your language compiles to machine code there's usually a way to access intrinsics for AES and with those usually there is little that one could do wrong - apart from not properly allowing the CPU to pipeline the instructions.
If you don't have a machine-code-compiled language and / or your target CPU doesn't have hardware AES instructions things get more tricky. You need to ensure that whatever you write in your language doesn't do some weird things during interpretation / just-in-time compilation to accidentally introduce extra instructions. You need to ensure that the implementation always takes the same amount of time independent of the key and data used. You need to ensure that the previous step is not actually potentially messed up by the interpreter / JIT compiler / CPU. You also need to ensure that your memory access patterns do not depend on secret data. Most of these points can be fixed, e.g. using bitsliced AES implementations, but this is of course far from a trivial task - especially if you want the implementation to be reasonably fast.


Apply visual cryptography to a video stream?

The simplest form of visual cryptography use transparencies that each individually convey no recognizable information, but reveal a meaningful image when precisely aligned

The basic approach for doing the same with video is using such visual cryptography to encipher each frame. That works, but (as stated in the question) requires generating two images for each frame, and playing these in perfect synchronization. Also, the decoding won't be easy: the eye is good at averaging luminous intensity, and projection on an ordinary screen, even if perfertly superimposed, will lack contrast. Further, lossy video compression (as most video compression schemes are) will tend to prevent decoding.

It is tempting to make the image in one of the two video streams still, which in particular allows decoding with fair contrast simply by projecting on a screen that serves as key. But that's very insecure! What's moving in the original video will be distinguishable to the naked eye; and XORing each frame with the previous one will make that even more apparent: the XOR of two consecutive frame in the ciphertext is also the XOR of two consecutive frame in the plaintext, and is very revealing; in particular, that shows the left and right contour of something moving horizontally.

I see no secure fix.


How is this affine function a pair wise independent permutation?

A family of functions F is a pairwise independent permutation if:

Each member of the family is itself a permutation, and
For any fixed $A$, $B$ (with $A \ne B$, and both from the input set of the permutation), and $f$ is a random member from the family $F$, then the pair $f(A), f(B)$ is equidistributed over all distinct pairs from the output range of the function.

In particular, if the size of the output range $2^n$, then for any $C \neq D$, then the probability that both $f(A) = C$ and $f(B) = D$ is $(2^{2n} - 2^n)^{-1}$

By applying the above definition, it is easy to see that the function family $f_{(a,b)}$ meets it; each $f_{(a,b)}$ is a permutation (remember, $a=0$ is prohibited), and if $f$ is a random member of that family, then $f(A), f(B)$ is a equistributed distinct pair; that is, given any pair $C \ne D$, then there is a unique $a$, $b$ with $a\ne 0$ such that $f_{(a,b})(A) = C$ and $f_{(a,b)}(B) = D$.  Each such pair $a, b$ occurs with probability $(2^{2n} - 2^n)^{-1}$, and so we have $f(A) = C$ and $f(B) = D$ holding simultaneously with that same probability.


i know the MAC size but how do i get the other parameters BEFORE even running init?

This is one of the cases where you have to deal with two different expansions of the acronym "MAC": Medium Access Control and Message Authentication Tag. The first two points, ie the MAC address and the MAC frame counter refer to the Media Accesss Control expansion, ie the (link-layer) address of the peer you want to communicate with and the (link-layer) sequence counter of the current message packet. The MAC tag size refers to the actual Message Authentication Code tag of CCM*.

  so in testing it should be random?

This depends on the tests you want to do. In some cases it makes sense to randomize these values, eg if you just test whether encrypt and decryption works. In other cases, eg when you want to test against test vectors, the randomness will not be helpful / will make verification of operationality of the system harder.


I can see at least one big issue with your own scheme: the attacker could cycle through as many counters until one is found that produces the same bits in the hash at the location of the padding bits used for authentication. In that case the authentication would succeed with a different nonce / counter. This problem also disallows additional authenticated data to be added to the scheme. This would be fixed by using HMAC instead of a hash. When validating the padding bits I would use a constant time compare to be on the safe side (I don't see a direct issue, but better safe than sorry).

You need to pad to the end of the block anyway otherwise you cannot XOR with the hashed IV. So you should at least use as many zero bits as possible. For two bytes you have a chance of one in $2^{16}$ that a random message is accepted. That's too large for most cryptographic systems.

So for a fixed sized message you could use 4 bytes minimum, giving you a chance of one in $2^{32}$ - somewhat over 4 billion in the short scale - to accept a random message. Even then it would be a good idea to implement additional ciphertext messages. Your messages would 12 bytes of course, as the AES block size is 16 bytes in size. The larger the padding the better.

Truncating a MAC (over the ciphertext) is common. It has the same problem as validating the padding in your scheme: if you check too few bits then the message may be accepted with a probability that is considered too high. It has the advantage of being secure for variable size messages, at the obvious cost of bits compared to your scheme.

Older triple DES schemes usually use 4 bytes / 32 bits. This could be OK if an authenticated session is broken if a bad packet is received, but remember that sending $2^{32}$ random messages is commonly not out of reach to an attacker.

I'd say that having a 10 byte cipher text (for a 10 byte message, there is no need to use 16 bytes for a 10 byte message) for AES-CTR and a 4 byte MAC is more secure than your proprietary scheme. CCM and EAX are ready made AEAD schemes that could be useful in your situation. They rely just on AES and allow shorter tag sizes without losing too much security, and they allow additional authenticated data as well.

The addition (having the counter and time synced) does make it harder for an attacker to have an invalid message accepted. However, it still doesn't disallow attacks on additional authenticated data that gets hashed. It should be noted that keeping a nonce and the time synchronized can be a deceptively hard problem. An attacker is often capable of power cycling devices, slowing down clocks etc.


The interaction between the malicious Adversary and the Simulator and Real-Ideal' views

Without meaning any offense to the authors, this proof could perhaps have been written a bit more clearly; probably, since this is a fairly minor result, they didn't expend too much effort on it. Here is a longer but hopefully clearer rewording which should clear your terminological confusion.

Corrupted $P_1$

The real-world adversary $\mathcal A$ corrupting $P_1$ has input $x$ and auxiliary input $z$. It sends some value $x'$ to $P_2$ and outputs some value $x''$; both $x'$ and $x''$ are computed from $x$ and $z$. Since $P_2$ is honest, it computes and outputs $x' \wedge y$, for its received value $x'$ and input $y$, as instructed by the protocol; the output pair is $(x'', x' \wedge y)$.

The ideal-world adversary $\mathcal S$ (aka the simulator) again has input $x$ and auxiliary input $z$; it first computes $x'$ and $x''$ from $x$ and $z$ just like $\mathcal A$ does*. It then sends (or instructs $P_1$ to send) $x'$ to the trusted party; the honest $P_2$ sends $y$. The trusted party returns $\varepsilon$ (the empty string) to $\mathcal S$ and $x' \wedge y$ to $P_2$. $\mathcal S$ outputs $x''$ and $P_2$ outputs $x' \wedge y$; the simulation is perfect.

Corrupted $P_2$

The real-world adversary $\mathcal A$ corrupting $P_2$ has input $y$ and auxiliary input $z$. It receives $P_1$'s input $x$ and outputs some value $y'$ computed from $x$, $y$ and $z$. Since $P_1$ is honest, it outputs $\varepsilon$ as instructed by the protocol; the output pair is $(\varepsilon, y')$.

The simulator $\mathcal S$ again has input $y$ and auxiliary input $z$; it sends $1$ to the trusted party, and the honest $P_1$ sends $x$. The trusted party returns $\varepsilon$ to $P_1$ and $x \wedge 1 = x$ to $\mathcal S$. The honest $P_1$ outputs $\varepsilon$, and $\mathcal S$ computes and outputs $y'$ just like $\mathcal A$ does; the simulation is perfect.

* This is basically what they mean by "$\mathcal S$ receives [...] from $\mathcal A$." You could consider that $\mathcal S$ is given black-box or oracle access to $\mathcal A$: it sends $\mathcal A$ the values $x$ and $z$ and $\mathcal A$ returns $x'$ and $x''$ like it does in the real world. It's a bit awkward, however, because such black-box/oracle access has not been defined at this point in the book, and in particular does not appear in the security definitions.


DH with AES - is that an acceptable security scheme over UPnP?

No. First, you've exposed a padding oracle by using unauthenticated AES. Secondly, you've not authenticated the devices: it's easy to mount a man in the middle attack. Thirdly, I don't understand the role of changing parameters all the time in your protocol.


Is there a standard format for compact 56-bit DES keys?

The one time I've seen a system compress a DES key into 7 bytes, it did it by logically placing the 8 bytes of the standard DES key into an 8x8 table, and then flipping the table along the diagonal axis, so that bit x of byte y of the standard DES key was mapped to bit 7-y of byte 7-x of the compressed key. For example, the first byte of the compressed key consisted of the msbits of all 8 bytes, and the second byte of the compressed key consisted of bit 6 of all 8 bytes, etc.  This moved all the lsbits of each byte into the last byte, which was discarded.

However, I don't believe this was, in any way, standard; it just happened to be what the system I saw did.  This particular transform does have the advantage that the same routine can convert both directions between the standard DES format and the compressed format (that has all the ignored bits in the last byte).


Some confusions about Repeated Doubling Algorithm?

This algorithm is a small optimization to Algorithm 3.21 of the same book on page 91. Algorithm 3.21 is the original algorithm for computing elliptic curve doubling using Jacobian coordinates (with $a=-3$). If you have a close look at both of the algorithms, you will notice many similarities. For example, Algorithm 3.21 computes $A \leftarrow 3(X_1-Z_1^2)(X_1+Z_1^2)$, whereas Algorithm 3.23 computes $A \leftarrow 3(X^2-W)$ (note that $W=Z^4$!). Therefore I would suggestion breaking problem (1) down into two parts:

For $m=1$ prove that Algorithm 3.23 computes the same thing as Algorithm 3.21. Since we are using Jacobian coordinates, this means showing that $X_3/Z_3^2=X/Z^2$ and $Y_3/Z_3^3=(Y/2)/Z^3$ (using the notation of the respective algorithms, and of course with equal input).
Use induction to prove the result for $m>1$.

I am not sure whether I understand part (2) of your question correctly. The statement $2Y$ for $4P$ is not really well-defined. Since we are working with projective coordinates (Jacobian), what you would probably want to check is whether we are computing a $X,Y,Z$ such that $4P=(X/Z^2 : (Y/2)/Z^3: 1)$. Since the first part of your question proves that the algorithm correctly computes $2^mP$ for any $m>1$, the second statement follows by applying the definition of Jacobian coordinates to Line 4 of Algorithm 3.21.


Are all self-synchronizing cryptosystems necessarily self-synchronizing stream ciphers?

Your best bet is to use an error-correcting code to correct the errors on the ciphertext.

In general, accepting corrupted ciphertexts is a bad idea, because it can allow devastating chosen-ciphertext attacks and because unauthenticated encryption has caused major security holes in practice.

When proper authentication is in use (which should be always), any error will result in the entire message being rejected.  There are   two solutions:

Break the message into chunks, such that bad chunks can be detected and retransmitted.
Use error-correcting codes.  These allow for errors to be corrected by introducing redundancy.

These can be combined.


Yes, since $N=p
\times q$, so we have $13029506445953503759481 = 109217267039×119298960679$,
also the private and public exponent $e$ and $d$ are related by the equation $ed\equiv1\text{ mod }\phi(N)\equiv1\text{ mod }((109217267039-1)×(119298960679-1)) $.
You should then be able to find $d$, the private exponent.


Would it be useful for companies who need to keep their data safe?

No, a one-time-pad is only useful in very rare circumstances.

The main issue is key-management. You can only use each pad once, it's as large as the data you want to encrypt, and you need to get it to all parties in a secure way.

The direct competition of a one-time-pad is a stream cipher. They don't come with a proof of security, but are much easier to use, since they only have a small key(32 bytes or so) instead of a giant pad. Thanks to IVs the key reuse problem is much smaller too, you just need locally generate a random value of around 16 bytes.
Would the files encrypted with our "product" be safe?

If you manage to do everything correctly, yes. But the key management is so annoying that mistakes such as pad reuse are likely, and it's not solving a practical problem. So nobody will use it.
Can we "outperform" their product?

Hardware PRNGs are not that useful on desktop systems, since those tend to have sufficient entropy sources to seed a PRNG. Embedded systems which often suffer from entropy issues on the other hand typically can't afford a specialized HRNG module.

Intel is also working on putting a HRNG into their CPUs, making it practically free. You can't compete against that.


Can insecure algorithms be combined to form a secure algorithm?

At the time of answering, the question was can insecure algorithms be combined to form a secure algorithm?

Yes: Think of any secure round-based block cipher. The independent rounds are not secure, but put together the overall cipher is. I think my favourite example is (currently) the Even Mansour cipher,
which combines two xor operations and one unkeyed permutation to form a secure cipher.

 nb: I know this isn't a direct link, but its the best introduction I know of

For a good discussion of the hash example in your question, read this question.


How to make an AES implementation using lookup tables immune to cache timing attacks?

When it's possible, a solution is to ensure that table lookups at data-dependent addresses are constant-time and without action on the cache, by

Disabling cache (use and loading/invalidation) during such table lookups. That's heavily system dependent, though. Some CPU architecture have special instructions, addressing modes, or mode bits allowing this, or allow to control which addresses can be cached.
And ensuring that there is no other condition causing timing variations in table lookup; I'm in particular thinking of an extra cycle due to internal carry in the addition of base address and index on some CPUs. On many 8-bit CPUs, that means starting the 256-byte table at an address multiple of 256.

It is not quite as safe to:

Flush cache before table lookup, because in some attack scenarios an adversary could examine the cache state.
Fill cache with the full table before use, because in some attack scenarios an adversary or a coincidence could partially flush the cache.

Other techniques aim at making it impossible to measure timing dependencies. For example, we may start a timer before encryption, set to a larger value than the worst-case encryption duration, then wait precisely until expiry of the timer after encryption. With a cycle-accurate timer, and if an adversary can not induce interrupts that make the duration of the encryption vary beyond the maximum forecast, and a host of other conditions, it is conceivable that timing variations in encryption are fully hidden. Beware that this could worsen leaks by other side channels (power, electromagnetic emissions).

None of this is general and portable. Other solutions have no such drawback: they just use no table lookups at data-dependent indexes, replacing them by constant-time expressions or table tookups at data-independent adresses. That can be made portable and reasonably fast when using bitslicing; see answers to this related question.

If speed is not an issue, a slow but simple and quite portable technique goes:

uint8_t lookup(const uint8_t table[256], uint8_t index) {
    unsigned j, r;
    j = r = 255;
    do
        r ^= ((-(index ^ j)) >> 8) | table[j];
    while(j--);
    return (uint8_t)r;
}

This works because -(index ^ j) has bits 8 to 15 each 0 or 1 depending on if  index==j or not, and the indexes in table[j] are not data-dependent.It might be necessary to inhibit a spurious compiler warning or/by inserting 0 before -.

It is also possible to use that (c >> j) & 1 does a lookup at index j in a $k$-entries 1-bit table defined by $k$-bit constant c, in a constant-time manner on CPUs with an at-least-$k$-bit barrel shifter and a compiler that uses it. That combines with the above: we can select among 32 constants each 64-bit according to 5 bits of the index (perhaps unrolling the loop), then use a 64-bit barrel-shifter to extract the 8-bit result according to the remaining 3 bits of the index.


Is this block encryption scheme using PCBC for RSA secure?

Is there any issue resulting from using that with RSA instead of a symmetric cipher?

The difference - with regards to security - between symmetric and asymmetric encryption is that anybody is supposed to have the public key for asymmetric encryption, including the attacker. This has to be taken into account when generating a mode of operation for RSA.

  Assuming that RSA is as secure as BlockCipher XYZ, will this give the same security as PCBC used with XYZ?

Nope. Assume that the first plaintext block is zero. Then the IV (initial chaining value) is encrypted twice in this scheme. As modular exponentiation itself is deterministic, this will result in repetition within the ciphertext. This repetition will show that the plaintext block is zero, thus leaking information to an attacker.

That's a fundamental break in CPA security. There may be other issues, but this is enough to declare the scheme to be broken when used as direct replacement of CBC or PCBC with a symmetric cipher.


Security properties of an encryption scheme built from a PRP and a PRG

Fourth, I think $E(k,m)$ is CCA-Secure too, right?

Consider this: what if an attacker takes a valid ciphertext $E(k,m) = ( P(k,r) , G(r) \oplus m )$ and flips a bit, so that it is $P(k, r), G(r) \oplus m \oplus 1$.  What would happen if you gave this altered ciphertext to the decryptor?


Do garbled circuits run in constant time?

No, this is not needed in general, for Garbled circuits are not meant to be reused (notice that while most are not, there is some research looking into reusable GC, but not much).

Furthermore, if you are using shuffled garbled truth tables, as you should, then timing discrepancies do not leak any useful information, as long as you do not reuse the circuit.


Symmetric property of DDT of inverse function

The proof for DDT is shown as following:

given:
$$y=F(x) ;\\ x=F^{-1}(y) \> \> (1) $$
The forward DDT is
$$F(x) + F(x+\alpha) = \beta \>\> (2)$$
substituting (1) into (2)
$$F(x) + F(F^{-1}(y)+\alpha) = \beta  $$

$$y+ \beta +F(F^{-1}(y)+\alpha) =0$$

re-arranging and applying inverse function
$$F^{-1}(y+ \beta) +F^{-1}((F(F^{-1}(y)+\alpha))=0 $$

$$F^{-1}(y+ \beta) +F^{-1}(y) = \alpha$$

Therefore ,

$$DDT_{F^{-1}}(\beta, \alpha) = \delta_{F^{-1}}(\beta, \alpha) = |\{ x \in \mathbb{F}_2^n | F^{-1}(x) + F^{-1}(x+\beta) = \alpha  \}|$$

The same concept applied to LAT proof.


Factorizing a handiwork number $n$ in two prime factors

The number you constructed is somewhat vulnerable to Pollard's p-1 method. If $r_0$ and $s_0$ are 64 bit long primes, then these are the largest factors in $p-1$ and $q-1$. The method works when $p-1$ (or $q-1$) is powersmooth for some "small" $B$ (choosing $B$ as $64$ bit number isn't that practical - the expected runtime of the algorithm is $O(\log^2(n)B \log(B))$).

In your question you wrote $r_0$ and $s_0$ have less than $64$ bit. If it is actually much smaller, the $p-1$ method will become viable.

Regarding the numbers in the comment: Those are $6\cdot 64 = 384$ bit primes? That is not an acceptable length for RSA - if that was your intention. According to the latest recommendation on keylength.com, today's fatoring moduli should have $2000$ bits at least, meaning you need primes with $1000$ bit each.


If we call $U_k$ the random variable uniformly distributed over bit strings of length $k$, then a function $g: \{0,1\}^k \to \{0,1\}^m$ is called pseudo-random generator if no feasible(poly-time if you want) algorithm can distinguish $g(U_k)$ and $U_m$ with non-negligible probability.

More formally let $U'_m = g(U_k)$ then the distinguishing advantage of any distinguisher efficient $D$ that we denote as $\Delta^D(U'_m, U_m) = Pr^{DU_m}[Z = 1] - Pr^{DU'_m}[Z = 1]$ is negligible.

Here $Z$ is the output of the distinguisher, and negligible is any suitable notion of "really small"; same for efficient.


When are hash functions considered insecure?

The security level of a cryptographic hash function has been defined using the following properties:

Pre-image resistance

Given a hash value $h$ it should be difficult to find any message $m$ such that $h = hash(m)$. This concept is related to that of one-way function. Functions that lack this property are vulnerable to preimage attacks.

Second pre-image resistance

Given an input $m_1$ it should be difficult to find different input $m_2$ such that $hash(m_1) = hash(m_2)$. Functions that lack this property are vulnerable to second-preimage attacks.

Collision resistance

It should be difficult to find two different messages $m_1$ and $m_2$ such that $hash(m_1) = hash(m_2)$. Such a pair is called a cryptographic hash collision. This property is sometimes referred to as strong collision resistance. It requires a hash value at least twice as long as that required for preimage-resistance; otherwise collisions may be found by a birthday attack.
More details are in here.


Diffie-Hellman Key Exchange attack on small secret keys

(in DH) Bob used a small secret key that can be brute-forced.

If the private key is $k$-bit, a meet in the middle attack allows private key recovery with cost $O(2^{k/2})$ group operations (here, multiplication in the modulo $p$ group $\Bbb Z_p^*$).

In its simplest form: we know Bob's public key $y=g^x\bmod p$ and want the $k$-bit $x$. We choose $a$ with $\log_2(a)\lesssim k/2$, compute and enter in a hash table the $a$ values $y\;g^{-a\;i}\bmod p$ with $0\le i<a$ and the corresponding $i$ (each additional value is computed with a single multiplication modulo $p$ by $g^{-a}$). Then we search in this table the $g^j\bmod p$ with $0<j\le2^k/a$. When we have a match, $x=a\;i+j$.

There are various optimizations: we can make the table more compact by perusing the near uniform distribution of the values in the hash table, truncate these values to below $k$ bits and filter out any false positives. For more time/memory tradeoffs see Paul C. van Oorschot and Michael J. Wiener, Parallel Collision Search with Cryptanalytic Applications, in Journal of Cryptology, 1999.

Update: but now that I have seen the linked files, this general method (while working) is way overkill.

We have Bob's public key (or "contribution") $y$ that is much shorter than $p$ is, and $g=3$. The simplest way (and in fact, the only known way for a good choice of $p$) to have such a small $y$ is that $x$ is very, very small and $g^x\bmod p$ is $g^x$. We thus we want to check if $y=g^x$ has a solution $x$ in $\Bbb N$ (hint: take an approximation of the logarithm on both sides to get an approximation of $x$, then check that guess). If we get Bob's secret $x$, then we can proceed the way he did to decipher the flag.


Here is the problem. For a specific ciphertext, sure you could try a bunch of keys and output the couple that result in the type of plaintext you want. But what does this really get you? For a different ciphertext, likely these same keys will not result in the same type of plaintext you desire.

Recent work on honey encryption might be what you are really looking for. It is still very new, so it should not be used in a production system without understanding all the intricacies. The authors of the paper also provide some nice theoretical foundation for the area.


Cryptographically secure linear congruential generator - is it possible?

Public m private a,c
If the attacker gets some $x_i$ in sequential
\begin{align}
x_{i+1} &= a \cdot x_{i} + c &\bmod m\\
x_{i+2} &= a \cdot x_{i+1} + c &\bmod m\\
\end{align}
Then subtracts the two
$$x_{i+1} - x_{i+2} = a ( x_{i} - x_{i+1})  \bmod m$$
this will lead to the exposition of the $a$, the rest is there.
In short the next-bit test is failed.

By the way what will happen if we will not?

No maximal period!
Private m,a,c
The attacker still can recover the $m$ then the rest as following D.W.'s steps;
Define a new sequence $t_n = x_{n+1} - x_{n}$ and with some operation;
$$t_{n+1} = x_{n+2} - x_{n+1} = a x_{n+1} + b - a x_{n} -b = a x_{n+1} - a x_{n} = a t_{n} \bmod m$$
So we have $t_{n+1} = a\cdot t_{n} \bmod n$, then we have $t_{n+2} = a^2\cdot t_{n} \bmod n$ and $t_{n+i} = a^{i}\cdot t_{n} \bmod n$. From this one can notice that $$t_{n+2}\cdot t_n - t_{n+1}^2 = 0 \bmod m,$$ i.e. $|t_{n+2}\cdot t_n - t_{n+1}^2|$ is a multiple of $m$
Now call $U_n = |t_{n+2}\cdot t_n - t_{n+1}^2|$ and consider $\gcd(U_i,U_j)$ where $i \neq j$
Now, we will use a fact that Dirichlet showed in 1849

The probability of two random numbers being relatively prime is $\frac{6}{\pi^2}$

Consider two multiples $k$ and $\ell$ of $m$, then there are $u$ and $v$ such that $k = u \cdot m$  and $\ell = v \cdot m$. This will turn the question of $\gcd(k,\ell) = m$ to $\gcd(u,v)=1$ and this is the Dirichlet's result. If you are lucky with 5 outputs from LCG to from two $U_i$ than with $\frac{6}{\pi^2} = 0.607927101854027$ you will find $m$. If you have more output, you can calculate $\gcd(U_i,U_j,...,U_r)$ to increase to finding probability close to 1.


Generating a strong unique Initialization Vector

"Unique" is relatively straight forward. It's something you haven't used before. Unique usually only applies to the individual party, you only need to verify that the IV is unique for your usage with the current key.

"Strong" relates to the requirements that your mode of operation has for the IV. Different modes require different constraints on the IV. Which ties in with...

The "scientific explanation" for a good IV comes from a security proof reduction. Researchers design a scheme (like a mode of operation, such as CBC) that uses a cryptographic primitive (like a block cipher, such as AES) that requires an IV, then they prove (or at least argue) that the scheme using the IV is as secure as the underlying primitive given certain constraints on the IV. In other words, if the scheme can be broken it isn't due to the IV as the IV's requirements makes the scheme no weaker. This principle applies to every form of IV, be it for a stream cipher or block cipher. Those constraints on the IV are the strong IV values you should use.

For example, CBC mode for block ciphers requires that the IV be unpredictable. So commonly it is either a) random or b) a unique value encrypted by a key. (The two most common IV requirements are that it be random or unique.) CBC has a proof of security that says that if one of those criteria for the IV are met, then the resulting scheme is as strong as the underlying block cipher.

How do you verify the IV is good? You should put your analysis into the process that does generate the IV, then you can test the IV after it is generated. The main focus should go on how the IV is generated and verifying it conforms to the specification's requirements.

For example: the requirement you are satisfying may be that the IV be random. You might use the high-quality native random number generator from the operating system (/dev/random, CryptGenRandom, etc) to do so. You can do some tests on the output to verify that something obvious hasn't gone wrong, like the IV doesn't fail to all zeros. But you can't verify that the IV is actually random, only that it looks sufficiently random. Verifying that something random or indistinguishable from random is really hard to do in real-time.
Another example: the requirement you satisfying may be that the IV be unique. You can use a counter that increments every time an IV is generated and ensure that the counter has a sufficient size that it won't roll over too soon. Or you can use a timestamp and take care to ensure you don't generate multiple IVs within the resolution period of the timestamp. If you want to be very careful, you can keep a list of all previously used IVs and check the list for each new one to ensure you aren't re-using it.

The summary is: Cryptography researchers say that certain schemes are secure given constraints on the IV. These constraints will be widely known and should be available for you to find.


How to prove in zero-knowledge that the attributes of Pointcheval Sanders signature is the opening of a commitment?

Quoting the proposal page 10, just before Theorem 8:

..and carries out a zero-knowledge proof of knowledge $\pi$
(such as the Schnorr’s interactive protocol [Sch90]) of $(m_1, . . . , m_r)$ and $t$ such that..

That means introducing protocol responses $(M_1, \cdots, M_r, T)$
for secrets $(m_1, . . . , m_r)$ and challenge $c$
like $M_i = m_i \cdot c + \xi_i$.
Combine responses above and commitment components for Schnorr verification equations.


Is there a way to easily encode a message without a computer on either end?

Most of the classical crypto algorithms used in the pre computer era can be doable with pen and paper!! Lot of there are in the list see here http://practicalcryptography.com/ciphers/classical-era/ . Try Vigenere and change you keys frequently.


How can I send a secure public message using ECC?

In this case, the private key will be included in the site code and anyone can read it.

No, the private key is not in the "site" code, it is not send. It is just used to authenticate the TLS session, by placing a signature that can be verified with the public key in the X.509 certificate. This certificate has been exchanged before in the handshake and it has been verified & validated in the browser. The private key must be kept private, as the name implies.

  How can I send a secret message encoded with a key (key1) and only able to be decoded with another secret key (key2), which I only know it, (using ECDSA).

The ECDSA encryption method cannot be used to encrypt messages to keep them confidential. But it can authenticate the handshake. This handshake establishes the session keys, commonly by performing (EC)DH key agreement using two temporary (ephemeral) key pairs generated both by the client and server. These symmetric session keys can then be used to protect the messages.

If you want to perform encryption with Elliptic Curves then you should have a look at the Elliptic Curve Integrated Encryption Scheme or ECIES.

Minimal description of ECIES

For ECIES the sender generates an message specific EC key pair.

The sender then performs key agreement with the generated private key and the (trusted) public key of the receiver. The sender then uses the resulting key material for normal symmetric encryption. The message specific private key of the sender can be discarded after the symmetric key has been derived; it is just needed to calculate the symmetric key once.

The established symmetric key can be used with any block cipher mode of operation - or indeed with a stream cipher to create the ciphertext. It would of course be a good idea to use authenticated encryption to do this. The message specific public key and ciphertext can be combined and send to the receiver.

The receiver then performs his own key agreement with the receivers static private key and the senders message specific public key. This should derive the same symmetric key, which can finally be used to decrypt the ciphertext.


You can try to encrypt your sensitive data with a lightweight cipher, like Prince. You encrypt your Prince key with a HE encryption scheme like BGV (HElib implements it) and give the cloud two things: Enc_HE(Key_Prince), Enc_PRINCE(Data). The cloud is able to decrypt homomorphically Enc_PRINCE(Data) using Enc_HE(Key_Prince) and obtain only Enc_HE(Data). The cloud can now perform unlimited computations on encrypted data. Your Key_Prince will not be found. You can find more about this scenario in: Toward Practical Homomorphic Evaluation of Block Ciphers Using Prince and Homomorphic Evaluation of the AES Circuit. HElib can be hard to use, do you might instead try a more friendly library, SEAL. But if you want to do only additions or only multiplications, there are more practicals schemes than fully homomorphic ones.


What is the difference between uniformly and at random in crypto definitions?

If you sample a random element, then you sample it according to some distribution.

Uniformly then means that you sample from the uniform distribution, i.e., you sample it from a set where drawing each element is equally probable. Let us assume you have a set of 4 elements, then sampling uniformly at random from this set, every element is drawn with probability 1/4.

However, you could also sample a random element according to some other distribution, e.g., say two elements have probability 1/3 to be drawn and the remaining elements have probability 1/6 each.


You will have to find $d \in \mathbb{Z}_{\varphi(y)}: x * d
 \equiv 1 (mod\ \varphi(y))$. Then $rem^d=a^{xd}=a^1$ (Euler's theorem) in $\mathbb{Z}_{y}$. To do so you will need to calculate the prime decomposition of $y$ so you can calculate the value of Euler's phi ($\varphi$) in $y$. Then the problem of finding $d$ reduces to the problem of finding inverse (extended Euclidian algorithm on the power and the modulus -- find $a,b$ such that $1=GCD(x,\varphi(y))=ax+b\varphi(y)\equiv ax (mod\ \varphi(y))$). Note that the inverse does not exist if $GCD(x,\varphi(y))\neq1$.

E.g. in RSA the public key ($e$ that corresponds to your $x$) has an inverse ($d$) computed during the key generation and the inverse is then stored in the private key.


Finding exponent $e$ in RSA given modulus and a plaintext/ciphertext pair

In this question we are given $c$, $m$ and $n$ (32 bit integers with $0\le c<n$), and asked to find the exponent $e$ (also 32 bit integer, odd and at least $3$) matching the equation of textbook RSA encryption: $c=m^e\bmod n$.

That's impossible with certainty unless $n$ is prime (which would not be RSA) and exactly 32-bit, because then the solution is never unique; either there is no solution, or several values of $e$ are possible. For some parameters (like $m=c=0$, $m=c=1$, or $m=c=n-1$), all odd values of $e$ work. If there's a solution, there is one below $\lambda(n)$ with $\lambda(n)=\operatorname{lcm}(p-1,q-1)$ when $n=p\;q$ with $p$ and $q$ distinct primes; that's the Carmichael function, and is less than $2^{31}$ in an RSA context when $n$ is an at-most-32-bit composite; and then $e+\lambda(n)$ will be at-most-32-bit and also be a solution.

What we can find is the lowest odd value of $e$ at least $3$ such that $c=m^e\bmod n$ holds. The simplest method is perfectly adequate in the context if we can use a computer:

$a\gets m\cdot m\bmod n$
$e\gets 1$
$b\gets m$; it holds that $b=m^e\bmod n$
repeat until $e=2^{32}-1$

$e\gets e+2$
$b\gets a\cdot b\bmod n$; again it holds that $b=m^e\bmod n$
if $c=b$

output "One solution is" $e$ and stop

output "There is no solution" and stop.

This requires $(e+1)/2$ modular multiplications if a solution is found, and  in any case no more than $2^{31}$.

There are at least two independent speedups which would allows to reduce the work, or/and tackle larger parameters:

There are better algorithms than exhaustive search to solve a Discrete Logarithm Problem, including baby-step/giant-step which reduces the work to $O(\sqrt n)$ modular multiplications; and Pollard's rho which is simpler and tends to be faster on average (but won't necessarily give the lowest $e$).
If we can factor $n$ (and it is square- free as customary in RSA), then we can solve the equation $c\equiv m^{e_p}\pmod p$ for each prime factor $p$ of $n$, then combine the results into $e$ using the Chinese Remainder Theorem, noting that if $e\equiv e_p\pmod{p-1}$ for each prime $p$ dividing $n$, this $e$ will be a solution (there might be cases where we miss the lowest $e$).


Does the SHA-256 sum of a 256-bit key help you crack it?

The practical answer is "not really". With that said, here's a more nuanced answer:

If you only have a single AES-256 plaintext/ciphertext pair (one block, that is), it's not actually possible to bruteforce the key. AES has a block size of 128 bits, so the probability of any given key having that plaintext/ciphertext pair should be $2^{-128}$. That number is quite small, except for the fact that there are $2^{256}$ possible AES-256 keys, so there should be about $2^{128}$ keys with this plaintext/ciphertext pair. In other words, even a bruteforce search would still leave us with about $2^{128}$ possible keys. With access to a SHA-256 hash of the key, we can instead search for a preimage of the hash, which should leave at most a few possible keys (those keys can then be checked against the AES plaintext/ciphertext pair).

So, in theory, the hash should help an attacker in the above situation. Of course, in practice, it's impossible to search a key space of $2^{128}$, let alone $2^{256}$, so the above has no practical implications.

A more interesting question is whether an attacker who knows both $\text{SHA-256}(k)$ and $(m,E_\text{AES-256}(k, m))$ can combine that knowledge in order to use some more efficient method.

Here's an example of how this kind of problem could happen. Suppose we have two secure cryptographic hash functions $f$ and $g$, each operating on 256-bit inputs and producing a 256-bit output. Let $f(m) = \text{SHA-256}(m)$ and $g(m) = f(m) \oplus m$ (where $\oplus$ is XOR). I haven't checked this example carefully, but $g$ should still be preimage resistant. If an attacker is given either $f(k)$ or $g(k)$, then they should be unable to determine $k$ without a brute force search. However, if the attacker is given both $f(k)$ and $g(k)$, then they can compute $f(k) \oplus g(k) = f(k) \oplus f(k) \oplus k = k$ to recover the original input.

As far as we know, there aren't any interactions like this between SHA-256 and AES-256. This kind of situation definitely deserves caution, since as far as I know, the algorithms were not explicitly designed to avoid interaction between the two. That said, there does seem to be a fair amount of confidence that there will not be any surprising relationships discovered between AES-256 and SHA-256.

In most cases, it's better to derive separate keys for separate uses. Instead of using $k$ directly, use $k$ to compute two subkeys $k_1$ (for AES-256) and $k_2$ (for SHA-256). There are a variety of ways to do this. My favourite is to use HKDF (that RFC is surprisingly readable), which might look like this:

$k_1 = \text{HKDF-Expand}(k, \text{0x01}, 32) \\
k_2 = \text{HKDF-Expand}(k, \text{0x02}, 32)$


NewHope and NIST's Post-quantum standardization

From Status Report on the Second Round of the NIST Post-Quantum Cryptography Standardization Process

3.12 NewHope
NewHope is a KEM based on the presumed hardness of the RLWE problem. At its core is Regev’s original idea for public-key encryption from plain LWE but specialized to a power-of-2 cyclotomic ring structure, enabling smaller ciphertext and key sizes as well as fast computations via NTT. CCA security is achieved by a standard flavor of Fujisaki-Okamoto transform and is supported by proofs in the classical and quantum random oracle models. Among all LWE-based lattice submissions, NewHope (and other RLWE schemes) can be viewed as the most structured, with MLWE being an intermediately structured case and plain LWE being the least structured
case. As a result of this structure, the scheme has very strong performance for nearly all applications.
In a technical sense, the security of NewHope is never better than that of KYBER. A recent paper gives a highly parameterizable, essentially linear-time reduction from RLWE to MLWE
. If that reduction is specialized to the case of NewHope, one finds the following: the reduction takes RLWE instances and outputs an MLWE instance; it is modulus-preserving; it is “almost” sample-preserving; it is error distribution-preserving; and it translates the ring dimension for RLWE into the product of ring-dimension times module-rank for MLWE. As
such, any attack against an underlying MLWE instance implies a bstantially similar-cost attack against NewHope’s underlying RLWE instance. There are a few minor caveats. However, NIST does not expect that these issues will substantially change the relative concrete security situation of NewHope and an MLWE scheme (like KYBER) that is indicated by the presence of such a tight and efficient reduction.
Further, NIST observed that the CoreSVP strength estimates of NewHope and KYBER are substantially comparable, and KYBER was slightly more efficient in most benchmarks [1] <a href="https://csrc.nist.gov/CSRC/media/Presentations/pqm4-testing-and-benchmarking-nist-pqc-on-arm-cort/images-media/kannwischer-session-9-paper-pqc2019.pdf" rel="nofollow noreferrer" title="pqm4: Testing and Benchmarking NIST PQC
on ARM Cortex-M4">[2]. Specifically because of the relaxation in algebraic structure, KYBER naturally supports a category 3 security strength parameter set, whereas NewHope does not.
Despite the numerous strengths of the NewHope KEM proposal, NIST developed a slight but clear preference for KYBER and for low-rank MLWE schemes over RLWE schemes for the KEM application setting. Therefore, NIST did not select NewHope to continue into the third round (Bolds and links are mine, except the recent paper link that was original)

Like the AES selection, the performance is an important metric when the cipher suites are close to each other or passing the required bounds.
For the categories see this answer, or the NIST original page on Post-Quantum Cryptography: Security (Evaluation Criteria)


How much entropy is lost if 1 character is fixed in HMAC SHA-512?

I'll assume the hash function is "good", i.e., equidistributed and partial-preimage-resistant.

If the input length $n$ is fixed and you fix $k$ bits of the output hash, you're losing roughly $k$ bits of information-theoretical entropy. This is easy to see: Without constraining the output, the entropy is $n$ bits, but forcing the value of $k$ bits means throwing away (on average) all but one out of $2^k$ of those preimages, therefore the resulting value is really sampled from (roughly) $2^{n-k}$ inputs rather than $2^n$.

However, computationally, this doesn't matter: Unless the hash function is severely broken, an attacker trying to recover your secret cannot "carve out" the subset of inputs whose hash values satisfy a specific constraint. (Note: If this were possible, they could just do it for any instance, not just one where you brute-forced those bits!)
Thus, the computational search space for an attacker is still $2^n$ instead of $2^{n-k}$, since they have to use basically the same method as you did.

These considerations are related to the conjecture that Bitcoin works and an indication that vanity keys such as Facebook's Tor Hidden Service address facebookcorewwwi.onion are not insecure even though their private key contains (information-theoretically) less entropy than other keys.


If the key is always the same and there is no IV (or fixed IV), then

$$plaintext1 \oplus ciphertext1 \oplus ciphertext2 = plaintext2$$


Table construction would require 148 Exabytes of RAM, so it would be hard to store all at once.  This also means that you can't have a predefined S box that you might have developed either to be a random permutation, or used some sort of hill climbing technique to be better than random.  You can however have a computed S box function. So it would not be a simple look up table, but rather the 64 bit output would be calculated piecemeal (byte by byte) based upon the 64 bit input.  As long as the function was bijective and not surjective, you'd have S box behaviour.

So instead of a large table, you'd have a mathematical function.  Without resorting to finite fields, the function could be a simple non cryptographic hash of the 64 bits /8 bytes.  One implementation would be a Pearson hash of the 8 bytes, with a unique 256 byte permutation table for each byte position.  That means you require 2048 bytes of RAM instead. Less than perfect non linearity could be compensated for with additional rounds, as is done in some current lightweight algoriths.

Note.  You'd need a similar function for the permutation layer of your cipher as you wouldn't be able to store that easily either.


How to compute the attacker's probability?

The probability of recovering the string $R$ is the same with both of your scheme. The reason is that your second scheme can be separated into two independent parts. In the first part, you just transform $R$ into $R'$ using only your step 1 (this is invertible and from $R'$ you can recover $R$).

In the second part, you just encrypt $R'$ with the previous scheme. As a consequence, the probability of recovering $R'$ is the same as in the first scheme and due to the invertibility of the first part, this is equivalent to recovering $R$.

I am wondering about why you want to use this scheme. Did you consider (in your context) attacks that would approximate $R$ instead of predicting it exactly ? I ask this because this would greatly increase the probability of success.


Recovering 3 private keys if Eve knows that the keys are shared prime numbers and knows their public keys, How would this be done?

Yes, your thinking is correct! Using a "shared prime" when calculating $n_A$ and $n_B$ is disastrous for security simply through the fact that it reveals $p$, $q$, and $r$ with a few calls to the $gcd$ algorithm.

Luckily this incredibly unlikely to happen with the use of good randomness. In the case of 512-bit RSA, there are roughly $2^{503}$ 512-bit primes which, when using the birthday bound, equates to about $\sqrt[2][2*2^{503}log(1/(1-0.5)] \approx 6.02520 * 10^{75}$ generated primes needed to achieve a 50% probability of a collision.

Source: http://www.loyalty.org/~schoen/rsa/


For H1=H2 there are one-way functions with that property: $y = g^x \mod p$.

$ (g^{k_1})^{k_2} = g^{k_1 \cdot k_2} = (g^{k_2})^{k_1}$

This property is exploited by the Diffie-Hellman key exchange. One variation of DH used for password based authentication is SRP.

I strongly recommend to use an existing protocol, and not write your own. Implementing SRP is quite easy to get wrong. I'd just use SSL, either with a normal suite (such as ECDHE_RSA) sending the password in plain over that connection, or using a SRP suite(only supported by a few libs, such as GnuTLS).


Combining fgrieu's and my observation, it appears that a large $r$ can be recovered given enough $p_iq_i + r$ values.

In particular, we will assume that both $p_i$ and $q_i$ are selected uniformly.

Then, $(p_iq_i + r) = r \pmod s$ will hold will probability at least $(2s-1)/s^2 \approx 2/s$ (as it will hold if either $p_i$ or $q_i$ is 0 modulo $s$, $(p_iq_i + r) \bmod s$ will be any other specific values with probability circa $1/s$.  Actually, the bias is even stronger if $s$ is a power of a smaller prime, we'll ignore that for now.

Hence, what we can do is, for various small prime-power $s$, take our $p_iq_i + r$ values, and compute $p_iq_i + r \bmod s$, and see what value happens the most often.  That'll give us the likely value of $r \bmod s$.  Then, we take all our likely values, and use the Chinese Remainder Theorem to reconstruct $r$.

If we have 10,000 such values, we can use the prime-power's up to 710; for each value of $s$, the correct value of $r \bmod s$ will be at least 3 standard deviations over the rest (and hence the most common value is likely to be the correct one), and that'll give us enough relations to recover a 1024 bit $r$.

We can then use fgrieu's observation to validate the $r$ we recovered.


Random Access vs. Parallelism modes of operation

Random access (read, or write, or both) is a property of a mode of operation. Parallelism is a form of computation where multiple independent execution units can work together to complete an operation faster. They're somewhat orthogonal concepts, although random access does imply that a mode of operation is trivially parallelizable.

Random access is always a good thing because it allows more flexibility in how the mode of operation can be used (for instance, random access modes are desirable in full-disk encryption because you don't want to be waiting for your entire disk to be decrypted just to read a small text file on it). There are perfectly secure modes of operation available with either non-random-access and random-access. Random-access modes do generally tend to require a little more care with nonce/IV selection than modes without due to the constructions that tend to come up when designing for random access, but there is absolutely no reason to equate random access capability with security.

Random access has nothing to do with security; if a mode of operation that allows random access is insecure, then it is a bad mode of operation and should never be used, regardless of its random access properties. Whether an attacker does or does not leverage CBC's random access properties when decrypting has no impact on CBC's security properties (stated differently: CBC is what it is; the fact that it happens to allow random access during decryption has no bearing on its security properties).


How can IND-CPA encryption be identity revealing?

Consider an IND-CPA secure scheme that has the setup, encrypt and decrypt functions as $S_{secure}$, $E_{secure}$ and $D_{secure}$ respectively. Consider another scheme with setup, encrypt and decrypt functions as $S_{IR}$, $E_{IR}$ and $D_{IR}$ respectively.

Let $S_{IR}$ be the same as $S_{secure}$ to produce the key $K$. Let $E_{IR}$ run $E_{secure}(K, x)$ to get the ciphertext $C$, and return $C||H(K)$ where $H(x)$ is a collision resistant one way hash function. Let $D_{IR}$ simply discard the hash part of the ciphertext and use $D_{secure}$ to decrypt.

If, $S_{secure}$, $E_{secure}$ and $D_{secure}$ form an IND-CPA secure encryption scheme, $S_{IR}$, $E_{IR}$ and $D_{IR}$ also form an IND-CPA secure scheme, but the latter is identity revealing.

Note that no additional information about any of the messages is revealed in this case, and this is the only thing that IND-CPA security wants to control for. The IND-CPA security notion does not care if some information about the key is revealed.


Understanding the big picture with regard to how anonymous credentials work

I'll try to give some high-level intuition of the used construction paradigms in my answer below. First, note that we distinguish between one-show and multi-show anonymous credential schemes.

For one-show credential schemes, you essentially have that multiple showings of the same credential can be linked to each other, while showings are unlinkable to the issuing. Those schemes are typically instantiated using Blind signatures (e.g. Brands' credential scheme, or Baldimtsi and Lysanskaya's anonymous credentials light). Essentially, a Blind signature scheme is an interactive protocol where the signer does not learn the signed message. The issuer usually signs a blinded version of a commitment to the attributes of the user and the user then uses the unblinded, signed commitment together with a proof of knowledge upon showing. From a very high-level point of view, the property that the signer does not learn the signed message helps to achieve unlinkability between issuing and showing.

For multi-show credential schemes you essentially have that even multiple showings of the same credential are unlinkable. Those schemes are typically instantiated using a signature scheme where the signatures can be publicly randomised and which is compatible with zero-knowledge proofs. The issuer signs commitments to the attributes and upon showing one randomizes the signature and proves knowledge of the signature and the attributes (only the attributes which should be shown get revealed). The most prominent instantiations of this paradigm are Camenisch and Lysyanskaya's anonymous credential schemes (both the RSA variant and the pairing variant). Recently, another paradigm to construct multi-show anonymous credentials was introduced by Hanser and Slamanig. The use signature schemes where signatures and signed messages can be publicly randomised, together with a compatible commitment (i.e., one which still binds the committed message even when re-randomised). Here, the issuer issues a signature on commitments and showing amounts to re-randomizing the signature and the signed message and opening the commitment with respect to the attributes to be shown (they also require a simple zero-knowledge proof to guarantee freshness).


What is the state of cryptographic obfuscation in 2015?

This is really an ongoing area of research in the cryptographic community. So, no, I don't think anything of the sort is available in any programming languages. The DARPA SAFEWARE program suggests that a lot of research money is being put into the area and will give you a feel for some of the topic areas that the community is working on.

Matt Green's post you linked to provides a lot of good background material, but being a year old is outdated somewhat.

A recent survey paper goes over the current state, open problems, etc.

Here are some relevant quotes on the state of the technology:

Scope

  Learnable programs, i.e. the source code of which can be reconstructed by just executing it on different
  inputs, are clearly not interesting for obfuscation, although, most of the interesting programs are not learnable
  and the range of potential applications is extremely wide.

Efficiency

  The most complex function that they (Apon et al., in Implementing Cryptographic Program Obfuscation) obfuscated was a 16-bit point function containing 15 and gates. The process took 9 hours and resulted in an obfuscated program of 31.1 GB size, the evaluation of which on a single input takes around 3.3 hours on a machine with 32 cores and 244 GB RAM.

Dan Bernstein, Andreas Hülsing, Tanja Lange and Ruben Niederhagen broke Apon et al.'s scheme in 19 min on a cluster of 21 PCs. Section 3 of their paper contains some (partially quite obvious) optimizations to get a speed-up of about 50 for running the obfuscated program.

I'm making this a community wiki post so that others can updated it more easily as new results come out. This is a rapidly changing field in cryptography.


SHA1 collision event probability after n iterations

Assuming the inputs and outputs are random, you would expect:

$$\begin{align}
P[\operatorname{SHA1}(s_1) \not= \operatorname{SHA1}(s_2)] &= 1 - 2^{-160} \\
P[\operatorname{SHA1}^2(s_1) \not= \operatorname{SHA1}^2(s_2)] &= (1 - 2^{-160})^2 \\
... \\
P[\operatorname{SHA1}^n(s_1) \not= \operatorname{SHA1}^n(s_2)] &= (1 - 2^{-160})^n \approx 1 - n/2^{160}, \\
\end{align}$$

where $\operatorname{SHA1}^2 = \operatorname{SHA1} \circ \operatorname{SHA1}$, etc.

Thus, $P[\operatorname{SHA1}^{10^9}(s_1) = \operatorname{SHA1}^{10^9}(s_2)] \approx 10^9 / 2^{160} \approx 2^{-130}$.

That's for a single pair $s_1 \not= s_2$. If you are looking for collisions, you would expect a collision with $\operatorname{SHA1}^{10^9}$ after something like $2^{130/2} = 2^{65}$ strings.

This approximation only holds while $n$ is small enough, and breaks down when it gets close to $2^{80}$ and cycles start to become an issue. However, for $10^9$ it should do all right.

However, there are (theoretical) attacks to find collisions in SHA1 faster, so for non-random inputs the probabilities could be higher.


Tests of randomness with only data as input can give proof of non-randomness, but never a credible indication of randomness unless their result is coupled with an analysis of how the random data tested has been generated. Without such knowledge, such tests give a falsely reassuring PASS, or a FAIL.

Illustration: consider the PRNG that outputs 512-bit blocks computed as the HMAC-SHA-512 of the previous block under some key. That pass any randomness test for one not knowing the key, yet is trivially predictable from past output with that knowledge.

In cryptography, randomness tests with PASS result can only be useful when and if we have a model of the source tested. This is at the heart of the AIS31 methodology of Common Criteria evaluation for True Random Numbers Generators in things like Smart Cards; see there (under AIS31; the page exists in German only AFAIK, but has links to many documents in English and a Reference implementation of the statistical tests).

Per the AIS 31 methodology, it is made some model matching the device, and justified that per that model, any likely defect that do not raise alarm won't result in using a significantly predictable bitstream. Typically there is:

a TRNG based on some analog phenomenon, e.g. sampling of a noise source, delivering a bitstream that can be sampled for testing purposes;
hardware or/and software testing that source, at startup and/or runtime, in order to check that this source delivers entropy; including, at least, something that raise alarm if anything makes that source totally defective (that could be an attacker with a needle, a laser, evaporation of some liquefied gas..);
a hardware or/and software conditioning of the output of that source, into another bitstream, that won't have discernible bias even if the source is only passable; that conditioned bitstream can be used e.g. as source of randomness for DPA countermeasures, or a key generator.
possibly, an additional test that conditioning works as intended.


Is it possible to add error propagation to OTP?

What you are actually looking for, which is a way to reuse a one-time pad, is not possible. For OTP reuse to be in any way secure, you need an algorithm with enough "complexity" to be a secure cipher (where the "pad" is actually a key).

For example, in the comments you raise the idea of including a random number and using the 8-bit CBC that Richie Frame and poncho mention. That would not work, because a known plaintext attack would reveal the pad, and the encryption of each byte would only depend on the encrypted value of the previous byte (known) and the pad at that point (recovered after a known plaintext attack).

For the title question the CBC idea is a valid answer, but it does not seem very useful. There is also a complementary question: is there a way to cause changes in the ciphertext to propagate through the plaintext. There e.g. the PCBC mode would work, but again I do not how useful that is.

As for actual suggestions, if you cannot handle the unique pad requirement of OTP (which is common), you should use a conventional cipher like AES. Preferably in authenticated encryption, so that error propagation does not need to be worried about.


Hash algorithm for user accounts passwords in macOS 10.12, 10.13, 10.14

As @kelalaka said, the answer is still valid as described in this question, so a PBKDF2-SHA512 hash with a large salt and iteration count in the 100000's, usually.


Is this definition of an RSA modulus safe?

Overall I find the proposed definition and methods satisfactory in principle, barring quantum computers usable for factorization; but the 512-bit limit for factor, and to a lesser degree the 2048-bit unfactored limit, are not conservative.

Unfactored limit

As noted in comment, for long term security or/and convincing security authorities, it's probably best to up the 2048-bit size to 3072-bit, or more. France's ANSSI changed mind and went from year 2020 to 2030 for the limit beyond which 2048-bit is no longer enough, but other authorities stick to earlier dates.

Difficulty of factoring $n$ by GNFS grows with $L_n\left[\frac1 3,\sqrt[3]{\frac{64}9}\right]$ in L-notation, and (ignoring the hidden $o(1)$ term) that tells 2048-bit is roughly 40 Binary Orders of Magnitude (BOM) harder than the RSA-768 landmark of 2009. This is comfortable for now, but not huge. 3072-bit gives 62 BOM, that is huge.

Small prime limit

Difficulty of factoring by ECM grows roughly as $L_p\left[\sqrt2,\frac1 2\right]$ where $p$ is the factor pulled. Neglecting the $o(1)$, that tells a 512-bit $p$ is roughly 28 BOM harder to pull by ECM than the 273-bit record of 2013. That does not look like a comfortable margin to me: Ryan Propper's log and account mention relatively modest resources compared to the RSA-768 effort:

  For this job, I did about 5,000 curves, spanning about 10 days, on the FarmShare compute cluster at Stanford. I guess this was quite the lucky find. :)

and I do not see that the latest theoretical advances (Edwards curves) have been used. Consider more effort, dedicated ASICs, Moore's law at 1 bit per year, and the 28 BOM is about gone. I would not go below 640-bit (>41 BOM) or 704-bit $p$ (>47 BOM) with 2048-bit $n$. 832-bit $p$ gives 59 BOM, that's large.


Stern identification scheme to signature scheme

In order to convert a 3-move id-scheme to a digital signature you have to replace the request (or the challenge) by the value of a secure hash function applied to the message (this method is called Fiat-Shamir method).

In Sterns's id-scheme you have to choose a random element from the set $\{0,1,2\}$ for your message. That is $H(m)\in \{0,1,2\}.$ For  instance if you have $H(m)=0$ then the signature of $m$ is $(c_1,\Pi).$

EDIT : Before you convert it, you have to run the id-protocol many times, say 64 or 80 times, and then apply Fiat-Shamir method.


Is it possible to fool Miller-Rabin test?

In fact even brute force does not work, unless you know what random numbers the Miller-Rabin test will use to test the numbers, because in case of each possible non-prime number, some Miller-Rabin test input will reveal it is composite.

FIPS 186-4 C.3 contains recommended Miller-Rabin number of rounds to use to test the numbers. Those amounts of Miller-Rabin tests are expected to catch composite numbers with overwhelmingly large probability. The document contains useful information about Miller-Rabin and how test is supposed to (probabilistically) protect from this attack (fooling it with composite numbers).


I think this can be done relatively simply with any additive secret sharing scheme (which Shamir's scheme is). The basic idea behind the scheme (to make a $(n, k)$ no-dealer secret sharing scheme) is:

Each party samples a uniformly random value $s_i\in\mathbb{F}_p$
Each party makes $n$ shares of this value (using an additive $(n, k)$ secret sharing scheme), which we will call $\{s_{i, j}\}$ for $j\in[n]$
For all $(i, j)\in[n]^2$, Party $i$ sends $s_{i, j}$ to party $j$.
For all $i\in[n]$, party $i$ sets $s_i' = \sum_{j\in[n]}s_{i, j}$
All parties are left with a sharing of $s' = \sum_{i \in[n]} s_i$

The idea for why this should be secure (up to the threshold $k$) is that there are really three things an adversary can do:

Choose $s_i$ non-uniformly (and among the $k-1$ parties, choose them dependent in some way)
Send out "incorrect" shares of their secret
Compute $s_i'$ incorrectly

The first two points can be seen to be equivalent, as sending out "incorrect" shares is the same as sending out correct shares of an incorrectly sampled secret.
If you know a group of honest parties will reconstruct the secret, these incorrectly sampled secrets will not be an issue (the sum $s' = \sum_{i\in[n]}s_i$ will be uniformly distributed as long as any $s_i$ is individually uniformly distributed, and all other secrets are independent of this value).
I don't know how tolerant the above will be to corruptions during the reconstruction process, but it doesn't seem like this is what you're asking about. I imagine it would be roughly as tolerant as the "base" additive secret sharing scheme is, but don't have a readily available argument (so will omit this, while mentioning that it's an interesting thing to think about).
This also has relatively high communication complexity ($O(n^2)$ in the sharing process --- it feels like $O(nk)$ might be possible, but I don't want to over-optimize it right now), and can only sample secrets on fields $\mathbb{F}_p$ for which Shamir's is secure (so you must take $p$ to be exponentially large, so it is wasteful in the size of communications (instead of just the number of messages) if you only need a "small" secret to be agreed upon), which seem like the major "downsides" of it to me.


Is this client-side password hash scheme secure?

This is far from secure, assuming a passphrase that a human can remember. The main thing you have to note is that an offline brute force attack on the password can be carried out. This is because the server can guess the password and follow the same procedure and see if decryption works. It is possible to buy a machine that computes billions of hashes a second (for a few thousand dollars). Very few passwords will be strong enough to resist such an attack.

If you can't do anything better than encrypting with a password, then at least it's something. But I wouldn't trust such a solution (not for passwords that I can remember). I suggest finding a different way to propagate a secret key for the client, rather than storing it on the server. (I know that this will be less usable, but security costs...)


If you XOR a random input with a biased input, the output is random - why?

Let $X, Y \in \{0,1\}$ be random variables, with $\Pr[X = 0] = \Pr[X = 1] = 1/2$ and any distribution on $Y$ as long as $Y$ is independent of $X$ so that $$\Pr[Y = y \mathrel| X = x] = \Pr[Y = y]$$ for any fixed bits $x, y \in \{0,1\}$.  What is the distribution on $X \oplus Y$?  Let $b \in \{0,1\}$ be a fixed bit.  Then

\begin{align*}
  \Pr[X \oplus Y = b]
    &= \Pr[X \oplus Y = b \mathrel| X = 0]\cdot\Pr[X = 0] \\
      &\quad\quad + \Pr[X \oplus Y = b \mathrel| X = 1]\cdot\Pr[X = 1] \\
    &= \Pr[0 \oplus Y = b \mathrel| X = 0]\cdot(1/2) \\
      &\quad\quad + \Pr[1 \oplus Y = b \mathrel| X = 1]\cdot(1/2) \\
    &= \Pr[Y = b \mathrel| X = 0]\cdot(1/2) \\
      &\quad\quad + \Pr[Y = b \oplus 1 \mathrel| X = 1]\cdot(1/2) \\
    &= \Pr[Y = b]\cdot(1/2) + \Pr[Y = b \oplus 1]\cdot(1/2) \\
    &= (\Pr[Y = b] + \Pr[Y = b \oplus 1])\cdot(1/2) \\
    &= 1/2,
\end{align*}

the last equality arising because $b$ and $b \oplus 1$ are the only two possible values that $Y$ can take on, so $\Pr[Y = b] + \Pr[Y = b \oplus 1] = 1$.


Help with AES decryption with AES-NI Instructions

This answer is based on Intel® Advanced Encryption Standard (AES) New Instructions Set whitepaper (Revision 3.01, September 2012) by Shay Gueron.

No, the keys are not identical (within order) for encryption and decryption. The first and last key used in decryption are indeed the last and first one used in encryption; but the other decryption keys are the encryption keys with an additional InvMixColumns applied (usually by way of the AESIMC instruction in a preparatory step), in reverse order.
No, the sequence of operations is not as described in the question; it shall be, for AES-128:

XOR with $K_{10}$ (the last and 11th key used in encryption);
for $j$ from $9$ downto $1$:

apply VAESDEC to the result using $K^\prime_j$ (the image by InvMixColumns of the $(j+1)$th key used in encryption);

apply VAESDECLAST  to the result using $K_0$ (the first key used in encryption).

Rationale: having InvMixColumns pre-applied to (the bulk of) the round keys allows to combine them in the decryption flow after InvMixColumns, rather than before in a realisation of decryption that inverts encryption step by step. Presumably, that's easing pipelining constraints. It works because InvMixColumns is linear, that is $\operatorname{InvMixColumns}(X\oplus K_j)=\operatorname{InvMixColumns}(X)\oplus \operatorname{InvMixColumns}(K_j)$.


Calculate RSA private exponent when given public exponent and the modulus factors using extended euclid

Try just expanding the parentheses. Once they're all gone, collect all the multiples of $40$ and $17$ together:

$(40 - 2 \times 17) - 1 \times (17 - 2 \times (40 - 2 \times 17)) = 1$

$1\times40 - 2 \times 17 - 1 \times 17 + 2 \times (40 - 2 \times 17) = 1$

$1\times40 - 2 \times 17 - 1 \times 17 + 2 \times 40 - 4 \times 17 = 1$

$(1 + 2)\times40 - 2  \times 17 - 1 \times 17  - 4 \times 17 = 1$

$(1 + 2)\times40 - (2 + 1 + 4) \times 17 = 1$

$3\times40 - 7 \times 17 = 1$, or

$(-7) \times 17 + 3\times 40 = 1$


Can the AES encryption and decryption algorithms be described as a polynomial for a specific key?

Yes, they can be described as a multivariate polynomial over $GF(2)$ (or over $GF(2^8)$).  See algebraic cryptanalysis.  This expression does not seem to help cryptanalyze AES, so far as we know, but it can be done.

For an example of how to write AES in this way, see the following paper:

A simple algebraic representation of Rijndael.  Niels Ferguson, Richard Schroeppel, Doug Whiting.  SAC 2001.

You can also read about the XSL attack, a controversial attack that was claimed by some researchers to work against the AES and which is based upon a representation of AES as multivariate polynomials.


KDF for generating RSA and ECC keys from a 2048 bit secret

Rather no. There is no standard construction going by the name Key Derivation Function aimed at generating public/private key pairs. Traditionally, especially for RSA, how to generate a key pair is left at the discretion of the implementation, rather than made per a specific deterministic process. The usual name is Key Generation. And it's usually stated as a randomized algorithm, rather than as a function.
For ECC per Sec1, it is straightforward to define such KDF. The private key is an integer $d$ in range $[1,n-1]$ where $n$ is the fixed, public order of a generator on a curve. Thus we could take the 2048-bit secret¹ $s$, and turn it to the private key by applying $d\gets(s\bmod(n-1))+1$; then compute the public key by applying $Q\gets d\,G$ using point multiplication. Since in practice $n\le2^{800}$, the bias on $d$ is negligible if the 2048-bit $s$ is uniformly random.
For RSA, that's less easy. We need to specify a Cryptographically Secure Pseudo-Random Number Generator, seed it with the 2048-bit secret¹ $s$, and generate the RSA key per some precisely agreed-upon process. FIPS 186-4 appendix B.3.2 is next to being precise enough. Also, beware that it is hard to secure such computations from side-channel and fault attacks.

¹ Or a derivative $s$ of that secret by a symmetric KDF.


For the sake of simplicity, I assume that every party can be identified by a keypair (e.g. Alice has a public $A_{p}$ and a secret $A_s$) and every asset by an identifier (a hash for example).

Let us say it is "known" that Alice owns a certain property identified by $P$, either because she created it and registered the identifier somewhere, or she claimed it, or got it from someone else (we don't care). A way that she could transfer the ownership to Bob (with keypair $B_p, B_s$) is to make a statement that is semantically equivalent to:

I, Alice, transfer the ownership of [P] to the person holding the key [B_s].
The current date is [Mon 30 Oct 17:27:18 CET 2017].

She then signs the statement with her private key $A_s$ and gives it to Bob. Then, if anybody contests whether Bob actually owns $P$, he can show the signed statement and thus prove that he owns $P$.

There is only one drawback to this system, which is that Alice could transfer the ownership more than once. This is because she can just write another statement with an invalid date, which looks (as long as we never have seen Bob's statement) to be valid all the same.

Therefore, we will always need to broadcast transfers of ownership. There are multiple ways this can be done. For example, Bob could put the hash of the statement in a widely distributed newspaper. Then he could later point back to prove that the statement indeed existed at the moment the newspaper was printed. To retract this Proof of Existence (PoE) you would need to get your hands on all the prints of the newspaper, which is probably not feasible.

We could (as you mention) also publish the statements in a blockchain (this is what Bitmark does), such that the distributed nature of the blockchain makes it impossible to retract a statement.

A third way is to use a trusted third party. The Time Stamping Protocol defines CA's for signing PoE's for users. On Twitter, you will sometimes see cryptographers publishing proofs of existence for articles/knowledge that they are not (yet) allowed to publish. In this case, Twitter is the trusted third party (because we all trust Twitter not to allow a person to tweet in the past).


Check if two anonymously signed messages have the same author

Ok, here's a simple method that appears to address your requirements.

It uses two signature methods; the first one (the "inner signature") is conventional; the second one (the "outer signature") is anonymized.

When Alice generates a message $m$, she either generates a public/private key pair $Pub_a, Priv_a$ for the inner one, or reuses a $Pub_a, Priv_a$ pair that she previously generated.  She then signs the message with the private key, generating $Sig_a(m)$, and forms the tuple $(Pub_a, Sig_a(m))$.  When then interacts with server to anonymously generate the public signature of this tuple $Sig_s(Pub_a, Sig_a(m))$, and generate as a signature the tuple:

$$Sig_s(Pub_a, Sig_a(m)), Pub_a, Sig_a(m)$$

To validate this signature, one would verify that $Sig_s(Pub_a, Sig_a(m))$ is a valid signature for $Pub_a, Sig_a(m)$ (based on the Server's public key), and if $Sig_a(m)$ is a valid signature of the message (based on the public key $Pub_a$).

As for your requirements:

It is anonymous; $Pub_a$ is a random public key, and so there's nothing to link it with Alice
It is linkable; Alice can use the same $Pub_a, Priv_a$ to sign two related messages; anyone can see that those two signatures use the same $Pub_a$ value (and hence must be signed by the same person)
Links are trustable; as no one else knows the value $Priv_a$, no one other than Alice can sign a message using $Pub_a$


Why does DESX break if one removed post whitening?

The goal of DESX is to improve the security above the 56-bit level offered by DES. So an attack that's merely as expensive as brute-forcing the DES key is an attack, even if it's still rather expensive.

Define $E_{K,W}^\prime(P) = E_{K}(P\oplus W)$ and $D^\prime$ as its inverse. Then we can relate the two known pairs $(K_1,P_1)$ and $(K_2,P_2)$:

$$\begin{eqnarray}
P_1\oplus P_2 &=& D^\prime(C_1)\oplus D^\prime(C_2)
             \\ &=& (D_K(C_1)\oplus W)\oplus (D_K(C_2)\oplus W)
             \\ &=& D_K(C_1) \oplus D_K(C_2)
\end{eqnarray} $$

Since $P_1\oplus P_2 = D_K(C_1) \oplus D_K(C_2)$ only involves $K$ and not $W$ we can simply brute-force that 56-bit key, ignoring $W$, showing that using only pre-whitening does not improve security compared to plain DES. A similar argument can be applied to post-whitening. Note that this attack does not rely on the particular structure of DES (except having a key short enough to brute-force) and can be applied to any other blockcipher.


You're missing a piece in your understanding of modern encryption.

AES is a symmetrical block encryption cipher. It describes how to use a key (which can be 128, 192 or 256 bits) long to encrypt and decrypt a single block of fixed size (128 bits) of data. That's it.

In order to have a complete encryption/decryption system, you need to couple it with several other pieces.

First, you need to decide how you're going to apply that algorythm to data that aren't exactly 128 bits long. At the same time, you might want that "system" to provide additional properties: make sure that encrypting two identical pieces of data with the same key will not result in the same encrypted data, providing a (standard) way to verify that a given block of data has been properly decrypted, etc.

That's the job of the mode of operation of your block cipher (and the padding algorythm you pick). There are several you can pick from which have different properties (and some are "protected" by patents which can makes their use expensive). Which one you choose depends mostly on what you're going to apply it to.
Almost all of these mode of operation will use something call an initialization vector (IV) which is a block of data that is use to initialize the processing and which should be unique but not private (so you can send it with the cipher text without any risk).

Once you couple these two elements, you can start thinking about key management.

AES is symmetrical so it uses the same key for encryption and decryption. There is no public key involved.

So, after this, the answers to your questions are:

The reuse of the key is not a problem as long as you have chosen a mode of operation that is appropriate for your application (and of course, if you have used it properly). This is because the mode of operation will "pre-mix" your clear text data in a way that, even before encryption, two identical block of data you feed to the actual AES algorythm will never be identical (or at least, not more often than by random chance).
To simplify, you can reuse a private key as often as you want as long as you can generate new initialization vector for each message.
The "strength" of algorythm mostly is defined on how long it takes for an attacker to test a set keys. A perfect cipher would have you attempt a full decryption using half the possible keys (key space) before you had a 50% chance of finding the right one. Many attacks on modern cryptographic ciphers consist of finding ways to test a key faster than going through the whole system or being able to obtain information about the key based the on input or output (sometimes both). The whole science behind this art if called "Cryptanalysis".

As you can see, finding out if an cipher is "safe enough" is a very complex tasks. That is why no serious system uses its own private crypto: it is just too hard (and expensive, and long) to come up with a good proof of safety. Hence the "rule zero" of secure software development: "don't write your own crypto". It's hard enough to use known algorithms properly...


How many oracle calls to break an affine cipher in a chosen plaintext attack?

The answer is 1 I think because if we apply a chosen plain text attack, then we need at least 2 encrypted alphabets and two plaintext alphabets corresponding to the related encrypted alphabets. Then we will have two variable and two equations.

By solving those you can get the additive key as well as the multiplicative key.


Is it possible to retrive the Hash from an encrypted folder?

Brute forcing a password is always possible - at least in theory. If it is computationally feasible to derive the password hash is a different matter; it obviously depends on the complexity of the password, the work factor used by the password hash (or rather, password based key derivation function) and how the software operates. You need to find the password as brute forcing the resulting key is not likely to be feasible. Depending on the encryption software the result can be directly validated or you may need to try to (partly) decrypt a file.

Reverse engineering the encryption software cannot be used to decrypt the files; the encryption depends on the key, not on the algorithm. You may need to reverse engineer the encryption software to facilitate the brute force or dictionary attack though. Then you could integrate it with password cracking software.

If the encryption is performed correctly then finding the password is the only real option available.


Are there any successful preimage attacks?

MD4 is Not One-Way. The attack described in the 2008 paper is a theoretical attack with complexity $2^{102}$, which is better than the brute force complexity of $2^{128}$. In later theoretical results reported here the complexity dropped to $2^{94.98}$ and here it dropped even further to $2^{69.4}$ for secondary pre-image attacks.

Similarly, The MD2 Hash Function is not One-Way as reported in a 2004 paper, where the complexity of finding pre-images was reported to be $2^{104}$, compared to the brute force complexity of $2^{128}$. The attack was improved in 2008 to a complexity of $2^{73}$.

Other examples include draft algorithms that are broken during the initial design phase or peer-review phase, such as the SHA-3 submission Maraca.

Non-cryptographic hashes, such as MurmurHash, are usually not designed to be one-way. In order for something to qualify as a proper "attack", it has to do better than anticipated given the security claims. If there are no security claims, there can't really be any attacks either. And of course, if there are no security claims, the algorithm should obviously not be used for cryptographic purposes.

A helpful hint might be to only use algorithms that are published, have security claims, and always search for papers that mention the algorithm name here https://eprint.iacr.org/search.html before using it for production purposes. Practical attacks are almost always preceded by theoretical attacks, and theoretical attacks are often (almost always?) published somewhere. This doesn't, however, apply to every proprietary algorithm on the Internet, and also not to algorithms that are not designed for cryptographic purposes to begin with.


You are essentially describing instant messaging via onion routing or garlic routing.  Tox is an example of such a protocol. Tor Chat is another.

In an onion network, messages are encapsulated in layers of encryption, analogous to layers of an onion. The encrypted data is transmitted through a series of network nodes called onion routers, each of which "peels" away a single layer, uncovering the data's next destination. When the final layer is decrypted, the message arrives at its destination.

Below is a simple illustrated description of onion routing (taken from Wiki).

In this example onion, the source of the data sends the onion to Router A, which removes a layer of encryption to learn only where to send it next and where it came from (though it does not know if the sender is the origin or just another node). Router A sends it to Router B, which decrypts another layer to learn its next destination. Router B sends it to Router C, which removes the final layer of encryption and transmits the original message to its destination.

This does not completely defeat attacks, but if implemented correctly it should be difficult to de-anonymize users and interpret traffic.  The arrest of silk road creator Ross Ulbricht suggests that with enough desire, time, and luck the FBI could catch you.  But even then, you'd probably need to make some mistakes along the way.  And obviously the FBI are not your average man in the middle.


Where did SHAKE128 and SHAKE256 originate from?

They follow from the general properties of the sponge construction. A sponge function can generate an arbitrary length of output. The submission of Keccak to the SHA-3 competition proposed a single "XOF" (extendable-output function) with a user defined length, which would have been essentially SHAKE-288. NIST seems to have decided on two instead, with more "normal" security levels.

  Any public cryptanalysis done on them?

Anything on the generic Keccak function may also apply to them. I don't know of any cryptanalysis specifically on the XOFs, beyond what was done by the authors themselves in the submissions and the site I linked above. However, a comment (pdf) to the draft standard complains that the usage of XOFs (i.e. SHAKEs) is not defined well enough and that their security claim is not very rigorously stated.


Decrypting ciphertext produced by the Trivium stream cipher

Trivium is a synchronous stream cipher. For synchronous stream ciphers the key stream is independent of the plaintext and ciphertext.

The key stream (which is not the key itself, but the output of the cipher construction) is then combined in a reversible way with the plaintext to for the ciphertext (commonly byte-by-byte). The reverse operation with the same key stream and the ciphertext brings back the plaintext.

Usually XOR is used, which allows you to use the exact same construction for both encryption and decryption (as $PT \oplus KS = CT$ and therefore $CT \oplus KS = PT$).


Is it possible to get an RSA encryption key by comparing the unencrypted and encrypted file?

No, if the RSA cryptosystem is secure, i.e. when it uses random padding such as PKCS#1 v1.5 padding or OAEP, then you cannot. As Stephen already mused, it is pretty likely that you can find out the key simply because it is included or can be derived; generally public keys are not meant to be secure.

If textbook (raw modular exponentiation) RSA is used then you can encrypt with the public key. If you get the same value then it is pretty likely that you've found the public key. But usually textbook RSA isn't used because it is insecure in several other ways as well. Ciphertext distinguishablity is just one of the problems.

Now some information can of course still be extracted from the ciphertext. First of all, the length of the RSA ciphertext is generally identical to the key size. So you can distinguish between keys of several lengths. Furthermore, if you find an RSA ciphertext that is higher than the modulus of the public key then that key is certainly not used to generate the ciphertext.

You explicitly asked for the encryption key which is the public key. If you meant the private decryption key then, no, the key cannot be derived except for the little amount of data also available for the public key.

Note that RSA is never directly used to encrypt files. Instead a hybrid cryptosystem needs to be used. The usual RSA schemes are not secure to encrypt data larger than the modulus minus the padding overhead. Furthermore, encrypting large amounts of data with RSA would be very CPU intensive and decrypting it would be worse.


Proving that there is no scheme which would be perfectly CPA-secure

The perfect indistinguishably under a chosen-plaintext attack: Pr[PrivK_cpa = 1] = 1/2
Is my argumentation correct to this point?

No, because the question doesn't ask about 'perfect indistinguishability' (which would include computationally unbounded adversaries), just indistinguishability against probabilistic polytime adversaries.
Assuming that the adversary has access to the public key, then here is an adversary that achieves an advantage $> 1/2$:

Select a set of random coins; send them through the $Gen$ function

Compare the public key generated with the public key presented

If they are the same, use the private key generated to decrypt the ciphertext and use the resulting plaintext to make the decision.

If they are not the same, select a random bit and use that as the output.

Now, if this procedure selects a set of random coins that just happen to be the same as the coins used during the original key generation process, then this always achieves the correct answer (or, at least, with high probability if the public key system has a small probability of decryption failure); if it does not, then this gives the correct answer with probability at least 1/2 ("at least" because there may be other sets of random coins that result in the same public key; those would also give the correct answer).
Hence, if $\lambda$ random coins were used in the key generation process, this gives the correct answer with probability $2^{-\lambda} + 0.5(1 - 2^{-\lambda}) > 1/2$


Deriving HMAC key and cipher key from passphrase?

If you are doing authenticated encryption with an AES and HMAC combination, the security of your scheme depends on the key for encryption and the key for message authentication being independent. The general idea is that you might generate two independent keys from a single master key, by proper usage of a $PRF$. The most performance effective solution is therefore to modify your first suggestion in either of two ways:

Let $K$ be the output from the PBKDF2.

Alt 1. Derive the encryption key $K_e$ and authentication key $K_a$ using one call each to
$K_n = PRF_K(label_n)$. The input $label_n$ might e.g. be the single char "e" and "a" respectively.
Alt 2. Derive $K' = K_e||K_a$ using a single call to $PRF_K$ to generate a 512 bit derived key.

Please note SHA-512 is not a pseudo random function, but might be used to create one. For instance, you could use HMAC-SHA-512 as your PRF.


Understanding Genkin-Pipman-Tromer's ground potential, side channel attack on RSA

How did they jump from the spectrogram showing the RSA exponentiation timings straight to the secret bits?

Actually, they're jumping to secret bits; however those aren't the secret bits you're thinking of.

The bits displayed above are not the actual bits of $p$ and $q$.  Instead, those are the bits from the secret exponent; because GnuPG uses CRT (and apparently binary exponentiation), those bits are of $d_q = d \bmod p-1$ and $d_q = d \bmod q-1$ (where $d$ is the private exponent).

With the CRT optimization of RSA, we take our message $M$, and divide it into $M_p = M \bmod p$ and $M_q = M \bmod q$.  We then compute $C_p = M_p ^{d_p} \bmod p$ and $C_q = M_q ^{d_q} \bmod q$ separately, and then recompute $C_p$ and $C_q$.  This attack looks at the computation of $M_p ^{d_p} \bmod p$ and $M_q ^{d_q} \bmod q$, and attempts to recover $d_p$ and $d_q$

So, what good are those bits?  Well, those are as good as the actual values $p$ and $q$; with the knowledge of those values (actually, we only need one of the two), and the public key, we can factor.

The actual technique to factor using $d_p$ does use some simple number theory; I'll sketch it out for you: with your known value $d_p = d \bmod p-1$ and the public exponent $e$; because of how RSA works, we have the property that $x^{e \cdot d_p} = x \pmod p$ (for any $x$), while no such relation holds $\pmod q$.  So, what you do is select a random value $r$, and compute $r^{e \cdot d_p} - r \bmod n$.  This value is 0 mod p, and (with high probability) nonzero mod q; hence doing a simple gcd with that value and $n$ gives you the value $p$

  I expect that jump is highly dependent on GnuPG's RSA implementation.

Yes; this sort of attack won't work with more recent implementations (such as OpenSSL), which disguise these sorts of simple side channel attacks.


No, in general you cannot.

WinRAR uses AES (128 or 256 depending on version) for encryption, which does not allow key recovery even with know plaintext and ciphertext.

It also uses key stretching to derive the encryption key from a password. The algorithm used in newer versions is PBKDF2 with a version dependent iteration count. So a key-guessing attack is only possible for low entropy passwords. There is a verifier in the file format that allows checking password guesses, so knowing a plaintext and/or ciphertext does not give any advantage there either.


SHA-3 is conjectured to be collision-resistant, which is enough for $H(r \mathbin\| m)$ to be eTCR; if SHA-3 fell to a collision attack like MD5 and SHA-1 before it, it would nevertheless be surprising and remarkable and worthy of publication for SHA-3 to fall to a target collision attack as neither MD5 nor SHA-1 to my knowledge has, but one can only speculate about hypothetical developments past the failure of what is already only a conjecture.

The NIST-recommended ‘keyed hash’ function associated with SHA-3 is KMAC of NIST SP 800-185, of course.  If you're still not comfortable with that, the NIST-recommended randomized hash for collision-resilient signatures is RMX of NIST SP 800-106, which you could use with SHA-3 out of an abundance of paranoia, but I have never heard of anyone bothering to do that.