Why not use an algorithm's code rather than data itself for one time pads? Instead of using actual data for one time pads, what would be different if the code for an algorithm was exchanged so that to acquire the pad one would execute the algorithm and use its output?  Why is this not being used?

An algorithm would be much shorter and could generate a significant amount of chaotic information.  There are so many examples of deterministic unpredictability from fractals (discrete maps) to cellular automata to irrational digit sequences (differential equation zeros?) to CPU floating point operations to modular exponentiation.  And many ways of combining these into more feedback loops.

Even if the output is not as cryptographically strong, aren't there deterministic operations that can ensure a certain level of strength?  And couldn't a computer conceivably do the work of trying long and complex combinations of chaotic algorithms and classes of initial values until an algorithm does produce strong pads to settle on the pad you will use?  There would be no point in an attacker guessing at the probability of kinds of initial values if he doesn't even know the combination algorithm used to generate the pad.  It seems that there would even be safety from guessing from the code length and execution time, even if not padded.

Generating a pseudo-random stream from a key, and XORing that stream with the data to encrypt, is done on a regular basis. That's how most stream ciphers work, e.g. the well-known RC4, and also applies to block ciphers in counter mode. This is not "One-Time Pad", by definition, since OTP requires the key stream to be truly random (that's the condition from which the OTP unbreakability comes). Such stream ciphers still share with OTP the absolute necessity of never reusing a given keystream for two distinct messages, so the encapsulating protocol must take care to renew keys when needed. In SSL/TLS, a new session key is generated for each connection, so when a stream cipher is used (RC4), things are safe.

There are quite a few stream ciphers which have been seriously looked at by cryptographers, who found nothing bad to say about them; see the eSTREAM portfolio for a selection of those.

Chaos, fractals and so on, are not the right tool for cryptography. A chaotic system is just a producer of values which "jump around" in a seemingly random fashion. Statistical analysis tools could be defeated by a chaotic system. But statistical analysis tools are dumb: they are designed to analyze physical phenomena. For cryptography, we want to defeat an intelligent attacker who has a copy of the same software than the one you use, save for the keys themselves. For instance, a Linear Feedback Shift Register has very good statistical properties and produces bits which statistical tools will declare "plausibly random". But for a $n$-bit LFSR, it suffices to observe the first $n$ bits of output to learn the complete internal state, and predict all subsequent output with 100% accuracy (even if the LFSR structure -- the corresponding polynomial -- is unknown, $2n$ output bits are sufficient for that, with Berlekamp-Massey algorithm).

In short words, if you use fractals or a chaotic system in a homemade loop, you will make a cryptosystem apt to defeat a chimpanzee. We cryptographers usually aim a bit higher than that.

Also, secrecy of "the code" (i.e. software) is usually not assumed, because it is very hard to achieve. Software exists in some permanent storage, on a computer hard disk; there's source code somewhere; it is bulky. Keeping code confidential is hard, and even harder is knowing how much confidential it is. This is why cryptographers talk about keys: they split the "code" (e.g. a pseudo-random stream generator) into an algorithm, which is public and becomes software, and a key, which is a small sized parameter which concentrates confidentiality. A typical key is a sequence of, say, 128 bits, small enough to be handled and protected properly (it can even be remembered by a human, and typed back when it is needed -- thus, no need for storage on a hard disk).


Isn't the security of EC curve 25519 126 bits? The security of the EC25519 is given as 128 bits, but since the order of the group is 252 bits shouldn't the security be 126 bits? Given as half the magnitude of the underlying field, since DLP algorithms such as Baby-Step-Giant-Step and Pollard-Rho generally have a complexity of O(sqrt(n)), n being the order of group. At least in theoretical terms. What am I missing?

In the usual definition of security of Elliptic Curves, curve25519 security is in fact 126 bits.

If look at safecurves's rho page you can see the rho complexity for curve25519 is $2^{125.8}$ in accordance to what you say.

Curve25519 author basically doesn't accept that definition of security.
In the Curve25519 paper he states in section 1:

  Every known attack is more expensive than performing a brute-force search on a typical 128-bit secret-key cipher

Which, accordingly to the usual definition of security, would provide 128 bit security.

He provides a little bit more details in Section 3, subsection "Generic discrete logarithms by the rho and kangaroo methods". But the best paper describing his critics to standard definition of security is Non-uniform cracks in the concrete: the power of free precomputation.


If you wrote a reversible SHA-256 algorithm, how many "metadata" bits would be required for reversability? I was reading about reversible computing while thinking about FPGA circuits. I realized that it would be possible to write a reversible SHA-256 algorithm if you stored some additional information as "garbage". E.g. The algorithm/circuit would compute a SHA-256 hash, but it would also produce some metadata that allows you to walk backwards through the logic gates and arrive at the original preimage.

A NOT gate is already reversible, and an XOR gate just needs to pass one of it's inputs as an output. Toffoli gates can be used for everything else, so any boolean function can be made reversible. A fully unrolled SHA-256 algorithm is just a boolean function with an input and output.

If you used reversible gates for every step in a SHA-256 circuit, how many garbage bits would be in the output? And would it be possible to compress this data?

Let's say you have a 447-bit preimage (so one 512-bit chunk.) Would it be possible to compress the garbage from a reversible SHA-256 circuit into less than 447 bits, so that [SHA-256 hash plus garbage bits] would be enough to reconstruct the preimage? (If not, then you may as well just store the original preimage.)

Another way of framing this question: How many bits of information about the preimage are stored in a SHA-256 hash?

If you wrote a reversible SHA-256 algorithm, how many "metadata" bits would be required for reversability?

If you would write such an algo, it would not be SHA-256 anymore. Also, it would lose its cryptographic usefulness.

SHA-256 is a non-reversible, one-way compression function. Voiding the non-reversability would void the core functionality that makes SHA-256 a cryptographically secure hash.

In  the end you would end up having a non-lossy, two-way compression function — and a bad one too as it would waste too much space compared to simple compression functions like (for example) ZIP.

Also, since the goal ends up right there, it is not about cryptography anymore… rendering any further discussion about your idea off-topic.

TL;DR:

Assuming you do not modify SHA-256 and simply rely on your "metadata" for reconstruction, the size of your "metadata" would be equal to the size of the input.
Modifying SHA-256 itself to optimize the space needed for any kind of "metadata" is not an option, as the algo would lose its cryptographic usefulness (and not be SHA-256 anymore anyway).

Besides that, your question seems to try work around something which has been asked several times before.

For example, see Would it be possible to generate the original data from a SHA-512 checksum?.

So, in a broad sense your question is a duplicate of all existing questions asking about restoring the original input data from a cryptographically secure hash output.

Any other interpretation of your question (in its current state) would make it an information theory question which would be more on-topic at Computer Science StackExchange.


Clarification of RFC2246 with regards to Finished Message I'm working on a client handshake finished message for a TLS client, and I'm reading through the RFC 2246 spec. The spec states (in section 7.4.9):

  The hash contained in finished messages sent by the server
  incorporate Sender.server; those sent by the client incorporate
  Sender.client. The value handshake_messages includes all handshake
  messages starting at client hello up to, but not including, this
  finished message. This may be different from handshake_messages in
  Section 7.4.8 because it would include the certificate verify message
  (if sent). Also, the handshake_messages for the finished message sent
  by the client will be different from that for the finished message
  sent by the server, because the one which is sent second will include
  the prior one.

Is anyone able to clear up what it means in the first sentence with regards to the Sender.server and Sender.client?

This is an error in RFC 2246 corrected at https://www.rfc-editor.org/errata_search.php?rfc=2246 and in the subsequent version TLS RFCs 4346 and 5246.
It derives from SSLv3 on which TLSv1.0 was mostly based, now available as RFC 6101 if you want to compare them. You'll see SSLv3 had

enum { client(0x434C4E54), server(0x53525652) } Sender;

(which are the ASCII strings "CLNT" and "SRVR" respectively) and specified that Sender is included in the hash calculation which in SSLv3 was a concatenation of doubled MD5 and SHA1 keyed hashes. TLSv1.0 changed this to finished_label with the values "client finished" and "server finished", included in the PRF defined elsewhere in the document as the XOR of doubled MD5 and SHA1 HMACs, where each HMAC is itself a doubled keyed hash.


Choice of delta-neighbors in Balloon Hash algorithm Reference Document: https://eprint.iacr.org/2016/027.pdf

According to appendix D section 4 definition 27

  each vertex in V has predecessors sampled independently and uniformly at random from the set U

It appears from the pseudo-code in section 3.1 step 2b, and the reference code given on GitHub hash_state_mix(), that this has been implemented by the authors as some form of squeezing bits out of the hash function; however my question is could it just as easily have been done with Mersenne Twister or is there another reason why the hash is required?

If you use the Mersenne twister or any other non-cryptographic PRNG, then it is conceivable that an adversary could exploit some pattern in the Mersenne twister's outputs to find a shortcut to reversing the resulting hash.  Cryptographic PRNGs are designed so that despite decades of efforts, cryptanalysts have been unable to find any patterns in their outputs that are even detectable, let alone exploitable in context.

Don't use the Mersenne twister!  It's also bad as a non-cryptographic PRNG because it is expensive to initialize and requires a multi-kilobyte state, so it discourages parallelism and reproducible subtrees of computations.


RSA 896 vs 1024 vs 2048 in Javascript? I am currently working on a secure messaging website and I had been using RSA 2048 for encryption, decryption and signing of messages but I found it to be EXTREMELY LAGGY so i've moved to 1024.

I did a timing test and these are my results (this was a test of generating a private key from the same string in cryptico.js):

2048 | 6403ms (6 seconds)
1024 | 515ms (0.5 seconds)
 896 | 89ms (0.08 seconds)

I would like to know if if 896 or 1024 are un-secure for use with messaging and what the best key size would be?

In common cryptographic protocols there is only a need to generate RSA asymmetric keys now and then, say once a year. The key pair generation does not have to take place in the same environment either; e.g. you could use openssl command line if that is available. Note that RSA key pair generation time depends on finding large primes; the runtime is not static - it changes on each run.

If your protocol does have to rely on asymmetric key generation then you would do well to switch to Elliptic Curves. Elliptic curve key pair generation is very fast and private key operations are faster as well. Verification is slower than RSA though, at similar security levels.

Try e.g. the BrainpoolP256r1 named curve. Warning; EC crypto is not for the weak of heart.


Coppersmith's method implementation suppose i have two equations:
$$ (m)^{3} \bmod n = c_{0}$$
$$(m + 2^{k}r + d) \bmod n = c_{1}$$
The values($c_{0}, c_{1}, k, d$) are known.
I wanted to retrieve r (ofc $|r| < n^{\frac{1}{9}})$
Using resultant on equations gives me equation of 9 degree.:
$$w(x) = x^{9} + 3(c_{1} - c_{0})x^{6} + (3c_{0}^{2} + 21c_{0}c_{1} + 3c{1}^{2})x^{3} + (c_{1} - c_{0})^3 \bmod n = 0$$    , where x is $2^{k}r + d$
(as usual with coppersmith method). After substitute x with $2^{k}r + d$ and  change polynomial to monic i have polynomial of 9 degree w(r).

My question is that:
How can i use coppersmith attack? I tried sagemath small_root() but it dosnt return r(it return it only in special case when d = 0, and polynomial of 9 can be cast to polynomial of 3- bc it have only nonzero coefficient on $ r^3, r^6, r^9 $. Can my goal be achieved by changing implementation of small_root or by other mathematic  transformation?

Example:

N = 55555
R = Zmod(N)
P.<x> = PolynomialRing( R, implementation='NTL' )

for k in range(1,5):
f     = (x-7)^k*(x-5)*(x-43)*(x-273)    # 7, 43, 273 are here for making 2 a root
d     = f.degree()
roots = [ r for r in R if f(r) == R(0) ]
info  = ( str(roots) if len(roots)<10
          else str(roots[:10]) + ( '... (totally %s roots)' % len(roots) ) )
print "k=%s" % k
print "          ROOTS: %s" % info
print "    SMALL ROOTS: %s" % f.small_roots()

Code above doesnt return 2 even if it meet condition for Coppersmith's method.

Coppersmith's method, parameterized by $\epsilon$, finds all roots $\le \frac{1}{2} n^{\beta^2/\delta - \epsilon}$ to a polynomial $f(x)$ of degree $\delta$ modulo an unknown factor of $n$ of size $\ge n^\beta$. In your case, $\beta = 1$ and $\delta = \{4,5,6,7\}$.

Sage defaults $\epsilon = \beta/8$, which in your case would be $0.125$. However, $55555^{1^2/\{4,5,6,7\} - 0.125}$ is, respectively, $\{1.96, 1.13, 0.79, 0.61\}$. Only the first (almost) respects the bound. But if you tweak small_roots with an appropriate $\epsilon$, e.g., f.small_roots(epsilon=0.02), you should get more satisfactory answers.


HSMs: Encrypt/Decrypt - But Not Read or Export Key Can HSMs be configured to store a key, and allow encryption or decryption with said key, but prevent any export or backup of the key itself?

We're basically trying to develop a system using asymmetric encryption to perform some custom signatures. We ultimately want a black box where a user inputs some plaintext and gets out the ciphertext, but is unable to access the key used to encrypt.

Can HSMs be configured to store a key, and allow encryption or
  decryption with said key, but prevent any export or backup of the key
  itself?

Yes, because that's precisely what HSMs are designed to do*. Assuming of course you don't mind your public (encryption) key being exportable, but if you don't want that, just get an HSM that supports symmetric encryption.

*: Actually more often than not you don't want your high-value or encryption keys to be completely without backup as to allow recovery of plaintexts or continuation of operation in case the HSM dies, which is why HSMs tend to have mechanisms that allow to securely backup keys, unlike smart cards which instead require you to backup keys before putting them onto the card.


How does NaCl Poly1305 implementation do modular multiplication? The NaCl ref implementation of Poly1305 performs modular multiplication to calculate a polynomial $\mod 2^{130} - 5$ using the following modular multiplication function:

static void mulmod(unsigned int h[17],const unsigned int r[17])
{
  unsigned int hr[17];
  unsigned int i, j, u;

  for (i = 0;i < 17;++i) {
    u = 0;
    for (j = 0;j <= i;++j) u += h[j] * r[i - j];
    for (j = i + 1;j < 17;++j) u += 320 * h[j] * r[i + 17 - j];
    hr[i] = u;
  }
  for (i = 0;i < 17;++i) h[i] = hr[i];
  squeeze(h);
}

... where squeeze() is a reduction. A sequence of mulmod() operations is rounded off with a freeze() operation:

static const unsigned int minusp[17] = {
  5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 252
} ;

static void freeze(unsigned int h[17])
{
  unsigned int horig[17];
  unsigned int j, negative;

  for (j = 0;j < 17;++j) horig[j] = h[j];
  add(h,minusp);
  negative = -(h[16] >> 7);
  for (j = 0;j < 17;++j) h[j] ^= negative & (horig[j] ^ h[j]);
}

This implementation has no documentation, and has been copied literally to various projects (the code above is actually from the libsodium fork).

I've compared this to the various multiplication algorithms on Wikipedia, Montgomery Reduction and Daniel Bernsteins explicit CRT method but I don't recognise it as any of them.

The most basic implementation of the overall Poly1305 using gmp simply uses add/mul/mod operations, so there's nothing that esoteric in the main loop.

The reduction and the freeze seem to indicate this is some kind of residue number system but I can't find explicit descriptions of how that would work.

One of Daniel Bernsteins motivations when writing this was probably to have a constant time implementation, if that helps identify the algorithm.

Does anyone recognize the algorithm being used here, and know of/can provide a complete explanation of it (i.e. one that explains how the magic numbers 320 and minusp are derived, and the basis for all xor operations in the freeze)?

Numbers get represent as in base 256, i.e. $h = \sum_{i=0}^{17} h_i \cdot 256^i$. Since ints are used which are significantly larger than bytes you don't need to propagate carries immediately.

If you forget about modular reduction, then the $i$th digit of the result is computed as $\sum_{j=0}^i h_j\cdot r_{i-j}$. Apart from the lack of carry this is pretty much the same as schoolbook multiplication.

Now to take modular reduction into account you take the high bits of the result starting with bit 130. Now you can shift these 130 bits to the right, multiply them by 5 and add it to the unreduced result. Now shifting to the right by 130 bits can be done by shifting to the right by 17 bytes and then shifting 6 bits to the left. Shifting 17 bytes to the right is done using index arithmetic in r[i + 17 - j]. Shifting 6 bits to the left is equivalent to multiplying with 64. Combining that with the multiplication with 5, gives you a multiplication by 320.

for (i = 0;i < 17;++i)
{// compute the i-th byte of the output
    u = 0;
    for (j = 0;j <= i;++j) u += h[j] * r[i - j];// schoolbook multiplication
    for (j = i + 1;j < 17;++j) u += 320 * h[j] * r[i + 17 - j];// 5 * overflow >> 130
    hr[i] = u;
}

So the first inner loop is the contribution of those digits that didn't overflow, and the second inner loop the contribution of the overflow.

freeze seems to simply be:

if(h > p)
    return h - p;
else
    return h;

Except it uses bitwise operations to avoid the branch. minusp is $2^{8 \cdot 17}-(2^{130}-5)$, i.e. it simply represents $-p$. It can be used to reduce modulo $p$ if the input is less than $2p$.

Since the individual elements of h can be larger than 256 but are in base 256 you need to propagate carries at the end of each multiplication. This is done using squeeze. Now after propagating the carries you get a number between 0 and $2p-1$. Having a slightly too large value as the result of an intermediate step isn't a problem, so no further reduction happens by default.

But at the of the MAC you need a number between 0 and $p-1$, so freeze is used as final reduction.


Tweaked Square Roots and Rabin-Williams I'm reading Bernstein's RSA signatures and Rabin–Williams signatures: the state of the art. In section 6, Bernstein states:

  Recall that Rabin’s system needed to try several values of r, on
  average about 4 values, before finding a square H(r,m) modulo pq. The
  Rabin–Williams system eliminates this problem by using tweaked square
  roots in place of square roots. A tweaked square root of h modulo pq
  is a vector (e, f, s) such that e ∈ {−1, 1}, f ∈ {1,2}, and efs2 −h ∈
  pqZ; the signer’s secret primes p and q are chosen from 3 + 8Z and 7 +
  8Z respectively. Each h has exactly four tweaked square roots, so each
  choice of r works, speeding up signatures.

If I control key generation, then I can ensure p and q are chosen from 3 + 8Z and 7 + 8Z respectively, and I can possibly use the tweaked roots. Do tweaked roots violate P1363? What I might be really asking is, does an exponent of 2 run afoul of P1363, but I'm not sure at the moment.

If I cannot use tweaked square roots and/or an exponent of 2, then what are the remaining options? Is it principal roots and Jacobi?

If I load a private key generated by another library and it does not satisfy the conditions on p and q, then what are the remaining options? Is it principal roots and Jacobi?

My apologies for asking. I don't have a copy of the P1363 standard, so I'm not sure what the potential pain points are in using the algorithm described by  Bernstein.

The ultimate goal of the exercise is to remediate CVE-2015-2141 (Evgeny Sidorov paper here). I'm trying to observe P1363 but avoid Jacobi.

An older copy of P1363 Public Key Cryptography was used below. In may (or may not) reflect the current state of affairs.

It also uses Bernstein's RSA signatures and Rabin–Williams signatures: the state of the art.

  Do tweaked roots violate P1363? What I might be really asking is, does an exponent of 2 run afoul of P1363, but I'm not sure at the moment.

No. The requirements IEEE places on them in 8.1.3.2 RW key pairs is:

  An RW public key consists of a modulus n, which is the product of two
  odd positive prime integers p and q, such that p ≡⁄ q (mod 8), and an
  even public exponent e (2 ≤ e < n), which is an integer relatively
  prime to (p – 1)(q – 1)/4. [Note that these conditions imply that p ≡
  q ≡ 3 (mod 4); moreover, one of the primes is congruent to 3 (mod 8)
  and the other is congruent to 7 (mod 8).]

So IEEE requirements are witness to tweaked roots.

  If I load a private key generated by another library and it does not satisfy the conditions on p and q, then what are the remaining options? Is it principal roots and Jacobi?

If its satisfies IEEE requirements, then one prime ⊂ 3 + 8Z, and the other prime ⊂ 7 + 8Z.

If I relax requirements to those surveyed by Bernstein, then I only need to satisfy p, q ⊂ 3 + 4Z. In this case, the efficiency of tweaked roots is lost and it looks like Jacobi is needed.

While its not readily apparent, Jacobi is needed for the blinding that gets applied. Its not strictly required for the mathematics, but it is needed for the cryptography. You can see an example of it in practice in Sidorov's Breaking the Rabin-Williams digital signature system...:

do
{
    r.Randomize(rng, Integer::One(), m_n - Integer::One());
    rInv = modn.MultiplicativeInverse(r);
}
while (rInv.IsZero() || (Jacobi(r % m_p, m_p) == -1) || (Jacobi(r % m_q, m_q) == -1));


Is it possible for a cryptographic algorithm to limit the number of times a package/ciphertext can be decrypted? I got the idea from Eve Online's BPCs (Blueprint Copy). The in-game explanation is that the license to manufacture a copy of a starship is limited to X times, and afterwards the BPC is automatically corrupted.

I understand that the resulting plaintext can be copied after decryption any number of times, rendering the limit moot, I was just wondering if its possible.

Cryptography itself cannot solve this problem. This problem has long been studied in the field of copyright management to prevent piracy.

The main issue is that it is difficult to keep a state in the ciphertext that records how many times the ciphertext has been decrypted. Even if you can, there is no way in practice to prevent someone reverting the state. I.e. you decrypt, then throw away the new ciphertext, then decrypt using the old ciphertext again.

There have been some interactive protocols designed in the past that use an external trusted server to track the number of decryption. This may work but add some other problems such as privacy (you are essentially tracking the user).


Two-way secret sharing for authentication? Secret sharing, using methods such as Shamir's Secret Sharing allows for t out of n shares to recreate a secret.

For authentication, the secret can be a user ID. A client with a logged-in user can store a token holding both a user ID and secret share. A server can hold another secret share for each user ID.

When requesting something that requires authentication, the client can send the user ID along with its' secret share. The server can use the client share and its' own share for the user to recreate the secret user ID. If the recreated user ID matches the ID that the client claims to be, then the server can proceed to fulfill the request. If not, then the request can be rejected.

Is this authentication scheme secure? If an adversary were to intercept a secret share for a user, would anything other than the user be compromised? Does this method have any practical use?

This scheme is no different from standard password-based authentiation / standard cookie-based authentication:

You have a token (call it "password", "cookie" or "share") and an ID (call it "username"), you send it to the server, the server does some processing using additional values only it knows and gives you a yes / no answer for whether or not you are authenticated.

For classic passwords, this would be password-hashing with a DB-stored salt and comparison to the stored salt.
For cookies, this would be either a static comparison or an integrity check on the cookie server-side with a server-side static key.
For the given scheme, this is the secret-recovery and verifying whether the recovered content matches a specific format.

  Is this authentication scheme secure?

It is as secure as the standard approach of sending a username and a password. So it usually works, especially if your channel is authenticated, eg using server-authenticated TLS, anyways.

  If an adversary were to intercept a secret share for a user, would
  anything other than the user be compromised?

Well, if the server-side shares are user-dependent and the shares are unrelated / independent, then obviously nothing can happen to the others if one is compromised. The exception being of course if the user in question can log-in as an admin or something and just read-out or modify the shares or the received shares.


decryption many time pad I have eleven ciphertexts that were encrypted with the same key (which I don't know). I want to decrypt the last ciphertext. I read similar question like Many time pad attack but I can't solve my problem with their answer.

I'm new in Crypto can anyone tell what can I do?

I know when XOR two ciphertext (Let's assume that the plaintexts consist only of spaces and ASCII letters) if both of them were space the result is null. If one of them was space and another was ASCII we have a new ciphertext. If both of them were ciphertext we have new word that is XOR of orginal message but how can I reveal the plain-text?

This sounds suspiciously like the first extra credit assignment out of Dan Boneh's Cryptography I on Coursera.  Dan gives you a great hint in the assignment listing for this one.  Take a look at an ASCII chart and note what happens when you XOR something with space rather than with an alphanumeric.

Once you've got that sorted out, your best bet is to XOR things together, as you suggest, and use the knowledge gained from Dan's hint on XORing with space to build a histogram of candidate plaintext characters for each position.  My first cut at this assignment got about 85% of the characters, and filling in the rest was simple due to the common digraphs of english.


Is Triple-DES a group? I know for a fact that DES is not a group, but are any of the Triple-Des versions a group? Why, or why not?

No, they aren't a group.

Justification: We know that the subgroup generated by DES is very large.
If (any of the variants of) 3DES formed a closed group, then the subgroup generated by 3DES would be no larger than $2^{168}$.  We know the latter is not the case.  Therefore, the former is not the case, either.

Also, for the EDE variants of 3DES, it is easy to see that the size of the subgroup generated by 3DES is the same as the size of the subgroup generated by DES (consider what happens with EDE-3DES when you set all three subkeys equal to each other; the result is equivalent to plain DES).


What is the difference in exchanging the Enigma rotors in their slots? I have a question regarding the exchange of the rotors in a enigma machine.

I know that there are 3 slots and that up to 8 rotors can be used in those slots. What I don't understand is, as all the rotors have 26 letters each (they are  equal), what is the difference in exchanging the rotors in the slots?

They may look equal but in fact each rotor defines a different letter substitution. A letter substitution is a function that converts each of the 26 letters into another letter. For example $a\rightarrow z$, $b\rightarrow x$, $c\rightarrow y$ and so on. There are many ways this can done. Therefore, exchanging the rotors changes how each letter is substituted in the cipher.

Furthermore, each letter to be encrypted actually goes through all three rotors one after the other, being substituted each time. Also the rotors rotate so that this substitution function changes every letter. This rotation shifts the letter substitution so if in the initial position $a\rightarrow s$ then one rotation along would substitute $b\rightarrow t$ since $b$ and $t$ are the next letters from $a$ and $s$ respectively.

There is other stuff such as reflectors and custom wiring but that is the basics.


Hierarchical Encryption Is there a way to setup a hierarchical encryption using public key encryption?

Let's say a higher level user can decrypt messages encrypted by lower level users. Is that possible?

I guess it is only possible to do with hierarchical key management, like the higher level users have access to the lower level user's keys.

Is there any other option to do something like this?

Yes, this is possible.

The Bresson-Catalano-Pointcheval scheme (link) is a sort of hybrid of the ElGamal and Paillier encryption schemes. The upper-level user knows the factorization of the modulus. The low-level user does not know the factorization of the modulus, but he does know the Diffie-Hellman contribution. The upper-level user can perform decryption using the prime factors of the modulus. The lower-level user can perform decryption using the secret Diffie-Hellman value. Two distinct lower-level users cannot decrypt each other's ciphertexts but the upper-level can decrypt everything.

Also, checkout BIP32 (link). This proposed scheme allows a user to generate a tree of secret keys and matching public keys. He can communicate the secret key of one particular branch to another user who will be able to decrypt all ciphertexts encrypted using public keys from that branch. However, this second user will not be able to decrypt ciphertexts from other branches. The original generator of the larger tree retains the ability to decrypt anything (as long as the message was encrypted using a public key from that tree).


Is there a term for "bootstrapping" encryption by storing an encrypted key? Say you want to encrypt a large file, perhaps a backup of a database. Encrypting the file will naturally take some time, due to the amount of data.

Now, if at any point you want to change the password protecting the file, a simple implementation would re-encrypt the entire file.

Another solution is to generate a key K, and use that to encrypt the file. Then encrypt K based on the password, and store the result with the encrypted file (perhaps in some meta data). Now, changing the password only requires a decrypt and re-encrypt of K using the new password, making the operation much much faster.

Is there a name for this kind of design?

Jonathan

PS: Appologies for the somewhat crude description, I am not well-versed in cryptology.

The random key that encrypts the message is commonly called a Data Encryption Key or DEK using a Data Encryption Mechanism or DEM. If this key is encrypted then it is encrypted using a Key Encryption Key or KEK within a Key Encryption Mechanism or KEM. Instead of "encryption" the term "enveloping" may also be used. An encrypted key is also called a wrapped key and the key that does the wrapping is then called a wrapping key. This just names the keys and lower mechanisms, not the overall scheme.

I'm not sure if there is a single term that is used for for this type of scheme. Usually the scheme is not explicitly mentioned. It is often part of a scheme that specifies a container format such as PGP. PGP however calls the data keys session keys:

  The message is encrypted with a session key, and the session key is
     itself encrypted and stored in the Encrypted Session Key packet or
     the Symmetric-Key Encrypted Session Key packet.

Note that PGP can also directly encrypt using the key derived from the password.

I've heard the term key hierarchy used a lot in this sense. Here the password / derived key is a higher level key than the one encrypting the data itself. Multiple data keys may be encrypted or derived from the password derived key material. So you could say that the file is encrypted using a hierarchy of keys, but you would likely still be required to explain what you mean by that.


Generating Random Primes Although this has been extensively discussed around here, I'm curious whether my approach makes sense, or I should just stick to "the standard version".

I'm implementing some homomorphic encryption primitives (Paillier, Okamoto–Uchiyama etc) and, at the moment, I'm using GMP as the big number library (this may change in the future). GMP has a function called mpz_nextprime and I generate random numbers, after which I call this function on them, to get prime numbers. Is this a good approach? The other alternative would be to just generate random numbers in a loop, until mpz_probab_prime_p(number, 10) says that they are prime. This latter approach seems rather wasteful though, from a programmer's point of view.

How do you generate prime numbers with GMP or OpenSSL (or other crypto libraries like cryptlib, crypto++, etc)? I am unsure how the mpz_nextprime function works or if other libraries provide such functionality... Ideally, I should be able to just swap various big number libraries in my implementation, without changing the prime generator wrapper.

mpz_nextprime states in the documentation and source (file: mpz/nextprime.c) that it simply finds the next prime larger than the provided input. There are various methods of doing so (depending on how efficient it tries to be), but they should all produce the same answer. Looking at the code, mpz_nextprime first tests a number against a large quantity of small primes to see if they are a factor. If not, mpz_nextprime uses a probabilistic Miller-Rabin test. If the number passes the MR test, it is output as prime; if it doesn't, it is incremented by 2 and tested again. (Like OpenSSL, as mikeazo linked to.)

mpz_nextprime used to use Miller-Rabin with 10 tests, a testing strength that could be argued to be weaker than desired. But looking at the source for the current version (5.0.4) they've changed to use 25 tests, which is sufficiently safe.

Now, regarding the method: A potential problem with generating a random number and then "walking" to the next largest prime is that primes are not evenly distributed, so neither are the gaps between them. If you have consecutive primes $p_i$ and $p_{i+1}$, any randomly generated number between $p_i$ and $p_{i+1}$ would get mapped to $p_{i+1}$. Primes that follow large gaps are more likely to be chosen, and primes that follow smaller gaps would be less likely to be chosen. You would be imposing a non-uniform distribution on your choice of primes. (Read a little more here.)

That isn't necessarily a problem, though, and I can't say I've ever seen serious concern raised over it. OpenSSL probably has sufficient confidence in their method. Although, of course, the "perfect" way to ensure your have a prime number distribution that is even is to just generate random numbers until one of them is prime. Although it is probably a little slower than "increment-and-test" on average, it can't be much slower. One advantage of the increment-and-test method that it is deterministic, since there is guaranteed to be a prime between $p$ and (approximatively) $p + \sqrt(p)$, but given the frequency of primes ($log(p)$), I would think that such weak work limit wouldn't be a concern.


Easy to implement proof of shuffle I will be writing some code to implement a non interactive proof of shuffle. I intend to use it on a voting application that supports Borda voting.
The voter must prove that her vote is valid, that is a permutation of 0..c-1 where c is the number of candidates.The vote is encrypted using lifted El Gamal.
However the bibliography is huge on shuffle proofs and I am kind of lost.
Can you recommend a paper/scheme that is easy to implement, practical and correct of course.

Andrew Neff's verifiable shuffle scheme A Verifiable Secret Shuffle and its Application to E-Voting is implemented by the DeDiS Advanced Crypto Library for Go

A working example program that uses the code is the server from the Riffle anonymous communication system.

Here's a "mostly finished" standalone implementation in Go, including a paper explaining the protocol: https://github.com/cjpatton/shuffle.git


Exploiting XOR one-time-pads with alphabet size that isn't a power of 2 I realized that if the key is chosen randomly from a range that isn't a power of $2$, the one-time-pad leaks information about the plaintext.

For example, if the alphabet was the first 20 naturals, then if you see a 6 in the ciphertext, the plaintext letter must have been within [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 20, 21, 22, 23], so it couldn't have been 16, for example (it couldn't have been 20-23 either, but that's assumed since the alphabet is just the first 20 naturals). However, encrypting and decrypting will work fine.

How can this be exploited in general? If the alphabet is small you can line up all possibilities and try to come up with English words (like coming up with words from phone numbers, possibly?) What about if $n$ is larger?

Unrelated question, given this limitation, why do people use XOR instead of modular addition? Is it just because XOR is faster?

Don't think about xor over an alphabet. Only think of it over a binary encoding of an alphabet. I see what you are saying, and what you are hinting at is why Vigenere Cipher is a bad idea in general (one time pad of length $\ell$ that you use over a message of length $k$ for $\ell < k$. However, there is no "meaningful" way of implementing xor with an alphabet that is not a power of 2 as it is defined in terms of bits. Therefore, if there is no binary encoding of your alphabet, then you cannot perform xor.

As for the unrelated question, we try to avoid modular addition because 1) it is slower and 2) it makes side channel attacks possible


Secure MAC implies that probability of same tags on different messages is negligible So let any secure MAC (message authentication code) be given.

Intuitively, I think it is clear that the probability of getting the same tag on two different messages is very small, i.e. negligible. I want to prove this statement mathematically.

How can we

formulate this in an exact manner (because, negligible in what? I guess negligible in $|k|$, where $k$ is the chosen key - I am not sure about this)
(once we have a precise formulation) prove this statement?

Supposing that this probability is not negligible, we'll have to construct a PPT adversary $\mathcal A$ that, somehow, is able to "beat" the system (which would be in contradiction with the fact that the MAC is secure).

Is this a homework problem?

Here's a hint: Suppose that the probability of getting the same tag on two different messages is $p$.  Show how to construct an adversary that breaks the MAC (i.e., forges a valid tag), and that has success probability $p$.  Assuming the MAC is secure, what can you conclude about the possible range of values for $p$?


Hard instances of matrix factorization Are there any hard problems related to matrix factorization?
Suppose $E$ is hermitian with public eigenvectors such that $U^T\Lambda U = E$ with $U$ public but $E,\Lambda$ secret. Given $X$ secret, we would "encrypt" it as $EX = U^T\Lambda UX$ can you create instances such that $f(U,EX) \rightarrow X$ is not polynomial time?
I believe matrix inversion is polytime, but I am not sure if this is worst case or average case. First thing you can do is knock off the first term so $UEX = \Lambda UX$, and with $U$ public, but $\Lambda,X$ chosen perhaps to make the problem hard, is this still possible in polytime?

This is not related to your particular factorization problem (I believe), but is related to a hard matrix factorization problem (I believe). It is known as the "Lattice Isometry Problem" (or perhaps it is the "Lattice isomorphism problem" --- I will call it LIP either way). Stated in matrix terms, this problem is, given two matrices $\mathbf{B}_1, \mathbf{B}_2\in\mathbb{R}^{n\times k}$, determine if they generate isometric lattices.
A lattice generated by some basis $\mathbf{B}\in\mathbb{R}^{n\times k}$ is defined as:
$$\mathcal{L}(\mathbf{B}) = \{\vec x\in\mathbb{R}^n\mid \exists \vec y\in\mathbb{Z}^k\text{ s.t. }\vec x = \mathbf{B}\vec y\} = \mathbf{B}\mathbb{Z}^k$$
As defined, basis of a given lattice are specified up to multiplication by an (integer) change-of-basis matrix on the right, i.e. if $\mathbf{B}\in\mathbb{R}^{n\times k}$ is the basis of a lattice, and $\mathbf{U}\in\mathsf{SL}_k(\mathbb{Z})$, then $\mathbf{BU}$ is a basis of the same lattice.
Two lattices $L, L'$ are said to be isometric if they are related by an orthogonal transformation of determinant 1.
In terms of matrices, $\mathcal{L}(\mathbf{B})$ is isometric to $\mathcal{L}(\mathbf{B}')$ if there exists some $\mathbf{O}\in SO(n)$ such that $\mathbf{O}\mathbf{B} = \mathbf{B}'$.
All combined, this means that the lattice isometry problem takes as input two matrices $\mathbf{B}, \mathbf{B}'$, and attempts to factor $\mathbf{B}' = \mathbf{OBU}$ for $\mathbf{O}\in SO(n)$, $\mathbf{U}\in\mathsf{SL}_k(\mathbb{Z})$, so can be seen as a certain matrix factorization problem.
I don't know precise results for the hardness of LIP, but a certain "natural" extension of it to the ideal lattice setting becomes easier than one would hope for. This is the content of the Gentry-Szydlo algorithm, which determines whether a certain ideal lattice is isometric to $\mathbb{Z}^k$, which can also be described as "having an orthonormal basis".


Are variable-length crypto hash functions still susceptible to collisions? I just recently learned that the SHA-3 finalist Keccak allows for variable length output. As the only answer to this question states, "[it] need to have an output length at least equal to the input length," which I understand just fine. However, I'm curious if this guarantees against collisions.

Is there any work done to show or prove collision resistance gained by increasing digest length? If so, how dependent is this resistance on the hash function itself? (I'm guessing the answer to this is "highly" or "entirely".)
What are the other benefits of allowing variable and arbitrary length output?

If the math on these points is still fuzzy, is variable length output just based on the intuition that "larger problem space = harder to attack"?

Note my crypto and math expertise is very low, so please add a 'for dummies' section to any answer you write and I thank you in advance.

Is there any work done to show or prove collision resistance gained by increasing digest length?

Actually, as CodesInChaos has mentioned, the variable length versions of Keccak ("SHAKE128" and "SHAKE256") are known not to have any collision resistance beyond their security level, independent of how long we make the output.

So, what's the point?  So, as you ask:

  What are the other benefits of allowing variable and arbitrary length output?

That's because collision resistance isn't the only property we want from a random-looking function.  One such alternative use is a Key Derivation Function; this is a function that takes as input some secret data (e.g. DH shared secrets) and some public data (e.g. nonces) and converts that into session keys; these are a series of encryption and MAC keys (and as we might have several such keys, and they're of variable length, this set of session keys is long and of variable length).  Now, a number of KDFs are in use by real protocols (such as TLS), however these constructions are ad hoc, and actually rather ugly looking.  It would be nice to use a single function that's designed to do that; a "variable length hash" (or XOF, that's what NIST dubs it) may be cleaner.


What is the smallest size of the hash output? Suppose we want to make the hash pre-image resistant to 40 bit security (success chance is $2^{−40}$). What would be the smallest size of the hash output?

To get a preimage resistance of 40 bits, you need a hash with at least a 40-bit digest. Finding a preimage for an $n$-bit hash typically requires performing $2^n$ attempts. A collision for an $n$-bit hash requires $2^{n/2}$. For a 40-bit hash, a preimage requires $2^{40}$ operations and a collision requires $2^{20}$.

Note that 40 bits of preimage resistance is typically not considered sufficient for most applications!


Recommended authenticated stream cipher for minimum overhead? I'm running my TCP/IP protocol secured by encrypting each packet with AES128/CBC, bundling a SHA256 HMAC over that packet.

This causes quite a bit of space overhead for small packets, so at first I was thinking of running AES in CTR-mode and still use the HMAC, but it would be much better to run some sort of stream cipher with integrated authentication.

What are my best options?

Edit:

I should mention that failing an integrity check will always disconnect a connection.

This means re-negotiating the encryption keys, which gives each new connection a new encryption and signing key.

In other words, make a wrong guess and the keys are reset. Even with a small integrity checksum, guessing right to sustain an exchange appears to be a hard problem.

There aren't any known attacks on the PRFness of HMAC-SHA256 better than brute force.

(So you can truncate that MAC to length L where $\:\:\frac1{2^L}+\epsilon\:\:$ is an acceptable risk of forgery.)

To reduce the impact of a forgery without making the ciphertext any longer, one should use a
format-preserving encryption (FPE) scheme that is secure against one query to the encryption

oracle and one query to the decryption oracle, which are not necessarily made in that order. $\;\;\;$

Choose either $\; [b_{client} = 0 \: \text{ and } \: b_{server} = 1] \:$ or $ \: [b_{client} = 1 \: \text{ and } \: b_{server} = 0] \;$.

Let $\;\; \operatorname{pL} \: : \: \{0,\hspace{-0.03 in}1,\hspace{-0.03 in}2,\hspace{-0.03 in}3,...\} \: \to \: \{0,\hspace{-0.03 in}1,\hspace{-0.03 in}2,\hspace{-0.03 in}3,...\} \;\;$ be an injective function that can be inverted

efficiently enough. $\;\;\;\;$ For the sentence two after this one to be possible, you will also need that

for all $m$, $\: m\leq \operatorname{pL}(m) \:\:$. $\;\;\;\;$ Let $\;\; \operatorname{rL} \: : \: \{0,\hspace{-0.03 in}1,\hspace{-0.03 in}2,\hspace{-0.03 in}3,...\} \: \to \: \{0,\hspace{-0.03 in}1,\hspace{-0.03 in}2,\hspace{-0.03 in}3,...\} \;\;$ be a function that

can be computed efficiently enough. $\;\;\;\;$ Let $\;\; \operatorname{pad}_{\hspace{.01 in}m}\hspace{-0.01 in} \: : \: \{0,\hspace{-0.03 in}1\}^m \hspace{-0.01 in} \times \{0,\hspace{-0.03 in}1\}^{\operatorname{rL}(m)} \: \to \: \{0,\hspace{-0.03 in}1\}^{\operatorname{pL}(m)}$

be a sequence of injective functions that can be computed efficiently enough and satisfies

$[message$ can be efficiently computed from $\:\operatorname{pad}_{\operatorname{length}(message)}\hspace{-0.02 in}(message,\hspace{-0.02 in}randomness)]$.

$\operatorname{unpad}_{\operatorname{length}(message)}\hspace{-0.02 in}(\operatorname{pad}(message,\hspace{-0.02 in}randomness)) \: = \: message$

For all other values of $x$, $\;\; \operatorname{unpad}(x) \: = \hspace{.08 in} \perp \;\;\;$.

$\operatorname{Enc}(key,party,packetnumber,plaintext,randomness)$
$=$
$\operatorname{FPEencrypt}(\operatorname{HMAC}(key,b_{party}||\hspace{.02 in}packetnumber),\operatorname{pad}(plaintext,randomness))$

$\operatorname{Dec}(key,party,packetnumber,ciphertext)$
$=$
$\operatorname{unpad}(\operatorname{FPEdecrypt}(\operatorname{HMAC}(key,(1-b_{party})||\hspace{.02 in}packetnumber),ciphertext))$

As long as each party only encrypts and decrypts once each for each $packetnumber$, a feasible adversary will have probability $\:\: \frac1{2^{\operatorname{pL}(m)-(m+\operatorname{rL}(m))}}+\epsilon\:\:$ of violating integrity for each submitted ciphertext

of length $\operatorname{pL}(m) \:$ (and a ciphertext whose length is not in $\:\operatorname{range}(\operatorname{pL})\;$ will always decrypt to $\perp$).

  Furthermore, if the parameters are such that that probability is noticeable, then the decryptions

  of ciphertexts with length $\operatorname{pL}(m)$ that violate integrity will be computationally indistinguishable

  from independent samples from the following distributions for each such ciphertext:

  if the indicated $party$ did not output a ciphertext for that $packetnumber$, then uniform on $\{0,\hspace{-0.03 in}1\}^m$

  else, the plaintext used by $party$ for that $packetnum$ with probability $\frac{2^{\operatorname{rL}(m)}-1}{2^{m+\operatorname{rL}(m)}-1}$,

  and each other member of $\{0,\hspace{-0.03 in}1\}^m$ with probability $\; \frac{2^{\operatorname{rL}(m)}}{2^{m+\operatorname{rL}(m)}-1} \:\:$.


How do you construct a practical full-domain hash function? I am looking for practical constructions for Full Domain Hash.

I have read Random Oracles are Practical by M. Bellare and P. Rogaway, the construction suggested on page 8, under "Uniformity: a technicality", but it's unclear whether that is producing a full domain hash, or just ensuring the message is well-formed using an existing hash function.

I haven't found any other information regarding full domain hash constructions.

I don't know if that counts, but authors of recently selected SHA3 function Keccak mention its ability to perform Full Domain Hashing:

  Variable output length hashing is an interesting feature for natively supporting a wide range of applications including full domain hashing [...]


How secure would HMAC-SHA3 be? It would be possible to implement the HMAC construction with (draft) SHA-3, leading to HMAC-SHA3-224, HMAC-SHA3-256, HMAC-SHA3-384, HMAC-SHA3-512 (the last 3 digits are the output size $\ell$, where $\ell/8$ is the $L$ parameter in HMAC). All that's missing to apply the familiar
$$\text{HMAC}_K(\text{message})=H(K\oplus\text{opad}\mathbin\|H(K\oplus\text{ipad}\mathbin\|\text{message}))$$
is a definition of the block size $b$, where $b/8$ is the $B$ parameter in HMAC. That is necessary to determine the size of $\text{ipad}$ and $\text{opad}$ (and above what size $K$ needs to be replaced by $H(K)$ beforehand). However, the original and improved security arguments/"proofs" of HMAC are made for the Merkle–Damgård structure, and thus do not directly apply to HMAC-SHA3.

How secure would these HMAC-SHA3-$\ell$ be? What does $b$ needs to be for each of the four $\ell$ values? What kind of security arguments/"proofs" can be made?

Would HMAC-SHA3 be any stronger than the generic sponge MAC?

HMAC is briefly discussed in the Keccak submission (section 5.1.3), but I do not understand that a proof is given or a security claim made.

Update: that makes reference to section 5.1.1 which I now read as suggesting that we should have the HMAC blocksize $b$ multiple of the so-called bitrate $r$; thus for output $\ell$ of 224 (resp. 256, 384, 512), $b$ a multiple of 1152 (resp. 1088, 832, 576). That's in agreement with these NIST slides

The Keccak submission says:

  From the security claim in [12], a PRF constructed using HMAC shall resist a distinguishing attack that requires much fewer than $2^{c/2}$ queries and significantly less computation than a pre-image attack.

Here, $c$ denotes the capacity of the sponge, i.e. the effective size of the internal state in bits.

Since HMAC is a deterministic iterated MAC (in particular, it does not use a nonce), it is always vulnerable to a generic birthday-based existential forgery attack requiring on the order of $2^{c/2}$ MAC queries (Preneel & Oorschot, 1999).

Thus, the claimed security level of HMAC-SHA3 is the same as the overall maximum attainable security level for HMAC, or any other deterministic iterated MAC construction, with the same effective internal state size.


How to calculate a hmac and cmac I'm searching for a simple description that tells me in a schematic way how hmac and cmac is calculated.
So far I found the following:
cmac = aes_encryption(hash(message), key)
hmac = hash(key, message)

The difference seems to be that cmacs are using a symmetric encryption additional to the hash-function while hmacs process the key within the hash-function itself. Is that correct?
Are there some situations when a cmac shall rather be used than a hmac?

The difference seems to be that cmacs are using a symmetric encryption additional to the hash-function while hmacs process the key within the hash-function itself. Is that correct?

There is no "normal" collision-resistant hash involved with CMAC. See below for details. For HMAC, the internals of the hash function are exploited to process the key, however it can use the hash function as a black box.

HMAC was standardized in RFC 2104 and NIST FIPS 198-1. The idea of HMAC is to exploit the common Merkle-Damgård structure of hash functions. This is done by first invoking the compression function with the pre-processed key, then using that state to process the message normally. Finally, the output of the previous step is used as a message again in the same manner as the original message was in the previous step, though this time with a different derived step.

CMAC is defined in NIST SP 800-38B which has a nice figure explaining the mode:

Where the $\oplus$ denote XOR, CIPH is a block cipher, the MSB operation is truncation, $K,K1,K2$ are keys derived from the main input key via doubling in a polynomial field.
The message is divided in blocks of at most CIPH's block size.

Are there some situations when a cmac shall rather be used than a hmac?

Yes, the typical recommendation is that if you either have hardware acceleration for a cipher or if you want to minimize code size and provide other functionality relying on a block cipher in your code.


Why would the use of Curve25519 in Dragonfly leak information? An answer explaining Dragonfly, a form of key exchange used in WPA3, has an interesting footnote:

  One final note: reviewing the Firefly RFC, I see that it would (as written) leak some information if you run in on an elliptic curve that doesn't have a prime number of points (that is, has a cofactor $h \gt 1$). If you're using (say) the NIST curves, that's not an issue; if you try to adapt it to run over (say) Curve25519, that would need to be addressed...

Why is this, and what would be leaked if using a curve without a prime number of points?

In the Dragonfly protocol on an elliptic curve, the password is mapped to a point $P$, and then both sides exchange (among other things) the values $-mP, -m'P$.

If the elliptic curve has a composite order, and in particular, has a small cofactor $h$, then it is easy, given a value $P = xG$ (where $G$ is a generator), to find the value $m \pmod h$, that is, the order (mod $h$) of $P$.

So, if an attacker observes an exchange between two legitimate parties, what he can do to test a potential password is to map it into a point $P'$, and compute the order (mod $h$) of $P'$, and the two observed values $-mP, -m'P$.  If his guess of the password was correct, then the order of $-mP, -m'P$ will always be a multiple of $P'$; if it is not, his guess of the password is impossible, and so he can remove that from his list.

Using this logic, it is likely that the attacker ma be able to eliminate approximately half of his dictionary entries by listening into one (or possibly several in a slightly more sophisticated version of this attack); this is contrary to the security goals of Dragonfly.

Also, it would be fairly easy to modify the HuntAndPeck procedure to avoid this weakness (just multiply the derived point by $h$); however the RFC doesn't specify that...


How to deniably send a value Alice has a single bit of information, b, that she wants to send to Bob (over an unalterable but possibly-monitored channel) but  in such a way that without the cooperation of Bob she cannot prove to anyone else (Eve) besides Bob after-the-fact that she sent b and not 1-b.

Is this possible? I am thinking perhaps not, because in any protocol Eve could step through the inputs Alice receives from Bob with both b and 1-b, and check which one of those the output she sends back to Bob matches. Even if the protocol is non-deterministic Alice could record the random values for Eve - but perhaps there is some way in which the random values could be set up to be trivially spoofed to indicate the other value to Eve after-the-fact (and hence Eve would not be able to trust Alice)?

By this paper, indistinguishability obfuscation is enough for that.


Should you change salt when changing password? Assume a password storage scheme using a computationally-expensive hash algorithm and a CSPRNG salt.  User ID, salt, and hash value are stored in  a table; if the table is compromised, all three values are available to an adversary.

Is there any value in computing a new salt when a user changes his password?

(I think this question only makes sense if the adversary has before and after copies of the password table, but I could be very wrong about that.)

If the attacker had already begun creating a rainbow table or is engaged in some other attack which requires knowledge of the salt, then a password change with a salt change will require the attacker to start from scratch.

Always assume the attacker has before and after copies of the password hash and salt.

If the salt is not changed, any work the attacker has done may still be applicable to the new password. It may even mean the new password is already in the rainbow table or has been cracked in some other way.


Can I securely refill a one time pad over the same connection? If you have a channel where you are communicating using a one time key, is it possible to receive additional key over that same connection without compromising security?

Naively sending it through the same encrypted channel would of course consume the pad at the same rate that you refill it, but maybe there's a more clever way?

Presumably brute forcing would yield the dictionary both when run against encrypted data and against the pad used to encypt future messages, since both look like (or are) random data.

No, using a one-time-pad to encrypt another key stream is futile, as the original key stream must be at least the same size as the message you're trying to encrypt. So the amount of bits used from the current key stream will at least equal the amount of bits transmitted. For a one-time-pad the key stream must be at least the same size as the plaintext message to achieve information theoretical security. XOR is not the only operation that encrypts the message using the key stream, but no other operation will allow a key stream smaller than the message by definition.

The more clever way is to use a stream cipher. A stream cipher generates the key stream from a statically sized key. This key can be any size, but sizes of 128 bits to 256 bits give the required key strength against brute force attacks. A stream cipher doesn't provide perfect security but it does give you practical security - even against quantum computing based analysis, given a large enough key size.

For transport security you also want to protect against leaking information by message size, plaintext oracles and side channel attacks - particularly time based side channels (presuming that the processor itself is in a secure location).

Furthermore you probably want to protect your message integrity and authenticity by using an authentication tag (using a MAC or AEAD scheme). A one-time-pad - by itself - does not provide integrity or message authentication.


Bleichenbacher attack, binary search, formula for $s_i$ Reading an excellent article explaining Bleichenbacher attack I came across the following statements under the formula for $s_i$:

  if we pick $r ≥ 2(bs_{i-1} - 2B) / n$, we obtain

  $(2B + 2(bs_{i-1} - 2B)) / b = 2s_{i-1} ≤ s_i$

Can anyone explain to me how the previous equality is obtained? If we try to reproduce it, we'll obviously get:

$(2B + 2bs_{i-1} - 4B)/b=(2bs_{i-1} - 2B)/b=2s_{i-1} - 2B/b$

Why the authors conclude that the result behind is equal $2s_{i-1}$? Moreover, in the code later they use

r = ceil((b*si - B2)*2,n) # starting value for r

as a starting point for $r$...

Okay, I examined this for a while, and I'm pretty sure this is more of an oversight. They probably wanted to take $r\ge2bs_{i-1}-2B=2(bs_{i-1}-B)$. The same correction should go into the code. (Taking $r=2bs_{i-1}-2B$ is indeed too low a value and does not ensure the doubling of $s_i$ at every successive step, so your observation is correct.)


Is python a secure programming language for cryptography? I know Python is a powerful programming language but is it secure for cryptography? I mean is it possible to reverse engineer the program (written in python) and discover the algorithm of cryptography or other things?

Python is a scripting language, so if you've got the program, you usually also have the source code. So you don't even have to reverse-engineer. That doesn't matter much for two reasons:

other languages are pretty easy to reverse engineer (or they are complex for both the programmer and the attacker);
the algorithm does not have to be kept safe anyway, due to Kerckhoffs' principle

Now the above does not directly make Python suitable for cryptography. One of the main things about cryptography is security. Without a secure programming environment, you can have any strength of cryptography, and still not have a secure system.

Languages have many constructs that make them more or less suitable for security and cryptography, so I show a few and indicate how Python fares:

type system: it has a dynamic type system with strong typing - with regards to security this is not as good as a static type system but it is better than weak typing;
character encoding: not good, python may confuse bytes and characters if specialized classes are not used;
operations on bytes, 16 bit words, 32 bit words and 64 bit words: not good, python simply regards everything as an unbounded number;
operations on large integers: good; modular exponentiation can be done directly on numbers using pow();
destruction of keys & state: this is a problem for any language that doesn't directly manage it's memory; Python is not likely to fair better than the rest, it may be hard to prove that keys can be safely destroyed while the program is running.

Finally, in general people like their systems to be fast. Unfortunately, scripting languages are often not fast with regards to binary operations required for symmetric cryptography (SHA-256, AES). Interpreted languages such as Java are already much faster, but languages such as C and assembly are faster than that (when used correctly).

More important for regular use of cryptography is the maturity of cryptographic support provided in libraries. Python has a relatively well kept crypto libraries called PyCrypto, PyOpenSSL available; those libraries however are mainly implemented mainly in C. These and other libraries are discussed here. One advantage of PyOpenSSL is that it should be possible to securely store and use keys from a hardware module (for instance a smart card or HSM).

Note that side channels may apply when using Python for direct implementation of cryptographic primitives. I'd say that Python is especially OK for fast prototyping of cryptographic primitives rather than library creation.

All in all, I would summarize that Python is OK-ish, but not great for cryptography if such a generalist statement can be made at all.


Decrypting LFSR, knowing the beginning of the cyphertext, and nothing else I have a cipher-text in binary, I know the beginning of the plain-text. I know that it is encrypted using LFSR, and I know nothing else.
How can I attack, and decrypt it?
What I have tried;
I converted the beginning of my plain-text to binary, which had a length of 84. My ciphertext's length is 952. I've got the first 84 bits of my cipher-text, XOR'd it with the known part of plain-text in binary, assuming that this would give me the first 84 bits of my key-stream, which was not periodic.
After that, I have used the Berlekamp-Massey algorithm with that 84 bits of the key-stream, to find the smallest possible connection polynomial that could be used to get it. (I don't know if it was definitely the connection polynomial for my key-stream, knowing that the long gap is huge and the known keystream is not periodic, it probably is not)
I then tried some shenanigans but nothing worked, I couldn't take any further steps. I've tried using the known cipher-text as the initial sequence and the polynomial I've got from the BM algorithm as the connection polynomial to generate another key, but that neither worked for my known plain-text or the rest, therefore assuming this was not a correct method to continue.
What further steps can be taken to decrypt this cipher?

It's used the right tools, apparently with the right input, but missed how to use their output.
If, when given the first 84 bits of keystream, a proper Berlekamp-Massey implementation outputs a polynomial of degree 27, then it also has found a 27-bit initial state, such that the 27-bit LFSR with this initial state has output starting with the 84-bit keystream. And one can have high confidence ($p\approx1-2^{2\cdot27-84}>99.9999999\%$) this is not by accident.
Next steps:

Understand where in the Berlekamp-Massey code used lies the 27-bit initial state, and output that. Basically, if the LFSR convention is that of a Fibonnaci LFSR, that initial state is the 27 first terms of the input sequence analyzed (which is why it is often not an explicit output).
Make an auxiliary program that implements this LFSR and produces keystream.
Verify correctness of the above by checking that the first 84-bit output is the input to the Berlekamp-Massey code / the known keystream. If not, fix whatever is wrong.
Generate as much keystream as needed to decipher.

Note: I recall I helped fix Berlekamp-Massey code in C. Try it online!. And someone wrote some elements of the auxiliary program (but it's non-trivial to link the two). Help on use of a particular tool is off-topic, especially for CTF or homework. And writing the auxiliary program (perhaps as an extension of the  Berlekamp-Massey code) is a simple and essential exercise.


Why do $p$ and $q$ have to be different in RSA? When using RSA cryptography, it is possible to have the decrypted message and the initial message the same when $p$ and $q$ are the same. So why are they always different?

Because factoring $n$ where $n=pq$ and $p=q$ is really, really easy, take a square root. If you can factor $n$, you can break RSA. Therefore, having $p=q$ is detrimental to the security of RSA.


Build a scheme that is CCA secure but not authenticated Trying to understand a solution from this paper:

Summary:

$E'_K=0||E_K(m)$ and $D'_K(0||c)=D_K(c)$ and $D'_K(1||c)=1$
IND-CCA secure (how?) as $1||c$ and $0||c$ are are easily decryptable
Not authenticated because $(1,c)$ is easy to decrypt because it will equal to 1. So, an adversary can append 1 to any ciphertext so that $1||c$ and say it was from him

Could someone explain what step 2, I can see why they are easily decryptable but cannot make the link between that and IND-CCA. My confusion is that the decryption looks like IND-CCA insecure because you can easily append 1 to c to get 1, so adv will always win.

Note that the goal of the adversary in the IND-CCA game is not to be able to output some valid ciphertext (i.e., a ciphertext that decrypts to something other than $\perp$), but rather to guess the secret bit $b$ on which the security game is parameterized (see the definitions here).

Since submitting a ciphertext of the form $1 || C$ to the decrypt oracle $D_K(\cdot)$ does not leak any information about the secret bit $b$,
this informally shows that the security of $(G,E',D')$ essentially boils down to that of $(G,E,D)$.

Stated more formally as a reduction: if some adversary $A$ could break the scheme $(G, E', D')$ (in the IND-CCA sense), then we can come up with an adversary $B$ that breaks the underlying scheme $(G,E,D)$. Namely, $B$ runs $A$ and whenever $A$ makes a call to its left-right encryption oracle $LR'_K(M_0, M_1)$, then $B$ responds with $0 || LR_K(M_0, M_1)$, where $LR_K(\cdot, \cdot)$ is the left-right oracle in $B$'s own game. When $A$ asks $0 || C$ to its decryption oracle $D'_K(\cdot)$, then $B$ responds with $D_K(C)$, where $D_K(\cdot)$ is the decryption oracle in $B$'s own game. Finally, if $A$ asks to decrypt $1 || C$ and $C$ as never been used before, then $B$ simply responds with $1$, otherwise $B$ responds with $\perp$. In the end, $B$ outputs the same bit as $A$.

Created in this way, $B$ perfectly simulates the oracles $LR'_K(\cdot, \cdot)$ and $D'_K(\cdot)$ for $A$, and thus wins its IND-CCA game against the underlying scheme $(G,E,D)$ with at least the same probability as $A$.

Incidentally, what you have noticed is that the scheme $(G,E',D')$ is not INT-CTXT secure. This security notion does ask the adversary to come up with some ciphertext that decrypts to something other than $\perp$. A standard result (shown in the paper linked to above) is that IND-CPA + INT-CTXT $\implies$ IND-CCA. So what your example shows is that the converse of this is not true.


Faster alternative to HKDF HKDF is used in one of my projects to derive separate keys from a common master key. But profiling has shown it to be the performance bottleneck under certain circumstances. Is there any faster alternative? The only things I get after googling "key derivation function" are HKDF and password stretching algorithms like PBKDF2 or scrypt.

If you are using the full HKDF each time, you could possibly save time by only using the Extract portion once and Expand once per derived key. That could even halve the total time taken, if you had a worst case situation.

Another speedup possibility within HKDF is to use another hash. Either a faster hash or one that matches the required key length better. For example, if you are generating a 256-bit key you would likely not want to use SHA-1 even though it is faster than SHA-256, because you would need two serial iterations.

Depending on the use case, you might also want to look into using KDF1 or KDF2, which are faster hash-based KDFs. They are defined in ISO18033, but KDF1 is also in RFC 3447 (appendix B.2), under the name MGF1.

However, as explained in the HKDF paper (pdf), the Expand scheme could work with any PRF. That means that for best performance you could roll your own version by replacing HMAC with a block cipher that you have in hardware (e.g. AES-NI on some new CPUs), since secure block ciphers are indistinguishable from a PRF up to the birthday bound.


What is the efficiency of the new Crown Sterling semiprime factoring method? In their press release a company called Crown Sterling describes they are working a paper that

  includes four different geometric and arithmetic methods for public key (semiprime) factorization and one of the methods titled, “The Reciprocal Factoring Method” includes an analysis of reciprocal values of public keys and their embedded private keys (prime factors) found within their period decimal extensions.

According to the CEO's Instagram, the factoring method is quite simple: search for the primes in the decimal expansion of the reciprocal of the semi prime. It doesn't hold true for all primes, and I get that its not even remotely efficient enough, but while the controversy is ongoing, it would be helpful to know just how inefficient their method is.

The bozos at Clown Sterling have adapted the advanced technology of bogosort to factoring: randomly blow a candidate solution out your nose and check whether it works.  For a semiprime $n$ chosen by modern RSA key generation methods, there are approximately $\sqrt n$ candidate solutions to check, which is also the expected cost of this method.  For instance, with RSA-2048, it will cost approximately $2^{1024}$ trial boogers.

The technical term for everything about these clowns is ‘uncastrated male bovine stool’.*  There is no more merit to the technical claims of Crown Sterling than there is to Treadwell Stanton DuPont.  The company's method is quite simple: the CEO Robert Grant is a scam artist who presumably uses technobabble like this to defraud unwary investors, and who sank some of the money into buying the prestige of a BlackHat talk slot (which is something that BlackHat really shouldn't offer) in order to drum up more hype around their scam.

And then they act the victim in a bogus narrative of persecution by the dominant establishment when subjected to universal derision by any competent cryptographers who bother to look at the nonsense.

So, what did these scam artists claim?

In their arXiv draft (which they proudly claim Cornell University published even though anyone can upload a draft to the arXiv with no peer review), Robert Grant and Talal Ghannam:

(§II) made the remarkable observation that every prime above 3 is congruent to $\pm1$ modulo 6 (proof: $2 \mid 6k \pm 2$ and $3 \mid 6k \pm 3$; this is the newest result they recycled, several centuries old—first published no later than 1509 and first proven no later than 1603, according to Dickson pp. 7–9, but quite possibly known earlier because it's so obvious);
(§III) reinvented the sieve of Eratosthenes several thousand years late;
(§IV) discovered that $x \mapsto x \bmod 9$ is a ring homomorphism (a technique known since antiquity and more commonly called ‘casting out nines’), and figured out that if $x \equiv 3 \pmod 9$, $x \equiv 6 \pmod 9$, or $x \equiv 9 \pmod 9$, then $x$ can't be prime (proof: duh);
(§VI) deluded themselves into thinking if $pq \equiv 1 \pmod{10}$ then either $\{p \bmod 10, q \bmod 10\} = \{3,7\}$ or $p \equiv q \equiv 1 \pmod{10}$ (counterexample: $19\cdot 29 = 551$; perhaps they used ‘proof by trying numbers until I got bored’); and
(Appendix) proved that $p \equiv \pm 1 \pmod 6$ implies $p^2 \equiv 1 \pmod{24}$, a trivial consequence of the Chinese remainder theorem first stated no later than nearly two millennia ago (proof: $p \equiv \pm1 \pmod 2$ so $p \bmod 8 \in \{1,3,5,7\}$ so $p^2 \equiv 1 \pmod 8$, and $p \equiv \pm1 \pmod 3$ so $p^2 \equiv 1 \pmod 3$; hence by CRT, $p^2 \equiv 1 \pmod{3\cdot 8}$).

Earthshattering stuff, I'm sure you'll agree.
In March, they published a press release as Strathspey Crown LLC announcing their findings with no additional technical claims.
In August, at BlackHat, they spent 115 000 USD for an unreviewed talk slot to debut Time AI, which

  uses five dimensions of encryption, leveraging biometrics, music’s infinite variability and dynamic change to secure your data

and is sometimes quantum and which was predictably laughed off the stage at considerable cost to BlackHat's reputation as a purveyor of fine corporate stoogery.

(Crown Sterling have since sued BlackHat because people were mean to them and BlackHat did nothing to stop people from pointing out their idiocy when they presented it at the BlackHat podium they bought.)
In September, they held a live stunt where they alleged to factor a 256-bit semiprime on a laptop on stage.

For perspective, this record was surpassed no less than a quarter century ago by Dixon & Lenstra, who reported solving a 110-digit/364-bit factoring challenge.  The 129-digit/426-bit factoring challenge announced in Scientific American by Martin Gardner in 1977 with the advent of RSA was solved in 1994 by Atkins, Graff, Lenstra, & Leyland revealing the magic words Squeamish Ossifrage.  Today you can factor a 512-bit integer for 100 USD using CADO-NFS and msieve on Amazon EC2.

Well, actually, Grant walked back the claim that it was a laptop (apologies for Twitter link to screenshot of Instagram; I don't deal in Instagram so I can't link to the page directly).  But randos on Twitter showed how you, too, can break this record in the privacy of your own living room on your own laptop in comparable time.

The fraudsters gave no details about the alleged novel factoring algorithm actually used in the demonstration.  A poor soul—pour one out for him!—who actually bothered to watch the video (which I'm not linking because I don't want to give these fraudsters any clicks) noted that some of the output of the alleged program appears to be output from CADO-NFS.
What about the Instagram post?  (Always a highly reputable venue for mathematical and cryptologic publication!)  The claim seems to be that you can find the factors of $pq$ in the decimal expansion of $1/pq$.

First, it doesn't always work.  For example, $1/(11\cdot13) = 0.\overline{006993}$ in which neither factor 11 nor 13 appears.  But one might wonder whether it probably happens.

The period of the decimal expansion of $1/pq$ for prime $p$ and $q$ is $\operatorname{lcm}(\operatorname{ord}_p 10, \operatorname{ord}_q 10)$, which is usually not much smaller than $pq$.  If we model the expansion as a uniform random digit string $pq$ (not $\log_{10} pq$, but $pq$) digits long, what's the probability of finding particular a $\log_b p$-digit string, namely $p$, in it?  The expected number of times that any particular $m$-character needle appears as a substring of a uniform random $h$-character haystack in a $b$-symbol alphabet is $(h - m + 1) b^{-m}$ (proof: exercise for reader).  Here $m \approx \log_b p$ and $h \approx pq$, so this is about $$(pq - \log_b p + 1) b^{-\log_b p} \approx q.$$  Cursory random experiments suggest that this is a reasonable model for the substring search, and I know of no theory that would suggest otherwise; it is up to the fraudsters to put up or shut up if they can prove anything better than this.

In other words, in this model, there's a reasonable probability that the the method works if you're willing to search through about (say) $2^{1024}$ possible candidate factors of the 2048-bit semiprime in question.  Which, as it happens, is essentially random trial division.  The fraudsters make it look easy by showing a screenshot with the answer already highlighted in a selectively cropped fragment that skipped over thousands of digits—about as many digits as the value of the numbers we're searching for.

In brief, these clowns—who are trumpeting thousand-year-old mathematical results on a preprint host open to the world as publications by Cornell University—appear to have at best caught up to the state of the art in factoring records from a quarter century ago by copying an alleged algorithm into software that looks just like off-the-shelf factoring software…or they're just using the off-the-shelf factoring software to wow an audience of chumps.

* Stack Exchange may have a profanity filter that has the unfortunate effect of interfering with using certain precise technical terminology.


What constitutes 1 AES round? I'm a little confused as to what constitutes a single AES round.  Most sources say it's this:
t0=Te0[s0>>24]^Te1[(s1>>16)&0xff]^Te2[(s2>>8)&0xff]^Te3[s3&0xff]^rk[4];
t1=Te0[s1>>24]^Te1[(s2>>16)&0xff]^Te2[(s3>>8)&0xff]^Te3[s0&0xff]^rk[5];
t2=Te0[s2>>24]^Te1[(s3>>16)&0xff]^Te2[(s0>>8)&0xff]^Te3[s1&0xff]^rk[6];
t3=Te0[s3>>24]^Te1[(s0>>16)&0xff]^Te2[(s1>>8)&0xff]^Te3[s2&0xff]^rk[7];

If so, then (by my testing) it requires 3, not 2, rounds for diffusion. It's also hard to implement an even number of rounds because it seems to require I begin and end on a t0=... round (vs. the alternating s0=... round).

A single full AES round consists of the following:

S-box application
Shift-Rows
Mixcolumns
Add round keys

2 subsequent applications of shift-rows and mixcolumns provides complete diffusion of the state and the initial round key.

What you posted is a software optimized design, which combines the first 3 steps into a table lookup, then adds round key words. Te0[] is the first lookup table, and s0 is the first word of the state. I would suggest looking at how the tables are generated.

  It's also hard to implement an even number of rounds

In that design, you simply set s0-s3 to t0-t3, and begin the next round with the correct round subkeys.


Building content-defined chunking with adversarial data preserving guarantees on splitting probability and global stability I'm using the Prolly tree data structure. This structure operates on serialized data which it chunks at the byte level into pieces. To build trees recursively, the list of chunk hashes is itself serialized and chunked until an un-chunked root node is created.
I am building a distributed application that must construct these trees on potentially adversarial data. The normal chunking algorithm can be manipulated to produce badly performing chunks that are oversize or undersized. I need a chunking algorithm that can guarantee good chunking properties while being publicly known to the attacker.
This algorithm must be globally stable to preserve the efficiency of the data structure since local modifications should not require recalculation of chunking outside some local region. This ensures modifications have consistent log(n) tree size dependent time complexity.
I'm interested in a secure solution to this problem, even if not very efficiently computable.

What I think may be doable is some standard rolling hash function applied over a one-way hashing of the original content to determine the splitting points, but I've not been able to write a non-fundamentally-flawed algorithm.

The Shape of the problem
The input is a string of bytes $\{D_1,D_2,D_3,...D_n\}$. This input needs to be chunked.
In the general case, I'll assume there is some hypothetical function chunk_at_index(Data[i-N:i+N]) which can be called to determine if the stream should be cut at index i. Any function that outputs a cut location given a section of the stream can be wrapped to produce this simpler function. This requires that chunking boundaries are stable and determined only by local information.
The general case is impossible
It is impossible to guarantee this in the general case while also ensuring that chunks meet a given (min/max) length criteria or maintain global stability. No such function can guarantee global stability of chunk boundaries after a local edit.
Consider the a string of repeated characters "aaaaaa[...]aaaa"
A function evaluated on a rolling window must either chunk on every byte or leave the entire string intact. No local function can stably decide where to draw chunk boundaries inside the uniform region without considering data outside that region.
Any algorithm that guarantees chunks fall in a certain size range has to be either unstable or use non-local information.
Consider the following string, with a section consisting of repeated 'a' characters. A hypothetical chunking function chunks it up as so. An edit is made and then it is re-chunked.
"Hello " "world!aa" "aaaaa" "aaaaa" "aaaHello " "world!
"Hello " "world!aa" "aaaaa" "aaaaa" "aaaHello " "world!
"Hello " "world!aa" "aaaaa" "aaaaa" "aHello " "world!
A change to the second chunk changes a chunk an arbitrary distance away.
A data compression algorithm could probably be built to pre-process the data in order to fix this. It would need some ability to recursively compress its own output to prevent its own output from having similar repeating patterns.
This illustrates the problem of finding features to use to cut the stream up reliably.

Prolly Trees Don't Have that Issue
Fortunately, Prolly trees are used to store sorted data items, typically key value pairs. Assuming the value is stored by a cryptographic hash reference in the serialized data and that the keys are close enough together, a chunking algorithm will have locally unique features with which to make a yes/no chunking decision for a given window onto the string. If an algorithm can't decide reliably where to make a cut it's the algorithm's fault.
Why a Rolling Hash?
A rolling hash takes a window of bytes in the string and outputs a score representing preference for that location as a chunk boundary.
This is a really powerful concept. The score represents how much the algorithm should want to split the stream at a particular spot. It's only dependent on the data near that index which is why chunk boundaries tend to be stable and re-synchronise.
For non-adversarial data a simple threshold works well to decide where to split but if the adversary can manipulate the scores, we need a better algorithm for choosing boundaries.
Requirements for the Rolling Hash
Any rolling hash will have an output range. If the attacker can completely control the output, they can create pathological score profiles that no function can use for choosing split points. Collisions and exact repetitions are quite problematic as are the integer function output limits. Normally an attacker would have to do 2^N work to set N bits of the function value. For universal hashes or anything else that uses tractable math to make calculating the hash over a rolling window efficient the output can be controlled trivially.
It seems necessary to use a strong hash algorithm for generating scores (essentially applying SHA2 or similar to the hash window). This ensures the attacker has to work harder to get a better score and can't cheat. all that's necessary is to build a splitting function that is computationally infeasible to mess with in the long term. Ideally something that gets quadratically or exponentially harder the longer it hasn't marked a chunk boundary.

Notation
The input is a string of bytes $\{D_1,D_2,D_3,...D_n\}$.
we compute a rolling hash function over this string to compute the score for each cut location. S(i) = SHA2(Data[i-A:i+A]). The scores can be seen as an array of values that can be sliced S[i:j].
The off by one issues here aren't too important. I'm similarly going to ignore issues relating to hash values at the start and end of the string where the hash window isn't full. the hash window size A should be a little larger than the minimum chunk size for reasons that will become clear later.

Localized Beauty Contest
A robust way to enforce a minimum chunk size is to select for values that are the smallest inside some local window. For stream index i we check that the score for that index S[i] is the minimum of the slice S[i-A:i+A] where A is the minimum chunk size. A point wins and becomes a chunk boundary if it is the minimum when it is in the center of the window. This can be done on a rolling window by keeping a sorted heap of values or the ascending minima algorithm. It chunks about once every 2*A bytes.
This doesn't enforce a maximum chunk length. If S[i] would win, the attacker can change some bytes around index i+2A to make S[i+A] lower. They repeat this at index i+A finding a change to make S[i+2A] lower still. When graphed out this looks like a stair step pattern.
The attacker does have to make sure these points aren't too good. Statistically, each time a better point arrives, that lower score will be about half the previous score. This ensures normal data has no very long chunks. If the attacker is naive search time roughly doubles for each step. The attacker can choose not to use values that are too low to make future searches easier though. Increasing compute cost per step slows the rate of difficulty increase proportionally making this attack quite practical.
Finding a "Good Place" to Cut an Evil String
The above algorithm provides a hard guarantee on minimum chunk size. Any change that can make additional cuts can break the minimum chunk size guarantee and usually will. Most things involving math on the score values directly will fail badly.
The attacker can also join sections of evil attack parts together. They just need to find a piece of "glue" that gives hash values in the transition region that meet their attack requirements.
One way to prevent that is with a hash tree. The score S[i], being a cryptographic hash, is a commitment on Data[i-A:i+A]. The hash SHA2(S[i] | S[j]) Changes unpredictably if data is changed in the vicinity of either index i or j.
Supposing we run into a stair-step pattern. Points are spaced too closely together to be used as chunk boundaries. Using the scores directly is difficult but we can make a new set of scores by hashing the points with either their left or right neighbor. The local contest algorithm can be applied to these new scores again to winnow down the list of remaining points. The process is repeated until, points are far enough apart to meet minimum chunk size requirements. Keeping the algorithm from making progress requires the attacker to arrange for values in successive layer to be a stair-step pattern This becomes exponentially harder the more layers are involved.
Let me make this all a bit more clear
Assume the indices $\{j_1,j_2,j_3,...j_n\}$ are the indices of all scores s[j] which were the minimum value for a window S[i-A:i+A] passed over by the first algorithm. These are the points in a stair step profile along with other points that "won" and are now chunk boundaries.
Any chunks that are above the maximum chunk size must be processed further.
Take the indices J[n:m] corresponding to a chunk over the maximum size with J[n] and J[m] being that chunk's boundaries.
Look up the corresponding "interesting" first level scores I_1[k]=S[J[k]] for k=n...m.
We construct $I_2[k]=SHA2(I_1[k],I_1[max(n,k-1)])$ for k=n...m, hashing in the left neighbor to get the next level of score values.
This series of $(J[k],I_2[k])$ (index,score) points is processed by a similar beauty contest algorithm that finds local minimum points. Unless there is a similar stair-step pattern in the I_2 points, some points will be eliminated or will win and become chunk boundaries. This can be repeated for successive levels hashing in left and right neighbors alternately at each level and applying the "beauty contest" algorithm to reduce the number of point and pick winners at each level.
Eventually chunks that are oversized will be cut into non-oversized pieces. This works locally too since we don't need to see the ends of a chunk to know it is oversized. Just seeing a long stretch of string with no chunk boundaries tells us we need to apply another layer.
Each additional layer gets exponentially harder for the attacker to add so there's a limit to the number of layers the chunking algorithm will have to look at. This ensures the function can be evaluated locally, requiring a little less than A*(Max layers+2) bytes of context ever be looked at.
I haven't done any analysis, but I'd guesstimate an attacker won't ever get past 40 layers or so.
I could throw together some python code implementing this if you're still confused.
This is an original algorithm so there might be some vulnerability I'm not seeing.


Are picture files "random enough" to be usable as a one-time pad? Say you have a picture with 1 megapixels taken at random and with $2^{24}$ possible colours per pixel (RGB-24). That image would be unique and the possible combinations $(2^{24})^{10^6}$ immense.

However when taking a picture in the real world, say of a clear sky, there will be a lot of repetition.

The question is: would such repetition present a security risk when used as a one-time pad, where the requirements of randomness is so high?

My hunch is that it is, as true randomness would require the possibility of all pixels being #FF0020 or whatever, but I would like to be proven right or wrong.

If I've been unclear at some point, please let me know and I will edit my post.

No.  This is not safe.  The one-time pad requires that the pad be generated by a true-random process, where each bit of the pad is chosen uniformly at random (0 or 1 with equal probability), independent of all other bits.

Any deviation from that, and what you haven't is no longer the one-time pad cryptosystem -- it is some kludgy thing.  In particular, once you deviate from that requirement even a little bit (and you're talking about a huge deviation), you are skating on thin ice and there will probably be security problems with your scheme.

If you're gonna use the one-time pad, you gotta use it exactly as it is defined, with a truly-random pad.  There are no shortcuts, no halfway stuff.  Messing around with this sort of thing is exactly what enabled the US to cryptanalyze Soviet use of a "one-time pad" in the VENONA project.

But in practice, you probably don't want to use the one-time pad anyway.  The key management issues are enough that it is rarely a good choice in practice.


Will cryptanalysis always stay a relevant topic? I hope this doesn't look like a silly question. In an age where our current cryptography is often impossible to crack when properly implemented and used, would we be able to decipher anything, for example if WWIII were to break out ? Similarly to how the Germans added some rotors to Enigma, what could be done against 500-rounds AES if classic AES were to be broken ? Iirc, quantum computers can trivially break RSA, but I don't know about AES. Also, while talking about quantum things, I think I heard about a paper related to the teleportation of some bits between 2 processors. This would mean that in the future, even intercepting the messages would be impossible.
In ~1900, the physicists thought that, minus one small problem, they were almost done with describing physics. Is it possible than in the future, cryptanalysis would also reach a state of near-completion ?

Will cryptanalysis always stay a relevant topic?

In the modern cryptologic sense cryptanalysis is the science of breaking concrete constructions. This will stay relevant for as long as we rely on constructions which only satisfy security notions heuristically. We can't come up with a general construction that is a Pseudo-Random Permutation for all input lengths, because that would imply $P\neq NP$. Therefore we need heuristic constructions like AES. Additionally this field will stay relevant for as long as we try to come up with new schemes that are ever faster and smaller for some definitions of fast and small.
Furthermore one could argue that side-channel analysis belongs to the general group of cryptanalysis as well and that will remain relavant for as long as we compute cryptographic algorithms on non-ideal hardware.
One may also argue that all these attacks one hears about against TLS, WPA, or SSH also fall under "cryptanalysis". In a sense I agree: While quite a few of them are implementation errors there are also some that aren't. In fact usually these days these protocols have security proofs in a particular communication and adversary model. The point of the attacks is then to find scenarios that aren't covered by the adversary's possibilities in said model, then find an attack that breaks an intuitive security property and argue why this break is (more or less) relevant. Though it is to be expected that this line of research will eventually exhaust all possible oversights in any given class of models. Of course some people also use protocols without proofs and those will always be the target of cryptanalysts (or proof-focused people) for as long as people do this - which may also yield successful attacks despite unbroken building blocks.

I hope this doesn't look like a silly question. In an age where our current cryptography is often impossible to crack when properly implemented and used, would we be able to decipher anything, for example if WWIII were to break out ?

It is currently believed that things like AES are actually secure. However, many governments have their own encryption algorithms, e.g. for highly-classified data. Most of these algorithm descriptions are classified, so only some of that country's researchers can analyse it and so some weaknesses could have been missed. This is of course less of a problem for countries like the USA but more of a problem for smaller countries with less access to enough people who are really good at this sort of cryptanalysis. A similar argument applies to the mechanisms used to transport / negotiate the keys for these algorithms, though probably less strongly. Because of this, it is not impossible for "hostile" encryption schemes to be broken once a description has been acquired - though it is unlikely as the really hard part about this kind of cryptography is getting it fast and secure as opposed to "merely" secure.

Iirc, quantum computers can trivially break RSA, but I don't know about AES.

Quantum computers can break most currently deployed asymmetric cryptography given a sufficient size. They can also give a substantial speed-up (in theory at least) for breaking symmetric schemes, but it is generally believed that this is "fixed" by doubling the key size from 128 to 256 bit (as quantum algorithms half the bitlength of the search space).
This point actually allows us to come back to the first question: It is currently an active effort to come up with as efficient asymmetric cryptographic algorithms as possible that resist quantum computers. As we don't have unconditionally provable secure constructions against quantum computers, we resort to heuristic methods again, which require analysis to see whether they actually stand up against quantum computers.

Also, while talking about quantum things, I think I heard about a paper related to the teleportation of some bits between 2 processors.

This is more of a question for Quantum Computing SE or Physics SE. If you're still looking for an answer on this site, I'll refer you to poncho's answer.