Security of expanded key Can somebody analyze this scheme and explain how (in?)secure it is?

Assume that:

The keys were initially securely exchanged
All keys are truly random

In this scheme:

The key size is of length 2s, the plaintext is of length s, and the total message size is 3s
The first 2s contains a randomly-generated key to be used for the next message
The last s contains the plaintext.
The message in question uses the Vernam cipher
The first half of the key encrypts the next key, and the last half encrypts the plaintext

How secure is it to have every bit in the first half of the key (total size s) encrypt every two bits of the next key to be used?

Does this leak information about the keys?
Is it possible to actually deduce keys from that?

What if some sort of random mapping where each bit of the key does not encrypt consecutive bits of the next key was thrown into the mix?

Edit:

Example message layout:

|     Next Key(size 2s)        |   Plaintext(size s)  |
               |
               |^ This half is the key for the next plaintext
^ This half is used to encrypt the whole key (each bit encrypts 2 bits of the next key)

Edit 2:

Message: | Next Key Key | Next Key | Plaintext |
           ^Encrypts this-\/     ^Encrypts this-\/
 Possible Random Mapping->\/                    \/
              [_________________________]       \/
Next message: | Next Key Key | Next Key | Plaintext |

What is inherently insecure about each bit of a random key encrypting two bits of the next (entirely random) key in this scenario?

In addition, would adding a random mapping between the bits of Next Key Key and the next key add any security if the mapping was changed every message (some kind of mapping struct in the plaintext)?

If not, why? If this scheme is completely insecure, I wish to understand in what specific ways it may (as you say) leak information about the plaintext.

Edit 3:

Upon inspection, it turns out that one only needs to figure out HALF of the first key in order to crack the entire message chain. Each message makes it easier to find that half-key, since each message depends on the previous one.

Does this leak information about the keys?

It leaks information about the plaintext.  For example, given the three ciphertexts, it's possible to compute the XOR of the second and third plaintexts.  This is often enough to deduce the original plaintexts.

  What if some sort of random mapping where each bit of the key does not encrypt consecutive bits of the next key was thrown into the mix?

To start, instead of trying to guess about how to make the process more complex, I would suggest thinking about how to rederive the attack I mentioned above.  Learning about how to do cryptanalysis is the right place to start to learn how to design cryptography.


How to construct a yes/no election protocol, such that only the result is revealed? Can we use a threshold scheme to construct a (yes/no)-election protocol, such that every voter can give a positive or negative vote or he can abstain, and such that only the result of the election is revealed, but the number of positives, negatives and abstains stays secret?

Are there some ways to do this without a threshold scheme?

A threshold, additively homomorphic cryptosystems (such as the threshold variant of paillier) would work just fine for this sort of system. Each voter would need to prove that their vote was in the set $\{-1,0,1\}$ instead of the typical $\{0,1\}$. All of this could be done using the thep library. There is a page on dealing with negative numbers.

An alternative to this would be secure multiparty computation. At its core, MPC has the disadvantage that all parties must be online at the same time. This can be mitigated by say designating a few (e.g., 5) servers that perform all the computation. When a person votes, they use secret sharing to split their vote into 5 different shares and send a share to each server.


How to attack Merkle-Hellman cryptosystem if the first element in the superincreasing series is too small? In An Introduction to Mathematical Cryptography Jeffrey Hoffstein et al. claim that "It turns out that if $r_1$ is too small, then there are easy attacks, so we must insist that $r_1>2^n$." Here $r_1$ is the first element of the superincreasing series used in the Merkle-Hellman cryptosystem before it is disguised with modular arithmetic and $n$ is the number of elements in the series. Does anyone have information on how these attacks might work or a basic explanation of why too small $r_1$ is unsafe?

Let's begin with a short description of the Merkle-Hellman knapsack scheme. The private key is a superincreasing sequence of $n$ elements $b_1, b_2, \dots, b_n$, along with a secret element $W$ and $N$, with $W$ invertible modulo $N$. A superincreasing sequence is a sequence in which every element is greater than the sum of its predecessors:
$$
b_i > \sum_{j=1}^{i-1} b_j \,.
$$

The public key is the vector $a_1, a_2, \dots, a_n$, where $a_i = W b_i \bmod N$. To encrypt a message, the sender splits the message into individual bits $m_i$, and calculates the encrypted message to be
$$
c = \sum_{i=1}^n m_i a_i \equiv \sum_{i=1}^n m_i b_i W \,.
$$

Decryption begins by multiplying $c$ by $W^{-1}$ modulo $N$, cancelling out the contribution of $W$, and then solving the subset sum for the known superincreasing sequence.

We can break the scheme by recovering either $W$ or $N$. The following simple attack is described in Galbraith's book. Suppose $b_1$ is small—much smaller than $2^n$. Then it is likely that $b_2$ is also similarly small, and we have the interesting property:
$$
\begin{align*}
  a_1b_2 &\equiv a_2b_1 \pmod{N} \\
  Wb_1b_2 &\equiv W b_2 b_1 \pmod{N}\,,
\end{align*}
$$
and therefore $a_1b_2 - a_2b_1$ is guaranteed to be a small multiple of $N$. By bruteforcing $b_1$ and $b_2$, we can recover a short list of candidate $N$, which we can then confirm by trying to recover $W = a_1/b_1 \pmod {N}$ and verify if this $W$ applies to the other $a_i, b_i$ as well. This suggests that $b_i$ should be at least $2^{n/2}$ in size.

This is not the only attack when $b_1$ is small. Odlyzko described another two, including the famous Shamir attack. There are also very relevant lattice attacks on Merkle-Hellman, but those are already seem to be described in Hoffstein et al.


Block cipher birthday bound and a KDF workaround Can the birthday bound arising from a block cipher’s block size be worked around by deriving different keys from the master key with a KBKDF using a tweak?

For example consider the following scheme, which assumes

K is a 256-bit key
tweak is an integer we can increment before 2^64 blocks have been encrypted with the current generation

and then encrypts as follows:

IV = random 256 bits
EffectiveKey = KDF(K, context=tweak)
ciphertext = KeyGeneration || IV || AES-CBC(IV, EffectiveKey, plain)

Would this scheme be secure for encrypting more than 2^64 blocks?

Asked in order to learn more about the birthday bound.

EDIT - this has similarities to the construction used in the Better Bounds for Block Cipher Modes of Operation via
Nonce-Based Key Derivation paper (great talk too by Yehuda Lindell), which also introduces AES-GCM-SIV.

Obviously you assume blocklength is $128$ bits. I believe the following is correct.

One might try rainbow table TMTO attacks, assuming known plaintext, and succeed with time and memory complexity somewhat better than
$$
O(2^{(2/3)k})
$$
where $k$ is the effective keylenth,
against such a scheme but it would be secure beyond the birthday bound.


hashing and message input size If a hash function like Whirlpool or Sha512 would take a byte array of 1 MB in size filled with the output of a Secure RNG as its input message, would this be considered a strong input message, a strong key, or neither ?

Neither.

There is no such a thing as a strong input message to a secure hash function.

Hash functions don't take a key as input. Keys could be used as input to a KBKDF such as HKDF to derive additional keys key secrets. Those algorithms are often build from hashes though.

The output of a secure random bit generator doesn't need to be hashed to be secure. Many PRNGs / DRBGs are actually build from secure hash functions. Adding a single hash won't help.


Decrypting an already sent encrypted file in PGP I am a novice in cryptography and need few clarifications.

If I am SenderA, sending document to Receiver using PGP encryption. Let's say, SenderA shuts down and SenderC takes on the role of SenderA. SenderC gets hold of the secret key from SenderA (to minimize disruptions of adding new keys and involving Receiver).

If I only have list of encrypted files that SenderA sent earlier, how can I as a SenderC decrypts those files back into original?

Any help will be much appreciated.

When encrypting with PGP, it's common for the sender to add themselves as a recipient. When they do that, they are able to decrypt their own messages at a later time.

If the sender doesn't do that, they simply won't be able to decrypt their previously sent messages.


What is the progress on the MIT LCS35 Time Capsule Crypto-Puzzle? Ron Rivest posed a puzzle in 1999.  MIT LCS35 Time Capsule Crypto-Puzzle.

  The problem is to compute $2^{2^t} \pmod n$ for specified
  values of $t$ and $n$.  Here $n$ is the product of two large primes,
  and $t$ is chosen to set the desired level of difficulty of the puzzle.

  Note that the puzzle can be solved by performing $t$ successive
  squarings modulo $n$, beginning with the value $2$.  That is, set

  $W(0) = 2$,
  $W(i+1) = W(i)^2 \pmod n \quad$    for $i\ge0$,

  and compute $W(t)$.
  There is no known way to perform this computation more quickly
  without knowing the factorization of $n$.

In 1999 they predicted that we'd have 10 GHz processors by now.  I realise that raw GHz is a dumb way to measure speed, but how fast are computers for this kind of "intrinsically sequential" computing?

I guess my questions are:

1) What is the state of the art for computation which can not be parallelised?

2) Has anyone claimed to make any progress with this challenge?

2) Has anyone claimed to make any progress with this challenge?

Ah that question I can answer now...

I found the solution on the 15th of April 2019 and sent it to the MIT's CSAIL on the 16th of April. Another team shall have the answer by the 11th or 12th of May (they used a FPGA).

I noticed around the end of 2015 that if I used GMP I could find the answer on my Core i7-6700 CPU in about three years and a half. So I basically let my computer open 24/7 so that it'd solve the "puzzle".

The secret message and the two primes shall be announced on the 15th of May during a ceremony where the "time capsule" shall be opened.

Link to the CSAIL's article about it:

Programmers solve MIT’s 20-year-old cryptographic puzzle


Near in place encryption with BouncyCastle CCM, How large must IV and MAC be? I need to encrypt 20 bytes of data and the encrypted nonce + data + mac cannot exceed 30 bytes in size. I have an implementation but i'm not sure if i'm cutting too many corners and compromising encryption.

Using the bouncy castle library i was able to write this.

    static (byte[],byte[]) encrypt(byte[] data, byte[] key, byte[] nonce)
    {
        var engine = new AesEngine();
        var parm = new AeadParameters(new KeyParameter(key), 16, nonce);
        var chipher = new CcmBlockCipher(engine);
        chipher.Init(true, parm);

        var output = new byte[chipher.GetOutputSize(data.Length)];
        var outputLength = chipher.ProcessBytes(data, 0, data.Length, output, 0);
        chipher.DoFinal(output, outputLength);

        return (output, chipher.GetMac());
    }

Here is my thinking. For the data encrypted i have the following pieces of information known:

Metadata about the origination of the data
The approximate date the data was encrypted (down to the day)

With that information i formulated a nonce that contains:

2 bytes meta + 8 bytes Unix ms timestamp

With that i'm able to chop off all but the last 4 bytes of the nonce as those are the least significant bytes that indicate a timestamp for the day in question.

With that in mind i can have the final full encoded data as:

4 byte nonce + 20 byte encrypted + 2 byte MAC

This makes it fit under the 30 byte limit.

So here are my questions:

Is a 16 bit MAC effective at all in this scenario?
Is it kosher to create a nonce from partially known data?
How can i verify that my nonce is being incremented properly inside the code? I just appear to pass a static nonce even though its supposed to increment according to CTR... right?

So I'll answer in order:

  Q1: Is a 16 bit MAC effective at all in this scenario?

You have defined (part of) your protocol, but you haven't defined your system. What happens if a MAC doesn't get accepted? If you have only a 16 bit MAC then there are only 65536 values of the MAC. If an adversary can just generate messages and fire them at the receiver then brute forcing a tag is entirely possible. Even if you can just have one try: a chance of $1 \over 65536$ is not considered secure enough.

Using 8 bytes would be a great idea, but that leaves you only 2 bytes for a nonce, so you would only have 65536 messages.

  Q2: Is it kosher to create a nonce from partially known data?

Sure thing, a Nonce just needs to be unique - but note that in the case of CTR and CCM the nonce size also influences how many counter blocks can be created, and therefore how much data can be processed per nonce. CCM is just like CTR in that sense; it even requires an additional byte of meta information in the counter, leaving less space for the nonce and counter.

Kind of obvious, but the other requirement is that the receiver must be able to re-generate the nonce.

  Q3: How can i verify that my nonce is being incremented properly inside the code? I just appear to pass a static nonce even though its supposed to increment according to CTR... right?

No, the counter is being incremented - not the nonce. The nonce is just used to create the counter. Often the nonce is simply the most significant part of the counter. In the case of CCM this is true as well, even though the most significant byte is skipped. see for instance NIST SP 800-38C chapter A.3 where the counter increase is being implemented.

In GCM mode it is also possible that the nonce is pre-processed to generate the initial counter value, so there are certainly differences in how the nonce is used between the various implementations of authenticated encryption, even though CTR mode is used in virtually all these modes.

Note that the counter mode specified by NIST does not specify how the counter value must be generated; implementations are free to choose any scheme they want.


What encryption algorithm is context-free, deterministic and symmetric? Meaning the same key is used for encryption and decryption (symmetric). The same message always results in the same cipher text (deterministic) and has no memory (conetext free) like nounce or intialisation vector (IV).

Which algorithms exist and are recommended?

There is SIV mode. It essentially computes a MAC over the plaintext and uses it as IV for encryption. It obviously doesn't offer IND-CPA security, but shouldn't leak anything beyond length of the plaintext and if two plaintexts are identical.

There are some generic constructions as well, like 3 to 4 rounds feistel networks, EME, etc.


Is there a recommended cryptoperiod for HMAC hashing keys? I have an application that receives certain pseudo-random input values and computes their keyed hash using HMAC-SHA256. The hashing key itself is 256-bits long, generated at random by a CSRNG.

Two questions:

Which category does the hashing key fall under in NIST's 2016 Recommendations? Is it a "Symmetric Data Encryption Key"?
If it doesn't fall under any of those categories, is there a recommended cryptoperiod for it, or can I use it ad eternum?

(I suspect that this is an irrelevant detail, but the pseudo-random input values the application is processing are themselves HMACs of other input values. However, they are computed by a third party. So, since I do not know or have access to the hashing key they use, I'm treating them as "pseudo-random.")

Theoretically as pointed out by @CodesInChaos there is no need to rotate keys as long as they remain secret.

Also as @CodesInChaos points out, you need to architect the system for key rotation in the event of key compromise.

The best way to do that is to build key rotation into the app and operational tooling, and then put procedures in place to rotate keys regularly. That way you know key rotation will actually work when you really need it.

During the Heartbleed incident there were banks that were unable to re-key many of their certificates for several months despite regulator requirements that they be changed immediately. Rekeying was an infrequent manual process on their varied and ancient systems; some had never been re-keyed and nobody in house knew how to do it. It simply couldn't be done in a timely manner.

Regular exercise of key rotation prevents this sort of problem. Automation makes it easy. Think of it as DR planning and testing for your crypto keys.


Session key Exchange, some doubt I have to find a solution to this problem: I have a network composed by 1 server and some client. The server has a couple of keys (public and private) and it shares a secret key with each client. My goal is to exchange a session key between the server and the clients.

I've evaluated some solutions, but I am unsure if my reasoning is correct.

I started thinking about DH, looking for a solution making it secure. And then I realised that maybe the client could randomly generate the session key and then it could send the key to the server in a secure way. In particular, my “secure way” consists in calculating the MAC of the session key using the shared secret key between client and server, and then encrypting $(MAC || session key)$ with the server's public key. In my opinion this “protocol” provides confidentiality, integrity and a sort of authentication using the secret shared key.

To conclude the protocol the server should send an ACK if the exchange has worked.

To recap:

Client:

generate $k$ // random session key
$t \leftarrow M(k,s)$ // calculate MAC using s(shared secret key)
$c \leftarrow E(es , k||t)$ // Encrypt $k||t$ using server's public key
Send $c$

Server:

$k||t \leftarrow D(ds , c)$ // Decrypt c using server's private key
$t´ \leftarrow M(k,s)$
$(t == t´)$ ? OK : ERR

I'd like to know if my reasoning is correct.

This is basically the difference between e.g. the RSA_ ciphersuites and the DHE_/ECDHE_ ciphersuites in the TLS protocols. Currently the standardization moves towards ECDHE_ because it provides forward secrecy: even if you factor the RSA key you can still not decrypt previous transmissions.

Note that you don't have to MAC the session key before encryption with the RSA public key. You do however need to MAC your ACK with the session key so the client can verify the that you both have calculated the same session keys.

I'm saying keys because you should try and create at least session keys for sending and receiving. In addition you could create keys for session encryption, session authentication and possibly even the initial authentication, depending on the rest of the protocol.

You can forget all the text above if you study TLS, or if you use (D)TLS in favor over your own protocol of course. No need to climb an ice wall, somebody already dug a tunnel.


How often does RSA-OAEP have a leading zero? We are working with a third party vendor who is very tight lipped about their security protocols, and one of our customers who used this vendor's products is claiming that approximately one in every 250 times they initialize the system, it generates a key file that is 127 bits instead of 128, and gets rejected. They believe that when the key has a leading zero, that zero is dropped, resulting in a key that is too short and is rejected by the system. My understanding is that in the final step of RSA-OAEP encryption, the key is left-padded with zeroes. I'm not even sure they're using OAEP. (Personally, I think if they were really concerned about security they'd be less worried about hiding their implementation details and more worried about only using a 128 bit key, but the attack surface for this system is very, very small.)

I don't follow all of the math leading up to that step, but how often is the result of the modular exponentiation step exactly the desired number of bits? My expectation is that if it were an issue with dropping leading zeroes, that the error would occur much more often than 1 in ~250 (which I assume is 1 in 256, since most of the process is handled in octet strings).

Edit: I did find clarification that there is an issue in the documentation we received and it is 128 bytes.

Your description of the protocol is rather confused. You seem to jump between a key and an encryption output. It isn't clear whether you're worried about the key generation process, or an encryption operation that happens with this key.

I assume that you're talking about RSA with a 128-byte key, not 128-bit — 128 bits was already insecure when RSA was invented, whereas 1024 bits (128 bytes) is still publicly unbroken but worryingly small nonetheless and deprecated by all major key size recommendations.

An n-bit RSA key (where n is a multiple of 8, which is almost always the case in practice) should usually have a most significant bit that's set, i.e. a most significant byte that's larger than 128. Some systems generate a key that's actually one bit short because they multiply two n/2-bit primes and the result can be anywhere between $2^{2\lfloor (n-1)/2\rfloor}$ and $2^{2\lceil (n-1)/2\rceil}$; that's acceptable, and results in a most significant byte that's between 64 and 128. If the key is supposedly n-bit but is sometimes a whole byte short (8 bits short), that indicates something wrong about the generation process.

RSA-OAEP applies the RSA exponentiation operation to a number which, when written out with the most significant byte first, has 0 as the first byte value and every other byte xor-masked by a pseudorandom string. A xor mask by a pseudorandom string is itself pseudorandom. That is, the number looks like this in hexadecimal: 00rrrrrr…rr where the r digits are pseudorandom. This is only an intermediate value however, so it isn't clear to me why it would be relevant.

The output of RSA encryption is a number modulo $n$ where $n$ is the RSA modulus. That number can be anywhere between $1$ and $n$ in a way that's indistinguishable from uniformly random (or at least pretty close) if you don't have the private key. That means that the most significant byte is biased (in particular, larger values are impossible), and it's 0 more than 1/256 of the time.


GOST R 34.11-2012 hash function works from the end, is this convenient in practice? RFC 6986

Step 2.
       2.1.  Check the condition |M| < 512
            If it is true, then go to Step 3.
            Else, perform the following calculations:
      2.2.  Calculate the subvector m belonging to V_512 of the message
            M:
            M = M'||m
            Then perform the following calculations:

So, this hash function process message from the end. Is this convinient in practice, when user wants to hash some big data, for example few gigabytes file, or when low CPU/RAM device wants to hash stream of data on the fly? The code have to keep entire message in buffer, and start hashing only when it receives full message.

I understand, that this approach is more secure and eliminate length extension attack, but it is very unpractical.

I understand, that this approach is more secure and eliminate length extension attack

Actually, just be processing the blocks backwards doesn't actually eliminate any attacks.  Instead of 'length extension' attacks, we have 'prepend attacks' (where we add the extra blocks to the beginning rather than the end), which yield the same vulnerability.

Now, this 'prepend attack' does not appear to apply to the GOST hash function, but that's because they perform some final block processing involving g_0 (which is distinct from their hash compression function g_N in that they don't xor in the bit counter).  However, this defense has nothing to do with the order of processing blocks.

  but it is very unpractical.

Depends on their use case; if they always have the message in front of them in memory, it would appear to work just fine.

However, they don't appear to gain anything from making the hash function not computable online (which is the term for the property you're asking about); I have no idea why they did so...


What is the impact of the Goppa code distinguisher on the CFS and McEliece? What is the impact of the distinguisher for the high-rate Goppa codes (as published in "A Distinguisher for High Rate McEliece Cryptosystems") on the CFS signature scheme and the McEliece/Niederreiter cryptosystems?

It seems that the distinguisher strongly affects the CFS scheme, forcing its parameters to increase (if one hopes for a provably secure signature) to such an extent that the CFS scheme becomes totally impractical.

On the other hand, the distinguisher does not seem to affect the security of the McEliece cryptosystem at all. Why is that?

Why the CFS signature is affected

Let us review the structure of the CFS signature, which is strongly related to the Niederreiter PKE scheme.

In the Niederreiter PKE scheme, a public key is $H \in \mathbb{F}^{n \times k}$, which is a scrambled parity-check matrix of the Goppa codes.
A plaintext is a decodable error; for example, we set $S = \{\vec{e} \in \mathbb{F}^n \mid H_w(\vec{e}) \leq t \}$ for some $t$ as a plaintext space. A ciphertext is a decodable syndrome of $\vec{e}$, that is, $\vec{c} = F_H(\vec{e}) = H \cdot \vec{e} \in \mathbb{F}^{k}$.

This mapping is not surjective. In other words, there are several undecodable syndromes.
The ratio of undecodable syndromes is in proportion to the ratio of the code.
The higher a ratio of code is, the lower a ratio of undecodable syndromes.
Therefore, the practical CFS signature requires the code to be high-rate.

The security proof of the CFS signature scheme goes as follows:

The original security game.
Exploit the random oracle in order to remove inversion. In each query, choose $\vec{e}$ and define the hash value $RO(i,m) \gets F_H(\vec{e})$.
Replace the public key from a scrambled parity-check matrix $H$ to a random matrix $H_{\mathrm{random}}$.
Now, we reduce the game to the syndrome decoding problem.

In several parameter settings, the high-rate code distinguisher falsify the argument at Step 3.

Why the McEliece/Niederreiter encryption is less affected

A one-line answer is that the above PKE schemes can be constructed from low-rate codes.

In the PKE schemes, a decryptor has no need to be able to decrypt any ciphertexts.
Hence, we can employ relatively low-rate codes, on which the high-rate distinguisher you referred fails.


What is a formal definition of strong one-time-secure signatures? What is a formal definition of strong one-time-secure signatures?

I know the Lamport's scheme is one of them, but what is the global definition of it?

It's the usual security game for digital signatures, but the adversary is only allowed to make a single signature query.

In other words:

The simulator generates a key pair, and gives the adversary the verification key.
The adversary sends the simulator a message $m$. The simulator signs the message and sends the signature $\sigma$ to the adversary.
The adversary outputs his forgery $(m',\sigma')$.

The adversary wins if $\sigma'$ is a valid signature on $m'$ and $(m',\sigma') \not= (m,\sigma)$.

In the usual signature game, the second step can be repeated many times.


Layman understanding of SHAKE128 XOF Need some help. I am not versed in hashing and just started programming with PHP and currently need to hash some strings but required it to be unique. Found that OpenSSL can hash with SHAKE128 but without the option to select the lengths of the output. Notice that every openssl_digest function with shake128 hash output is 256 character by default, can I just take the first 20 character to use since I notice only the last few characters are appended with each length change?
shake128 hash "hello"
example:

5 byte - 8eb4b6a932

6 byte - 8eb4b6a932f2

7 byte - 8eb4b6a932f280

8 byte - 8eb4b6a932f28033

16 byte - 8eb4b6a932f280335ee1a279f8c208a3

Appreciate your insight. Thank you.

Yes, you can do that as long as you promise to not to use the hash for any other purpose that would be compromised if the shorter hash would leak. However, if you  need fewer than 128 bits then you might as well use SHA-3 and truncate that; it depends on the purpose if SHAKE128 is better than, say, SHA-3-256; they both depend on the same underlying sponge function after all.

Note that neither SHAKE128 or SHA-3-256 output any characters. They generate binary bits or - for most implementations - bytes. The hexadecimal characters that you're showing are just a representation of those bytes.


Is there a digital time-stamping scheme that does not rely on a time-stamping authority? Given a bit string, is it possible to assign it an immutable time stamp that is verifiable as correct without assuming a (one or more) trusted time-stamping authority? A time-stamp is correct if it is within delta milliseconds of the creation of the (instance of the) bit string, for some fixed but small delta. The creation time of a bit string is chosen by its creator / owner (but it is immutable once stamped).

To start off the discussion, I suspect that there will be a need to connect to some sort of physical information source (a la atomic clocks, resistor noise, radioactive half-life etc.) and make some clever use of it.

If it is not possible, I would like an argument that exposes the fundamental barrier.
If it is possible, I would like an exposition of the main idea and links to papers or patents for details.

I apologize if my question has a simple answer that my novice mind has  missed.

Thank you for considering my question and I appreciate your spending any  cycles on a stranger's query.

Update 1: When I say that the creator of the bit string may choose the timestamp, I mean that they can choose when to timestamp the bit string. If they decide to do so at some time t, then the bitstring must be time-stamped to show time t (within delta). It does not mean that the creator can choose any timestamp in the past or future. Such arbitrary stamping must be impossible in the scheme, of course.

If being decentralized with no trusted timestamping authority that could backdate things is a must, then the solution is Bitcoin's blockchain (or a similar cryptocurrency's blockchain). OpenTimestamps is a project for efficiently using it to timestamp files.

Most of the design for a possible basic decentralized cryptocurrency has been known since public key cryptography was invented (have a shared ledger of public keys with associated balances, and anyone can transfer currency from their balance to another by signing a transaction with their private key), but it had always been blocked by the double-spend problem (Alice could sign a transaction sending currency to Bob to buy a physical object, and then once it's in her possession, she could broadcast a second transaction with an older timestamp that sends that same currency to a 3rd address also controlled by herself instead, and try to convince everyone else that it came first and should be honored instead of the transaction to Bob). Essentially, without a decentralized timestamping service, there's no way for a decentralized cryptocurrency to get everyone to agree on the same order of transactions.

The double-spend problem was finally solved in 2009 by Bitcoin through its use of a proof-of-work blockchain. Each block contains a proof-of-work based on a hash of the rest of the block, the hash of the previous block, and a list of transactions. People ("miners") are incentivized to compute the blockchain proof-of-works by receiving newly minted bitcoins and bitcoin transaction fees. Each block contains a timestamp, and the proof-of-work difficulty automatically scales so that the proof-of-work (and therefore a new block) can be made every 10 minutes. Every Bitcoin node knows to use the longest blockchain. For an attacker to backdate a transaction N blocks into the past so that it would be before a conflicting transaction, they would have to calculate N proof-of-works, but the while they are computing these proof-of-works, the rest of the miners are on the network are still building the blockchain by creating more proof-of-works. The attacker would have to have more computing power than the entire rest of the miners on the network in order to race them and create a bigger blockchain.

Now to rewind a bit: to actually use this for timestamping files, then you would just want to encode a file (or merkle tree) hash into a transaction in the Bitcoin network. OpenTimestamps is a project for doing this efficiently. (There are other such projects, but OpenTimestamps is much more efficient than most and is made by a Bitcoin developer.) You might be wondering "why involve Bitcoin at all?" and want to extract out its blockchain, but that can't work as Bitcoin's blockchain only works because the miners have a cryptocurrency incentive to contribute, and a blockchain without a significant number of miners like Bitcoin's already has could be easily attacked.


Has Burdges and De Feo's concept of Delayed Encryption ever been implemented? In mid 2020 Jeffrey Burdges and Luca De Feo published a paper proposing a trapdoor-less time-lock puzzle called Delay Encryption. Has a prototype of this ever been made?

There is PoC code for the De Feo-Masson-Petit-Sanso VDF here: https://github.com/isogenies-vdf/isogenies-vdf-sage. It's easily adapted to Delay Encryption.


OWF by encrypting a constant? This question is a generalization of this old, unanswered question.

Suppose we're given a strong PRP $E:\mathcal K\times\mathcal M\to\mathcal C,(K,M)\mapsto C=E(K,M)$. Suppose further we pick a constant parameter $S\in\mathcal M$.

Is $F_S:\mathcal K\to \mathcal C, X\mapsto E(X,S)$ a secure one-way-function?
If the above is not answerable: Is $F_S$ at least a secure OWF for practical purposes?

As example instances one can imagine $S=0^{128},E=\operatorname{AES}$ or $E$ being a fixed-key AES instance within an Even-Mansour construction.

Since $E$ is a secure PRP, instead of giving $C=E(X, S)$ to the adversary, you can give a uniform random $C\gets\mathcal{C}$.  To 'invert' this, adversary has to find a key $X'$ such that $E(X', S)=C$.

So, the construction being one-way function is equivalent to the property that, given a uniform random $C$, it should be hard to find $X$ such that $E(X, S)=C$.  I don't think that this necessarily follows from $E$ being secure, strong PRP.  For example, when the block cipher has polynomial-sized small domain (rather unusual case, I know), then this would not hold.  On the other hand, most reasonable block cipher constructions would have this property, I guess.  So, I think it could be considered as a secure OWF for practical purposes, in reasonable settings.


How to calculate cycles per byte Sometimes, websites and scientific papers that introduce and/or handle cryptographic algorithms also provide speed-analysis and tables comparing the individual performance of cryptographic implementations. I would like to do the same, but I'm not sure how to calculate the “cycles”.

I have this data:

processor clock frequency: 2,1 ghz
message length: 16 byte
Speed: 4,3 Mbytes/s

How can I calculate “cycles” and “cycles per byte” from that data?

$\displaystyle \text{cycles per byte} = \frac{\text{cycles per second}}{\text{bytes per second}} = \frac{2.1 ~ \text{GHz}}{4.3 ~ \text{MiB}} = \frac{2.1 \times 10^9}{4.3 \times 1024^2} \approx 466 ~ \text{cpb}$

Of course this may be way off because processors are complex beasts these days, and may not work at their full potential all the time, and the calculations may very well be reordered, optimized, or vectorized.

So it's a little better than raw speed in that it is not dependent of processor clock speed but it is still quite dependent on the underlying hardware details. It is a decent measure of cryptographic performance.


survey on zero knowledge proof Is there a recent and comprehensive survey on zero knowledge proofs? I'm trying to find one which provide more details than the two chapters (19/20) in Boneh and Shoup's book (a grad course in applied cryptography)

Here's a recent doctoral thesis with a decent literature review.
https://discovery.ucl.ac.uk/id/eprint/10073525/


How to factorize the group order in Pohlig-Hellman algorithm The Pohlig-Hellman algorithm is for computing discrete logarithms in a group whose order is a smooth integer.
This algorithm requires the factorization of the group order. However we know that factorization of big number is a hard problem. So how could Pohlig-Hellman be an effective algorithm?

I will mostly talk about the Elliptic Curve since here the field size is around $2^{255}, 2^{448},2^{512}$ for secure curves. With Hasse's bound $$|N - (q+1)| \le 2 \sqrt{q}$$ the number of points is not too far away from the field size. With this, we can compare with the factoring records.
The current record achieved in 2020, CADO-NFS has factored an 828-bit $n$ with "roughly 2700 core-years, using Intel Xeon Gold 6130 CPUs as a reference (2.1GHz)". For the history see this detailed answer
If you set up a curve that has no big prime order on the order of the safe curves, it is not hard to factor for a dedicated attacker then use the Pohlig-Hellman algorithm for the discrete logarithm. Don't set up such a curve.
Actually, the parameters are never meant to be hiding see in SafeCurves, no security by obscurity. This more about don't propose a curve that doesn't have a large factor.
Having one large and a few small is fine like Curve255 has 8 as cofactor. The cofactor ($h = \#E(k)/n$) of the curve Curve25519 is $h=8$ which means that there are small subgroups of Curve25519. The order of the subgroups is $2,4,8,n,2n,4n,8n$.
Small groups are also vulnerable to small-subgroup attacks ( Lim–Lee active small-subgroup attacks), so we don't want them for this reason, too. Curve255 has no problem with either the curve itself or its twist.

Multiplicative discrete logarithm, on the other hand, dead for characteristic 2 ($GF(2^m)$) and almost dead for characteristic 3, ($GF(3^m)$). To be secure you need to a big field that the Pohlig-Hellman is your least problem (see on the keylength.com). Anyway, there are not to be kept secret either.


Is there a multiplicative group of integers modulo p in which the discrete logarithm is easy? The complexity of computing discrete logarithms in a multiplicative group modulo a prime $p$ is assumed to be sub-exponential time. The complexity is determined by $q$, the biggest factor of the group order $p-1$. Is there any group $\mathbb{Z}_p^*$ such that discrete logarithms are easier than subexponential in $q$?

As far as I am aware, all the recent progress on discrete log algorithms which derived pseudopolynomial efficiencies took place for the case of small characteristic fields $GF(p^n)$ with a structured exponent $n$. So the best complexity is still exponential in $\log N$ where $N$ is the size of the subgroup under consideration. So nothing better than generic DL complexity seems to be known.

You may find the following interesting. Bernstein and Lange have shown advances for generic discrete logs for the case that preprocessing is allowed, e.g., for curves in standards.

Even there, the online phase complexity seems to be $\geq (\log N)^{1/3}.$ See this paper for a discussion. Here is a quote:

  In practice, however, an adversary may have access to the description of the group $G$ long before it has to solve a discrete-log problem instance. In particular, the vast majority of real-world cryptosystems use one of a handful of groups, such as NIST P-256, Curve25519, or the DSA groups.


What is an impure NIST true random number generator? I'm working on a true random number generator, and I came across this phrase in the American NIST guide, in section 6.4.1 Non-Approved Conditioning Components:

  The entropy rate provided shall be no greater than the entropy rate provided by the input to the conditioning component; full entropy shall not be provided by non-approved conditioning components.

This suggests that you can have a random number generator that does not provide full entropy.  So if you use the de-rigour noisy diode source natively generating approximately 50% pure entropy, your generator can only output 50% entropy.  I'm unaware of any source that can natively generate 8 bits /byte entropy.  It would actually be undesirable  to run the source sampling equipment cranked up to 100% for many engineering reasons.

What is the point of a true random number generator that only produces half pure entropy?  Do you only use it half of the time?  Or do you just use every other byte (the random ones), ignoring the predictable ones?  Seriously though, is it just a thinly veiled warning that "it's our way or no way"?  Or..?

The NIST source you link to is SP 800-90B. If you look at the other two publications in the series: 90A and 90C, you can find explanations of how you can use a TRNG to instantiate a DRBG or requirements on how to condition the entropy.

Here is what section 7.1 of 90A says about entropy input to a DRBG:

  Ideally, the entropy input will have full entropy; however, the DRBG mechanisms have been specified to allow for some bias in the entropy input by allowing the length of the entropy input to be longer than the required amount of entropy (expressed in bits). The entropy input can be defined to be a variable length (within limits), as well as fixed length.

So you can use a TRNG with 50% entropy rate to initialize a DRBG, you just need a longer input.

90C defines the assumptions more exactly in section 4.2:

  An entropy source output string containing $2n$ bits of entropy can be conditioned into a string of $n$ bits that contains full entropy output1 using an approved conditioning function, where $n$ is the length of the output block of the approved derivation function (see SP 800-90B). Note that in SP 800-90C, a derivation function2 is used as a conditioning function.
  A DRBG that has been instantiated at a given security_strength can be used to produce security_strength/2 bits of full entropy output if constructed as specified herein.

The approved conditioning functions are listed in 90B, after the section you quote. Anything else would fall under non-approved, but something sufficiently standard would be fine if you do not mind diverging from what NIST says.

So a half-entropy TRNG is very useful. You just need to take the entropy rate into account when using it.


Why do block ciphers use key schedules instead of round constants? (Even-Mansour) Let's take AES as an example. What would be wrong with just having a 256 bit key that you XOR into your input and then XOR into your output? No key expansion at all.

I believe it's even known as the Even-Mansour construction and is secure under the assumption that the permutation is sound.

So I'm confused by the purpose of key schedules, you need variability to resist slide attacks but you don't need a key schedule for that, round constants suffice.

What would be wrong with just having a 256 bit key that you XOR into
  your input and then XOR into your output?

If I understand you properly, you split the 256 bit key into two 128 bit parts. This will be the whitening key that helps to resist exhaustive key search.

In term of round constant, it is adds asymmetry to the key and prevents slide attacks. However, you overlooked other attacks such as invariant subspace attacks for which you have to choose constants that eliminate weak key classes.

A related-key attack may remove the effect of the constant (key difference  eliminates the constant) but in real world, the adversary needs to have access to key generation to perform this attack.

I believe that the design of key-schedule lacks to solid proof. There was a paper in FSE18 about the mathematical proof of the AES-128 key schedule under related key attack. A solution was proposed using a better and lighter key-schedule without s-box or round constants, just permutation.

However, how to choose constants that prevent slide attacks? In other words, is there a proof that adding any constant will stop a slide attack?


Padding to increase entropy and size of (otherwise) small JSON objects Maybe this better fits, the security stackexchange...

I'm building a web API. We want to enable some relatively simple encryption, instead of going full-blown OAuth2 (which frankly, IMO, sucks). So I decided to use JWT. Anyway, it could happen for some requests that the request or response payloads are very small. Something like this for example:

{
    "order_id": 7
}

I imagine that when you encrypt something as small as this that it'd be relatively easy to brute-force. Therefore I'd like to increase the size of the payload by doing something like this:

{
    "order_id": 7,
    "padding": "kjt4J78vwzXXKEpuaodwOeTes2O5IIM5mUieNrxlRRWg1K0gXK164hstyL42QlQhKwoKCfVuA2eEJ8Pb1Sdm5tdRxXNNTl55dzrENzMBvrybGjeaHz8c7awmFmiHIsFsQ6gFKTzK2afZV483V4sjYVlYCy9C4pqU2BTK3YaonfxocG57UQwxlharNIhl8qqWbxCjEF7za9b6Sf1YfjHo2WoQ38miqSHr1aDlDWi35UZmHkYXpNVG7SoB3lfTYJ0Y"
}

This should work, unless I'm missing something. But ideally, I'd like to prevent the padding from being visible after decoding the JSON payload. I considered using a comment to that end, but JSON does not allow comments and apparently most implementations stick to the specification in that regard.

So is there a better way to do what I want, with the padding disappearing after decrypting/decoding? If anyone has an alternative for JWE, which does not involve OAUTH, I'm also all ears.

Encryption cannot be brute-forced: verifying a guess is as hard as decrypting. You can encrypt a 1-byte string — even a 1-bit string — and any sane encryption scheme guarantees that an adversary cannot tell which value is encrypted.

You do need to take care that the encryption algorithm is non-deterministic, in that if you encrypt the same plaintext twice, you get different ciphertexts. Otherwise an adversary could tell when you've sent the same message twice. All recommended encryption modes (i.e. anything found in typical libraries other than ECB) provide this guarantee, provided you use them correctly (e.g. using a random IV, which is necessary anyway with some modes).

An adversary can tell the length of the plaintext, or more precisely, can tell in which 16-byte interval it lies (16 bytes being the block size of AES (regardless of key size)). For example, {"order_id": 7} might encrypt to 32 bytes while {"order_id": 17} would encrypt to 48 bytes. You may want to pad all your objects to a constant size to avoid this, or at least arrange for variable-size values to be padded. The padding doesn't need to be random, you just need to manage the length. Given that you're encrypting JSON representations, adding space characters at the end should be fine.

Note that encryption only guarantees that the encrypted message remains secret. It doesn't guarantee that the message hasn't been modified in transit. For that, you need authentication. JWT offers A128CBC-HS256 (AES-128-CBC + HMAC-SHA-256) which combines encryption for confidentiality and a MAC for authenticity; if available on your implementation (it's only recommended in the standard), use the authenticated encryption mode A128GCM (AES-128-GCM).


Is it possible to create a Bilinear Function with Already Assigned "Multiplicative" Input Groups? Assume that we have an already assigned Multiplicative Cyclic Group $\mathbb Z_p^*$ with order $q=p-1$, and $p$ is a prime number, is it possible to create a bilinear function $\hat{e}: \mathbb Z_p^* \times \mathbb Z_p^* \rightarrow \mathbb G_2$ with the property that follows:

$$\hat{e}(g^{a},g^{sb})=\hat{e}(g^{b},g^{sa})$$

$g$ is a generator for $\mathbb Z_p^*$, and $\mathbb G_2$ is also a Multiplicative Cyclic Group with order $q$

it seems that if the creation of this function is practical in polynomial time then there should be new attacks on some cryptographic protocols with security property of anonymity.

If you can find such an efficiently computable function (other than the trivial solution $\hat{e}( x, y ) = 1\ \ $ for all $x$, $y$), then you have shown that the decisional Diffie-Hellman problem is easy.  That is, given $g$, $g^a$, $g^b$, $g^c$, you can check whether

$$ab = c$$

simply by testing:

$$\hat{e}( g^a, g^b ) = \hat{e}( g, g^c)$$

The decisional Diffie-Hellman problem is believed to be hard in appropriately sized Multiplicative Cyclic groups, hence we believe that there is no such efficiently computable $\hat{e}$


How can a message encrypted with the public key be decrypted with the private key? I've been reading about encryption and have a basic understanding of the concept. What I don't understand, however, is how a calculation with one key can result in a number that, through calculation with a different key, leads back to the same number you started with. Are they doing the same calculation (what I mean by this is for example: first multiplying the number with the first key, then dividing it with the second one)? If anyone could in a simple way describe how this works to me; and add some examples with actual numbers in them as well perhaps; that'd be be wonderful.

Perhaps a simplified example or two might help you intuitively understand the concept.

Let's say you want to let your little brother and sister encrypt messages so that either of them can encrypt any message, but only you can decrypt them.  To keep things simple, let's say that the messages are simply numbers from $1$ to $10$.

Your siblings have been recently learning about addition in school, so you come up with a simple encryption scheme based on that.  Specifically, you tell your brother and sister to encrypt their messages like this:

add $7$ to the number to be encrypted, and
take only the last digit of the result.

Your brother and sister do know about subtraction, and they're smart enough to realize that they could try to decrypt a message by just subtracting $7$ from it.  But when they try it, they realize that it only works when the encrypted message is $8$ or $9$ — otherwise, they're not quite sure what to do, since they haven't had negative numbers at school yet (and zero as a number is still kind of an advanced concept for them, too).

You, of course, know how to decrypt the messages, even without using any negative numbers at all!  You just add $3$ to the encrypted message, and again take only the last digit (or $10$, if the last digit is $0$!).  This works because $3+7 = 10$, and adding $10$ to a number leaves its last digit unchanged.

Eventually, your brother and sister work this out on their own, so you have to come up with a better encryption scheme.  Fortunately, by this time your siblings have learned how to multiply numbers, so you base your new scheme on that.  Specifically, you tell them to:

multiply the number to be encrypted by $7$,
if the result is bigger than $10$, subtract the first digit from the second, and
if the result is now negative, add $11$.

(Steps 2 and 3 are, of course, equivalent to reducing the result modulo $11$, but explaining it like that would be a little too advanced for your little siblings — they've only just started learning about division!)

Again, your siblings quickly come up with the idea of trying to divide the encrypted numbers by $7$, but this works even worse than subtraction did with the first scheme — sure, they can calculate $7 \div 7 = 1$, but none of the other numbers between $1$ and $10$ are divisible by $7$.  You, of course, know the trick for decrypting the messages — you just multiply them by $8$, and then repeat steps 2 and 3 above (i.e. reduce the result modulo $11$).

This trick works because $8 \times 7 = 56 = 5 \times 11 + 1$.  Thus, for any number $x$, $8 \times 7 \times x$ equals $5 \times 11 \times x + 1 \times x$; and when you take the remainder modulo $11$, you're just left with the original number $x$!  In other words, $8 \times 7 \equiv 1 \pmod{11}$, so $8$ is the modular multiplicative inverse of $7$ modulo $11$.

This new scheme is a lot harder for your siblings to break, because their grade school math curriculum doesn't really cover modular arithmetic.  Eventually, they do come up with a brute force solution — they just write down every number from $1$ to $10$ and its encrypted result, and use this table to look up which number each encrypted message corresponds to:

$$\begin{array}{lrrrrrrrrrr}
\text{Plaintext:} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\
\hline
\text{Encrypted:} & 7 & 3 & 10 & 6 & 2 & 9 & 5 & 1 & 8 & 4 \\
\end{array}$$

But you just change your scheme to work on two-digit numbers instead, using $101$ as the modulus.  It's a bit more work for you, since you now have to multiply by $29$ to decrypt, but at least your siblings are too lazy to compile a 100-element table.  As long as they choose their messages to be large enough (so that multiplying by $7$ gives a result over $100$) and don't repeat a message whose encryption the other one already knows, this means they can't easily decrypt each other's encrypted messages.

You even briefly think about increasing the modulus to $1{,}001$, but realize that you'd have to choose a different public multiplier, since $1{,}001 = 7 \times 11 \times 13$, and so $7$ is not invertible modulo $1{,}001$.  You kind of like the number $7$, but in this case, $6$ or $8$ would work better.  Or you could just skip all the way to $10{,}001$, which has no small factors.

The multiplicative encryption scheme works great (at least with a large enough modulus to resist brute force tabulation), until your sister one day stumbles across a web page about the extended Euclidean algorithm.  Being clever, she realizes that she can use it to quickly calculate the modular inverse for any public multiplier, and thus read any encrypted message, no matter what the public multiplier or the modulus is!

Suddenly, you need to come up with something even more secure.  The obvious next step would be to replace the multiplication with exponentation, something like this:

raise the number to be encrypted to the $e$-th power, and
take the remainder of the result modulo $n$.

You're hoping that, if you choose the right exponent $e$ and modulus $n$, you might be able to find another exponent $d$ such that raising the encrypted number to the $d$-th power modulo $n$ would just happen to "cancel out" the $e$-th power, leaving you with the original number.  In other words, you'd need a modulus $n$ and two exponents $e$ and $d$, such that $(x^e)^d \equiv x \pmod n$ for all numbers $x$.

It's not exactly obvious that such pairs of exponents should exist, but you're feeling optimistic — after all, it worked for addition and multiplication, so why not exponentiation too?  In fact, you remember a number theory class you took in college mentioned something about modular multiplicative groups that might've been relevant.

Looking through your notes, you realize that, since $(x^e)^d = x^{e \times d}$, you really just need to find a number $\lambda$ such that $x^{\lambda+1} \equiv x \pmod n$ for all $x$; then adding or subtracting multiples of $\lambda$ from the exponent won't change the result, and so you can simply use the same extended Euclidean algorithm you used to generate the private keys for the previous encryption scheme (and which your sister used to break it!) to find $e$ and $d$ such that $e \times d \equiv 1 \pmod \lambda$.

You can even choose $e$ freely (as long as it doesn't share a factor with $\lambda$!) to make the calculations easier for your siblings.  For example, letting $e = 3$ might be a good choice.  Of course, the resulting secret exponent $d$ probably won't be so convenient, but that's all right — you know an efficient algorithm for exponentiation modulo $n$.

Your notes even mention that the smallest such $\lambda$, for a given modulus $n$, is given by Carmichael's reduced totient function.  (Euler's totient function $\phi$, which is always a multiple of $\lambda$, could of course be used, too.)

But there's a problem!  On one hand, you need to know $\lambda$ to calculate $e$ and $d$ — but if anyone else (like your too-clever-by-half sister) could figure it out, they could break the encryption!  So you somehow need to choose the modulus $n$ so that you can easily calculate $\lambda(n)$, but nobody else can.

Obviously, choosing a prime modulus like $101$ would be right out (never mind that your siblings have had programming classes at school by now, and could easily write a program to calculate a 100-element lookup table), since $\lambda(n) = n-1$ for prime $n$.  But what if you took two random primes $p$ and $q$, and multiplied them together?  Then $\lambda(p \times q)$ would just be the least common multiple of $p-1$ and $q-1$, which is easy to calculate.  But you're pretty sure that, given just $n = p \times q$, even your sister won't find it easy to break $n$ back into its prime factors, and so won't be able to calculate $\lambda$.

And that's basically where we are today with RSA.

As long as we choose the prime factors $p$ and $q$ of the modulus $n$ to be large enough (and they do need to be quite large, at least several hundred digits long, to resist the most advanced factoring algorithms and the most powerful computers) and make sure that our messages don't repeat and aren't too small (to resists brute force attacks and simple attempts to take the $e$-th root; this is generally achieved by padding the messages appropriately), there's no known efficient way to calculate $x$ from $x^e \bmod n$.

That is, unless you happen to know the secret number $d$, chosen so that $e \times d \equiv 1 \pmod \lambda$, in which case you can just raise the encrypted message to the $d$-th power modulo $n$, and obtain $(x^e)^d = x^{e \times d} = x^{k\lambda+1} \equiv x \pmod n$.


What is a clearsigned message? PGP Digital Timestamping Service webpage mentions

The service operates in a number of different "modes" depending upon the required results. The current modes are:-
post: forwarding an outbound message with a proof of posting certificate
clear: the received message is clearsigned and returned to the sender
header: the received message (with headers) is clearsigned and returned to the sender
text: the received message is signed and returned ASCII armoured to the sender
pgp: the received message (which must be ASCII armoured) is assumed to be a PGP file which is then signed and returned to the sender
binary: the received message (which must be ASCII armoured) is assumed not to be a PGP file which is then signed and returned to the sender

What is a clearsigned message? I searched around quite a bit using Duck Duck Go, and on this site but I couldn't find an explanation.

From dictionary.university with search clearsigned definition

Dictionary of Internet Terms A digitally signed S/MIME or PGP message in which the content of the message is readable even if the signature is not.

A message that is digitally signed but not encrypted.

These might be helpful, too;

Cleartext  is readable data transmitted or stored “in the clear” (i.e. unencrypted)

Plaintext is the input to an encryption algorithm

Ciphertext is the unreadable output of an encryption algorithm

Plain text means its text that hasn’t been formatted (i.e., a plain text file)
Note that plain text might be an ambiguous term without context. See the commnets.


The purpose of ADATA in GCM I have a hard time understanding the purpose of ADATA in GCM algorithm. Is ADATA the plaintext itself we would like to encrypt or is it some random data as for the IV ? Otherwise from what I have understood so far, is that one cannot get the GMAC (i.e. Tag) of some plaintext unless he does encrypt it where the ciphertext is fed to the XOR function. Is that right?

GCM is an algorithm for building an "authenticated encryption with associated data" (AEAD) scheme. The ADATA in the spec refers to associated data. Associated data is auxiliary information or metadata that needs to be in plaintext for functionality reasons (for example, headers in an IP packet) but which needs some integrity guarantees. The idea of AEAD was folklore, but Phil Rogaway introduced it as a design goal for symmetric encryption and formalized security notions for it. See this paper for more details.


Fiat-Shamir paradigm and the forking lemma I am reading the proof by Pointcheval and Stern and by Bellare and Neven about the forking lemma. The papers discuss the security proof of digital signatures by applying the lemma. It seems also mentioned that the same proof idea works for showing the Fiat-Shamir transformed interactive proof system is sound in the random oracle model.

I am not sure I understand why the forking lemma implies the Fiat-Shamir transformed noninteractive protocol is sound using a random oracle, or it is essential to apply it for only the soundness. There are many papers about instantiation in the plain model, but that is beyond what I am trying to understand for now.

It would be appreciated if anyone could explain the connection, or point some good references about that.

Let's recall important definitions. A proof system $(\mathsf{P}, \mathsf{V})$ for an NP language $\mathcal{L}$ is a pair of interactive Turing machines where the prover ($\mathsf{P}$) and the verifier ($\mathsf{V}$) receive a common input $\ell \in \{0,1\}^*$ and the prover receives an additional input $w \in \{0,1\}^*$ that is the witness for $\ell$, i.e., the relation $\mathcal{R}_\mathcal{L}$ defined by the NP language $\mathcal{L}$ satisfies $\mathcal{R}_\mathcal{L}(\ell,w) = 1$. The prover and verifier exchange a couple of messages and finally the verifier outputs a single bit denoted by $\mathsf{out}_\mathsf{V}(\langle\mathsf{P}(\ell,w)\leftrightarrow\mathsf{V}(\ell)\rangle)$, indicating whether the verifier accepts the proof (1) or rejects it (0). The proof system is public-coin if the verifier's messages consist of pure, unprocessed randomness. In this case the Fiat-Shamir heuristic says that no security is lost by replacing these randomly chosen messages by the hash of all messages up until that point. (And since there is a proof of this fact, albeit in the random oracle model, it is technically wrong to refer to it as a heuristic --- hence the more common phrase "Fiat-Shamir transform".)

The proof system is complete for a language $\mathcal{L} \in$ NP if honest provers are likely to succeed, i.e., $\forall \ell \in \mathcal{L} \, . \, \forall w \in \{0,1\}^* \, . \, \mathrm{Pr}[\mathcal{R}_\mathcal{L}(\ell,w) = 1 \, \Rightarrow \, \mathsf{out}_\mathsf{V}(\langle\mathsf{P}(\ell,w) \leftrightarrow \mathsf{V}(\ell)\rangle) = 1] \geq 1 - \mathsf{negl}(\lambda)$, for some function $\mathsf{negl}(\lambda)$ that is negligible in the security parameter.

The proof system is zero-knowledge if the transcript, i.e., the list of all exchanged messages which is denoted by $\langle\mathsf{P}(\ell,v) \leftrightarrow \mathsf{V}(\ell)\rangle$, is indistinguishable from the output of some simulator $\mathsf{S}$ that receives the string $\ell$ but not the witness $w$. Formally, $\forall \ell \in \mathcal{L} \, . \, \forall w \in \{0,1\}^* \, . \, \mathcal{R}_\mathcal{L}(\ell, w) = 1 \, \Rightarrow \, \langle\mathsf{P}(\ell,w) \leftrightarrow \mathsf{V}(\ell)\rangle \sim \mathsf{S}(\ell)$. Here $\sim$ denotes your favorite notion of indistinguishability of probability distributions, i.e., perfect, statistical, or computational.

With respect to soundness, it is important to draw a clear distinction between two related notions. First, the proof system has plain soundness if no (appropriately bounded) adversary $\mathsf{A}$ can make the verifier accept nonmembers of the language: $\forall n \not \in \mathcal{L} \, . \, \mathrm{Pr}[\mathsf{out}_\mathsf{V}(\langle \mathsf{A}(n) \leftrightarrow \mathsf{V}(n)\rangle) = 1] \leq \mathsf{negl}(\lambda)$. I call this notion plain soundness for the sake of exposition but the literature refers to it simply as soundness. Second, the proof system has knowledge-soundness if there is an (appropriately efficient) extractor machine $E$ that can extract and output a valid witness from any successful proof-forger $\mathsf{B}$, whether it receives the witness $w$ or not. Formally, $\forall \ell \in \mathcal{L} \, . \, \mathrm{Pr}[\mathsf{out}_\mathsf{V}(\langle\mathsf{B}(\ell) \leftrightarrow \mathsf{V}(\ell)\rangle) = 1 \, \Rightarrow \, \mathcal{R}_\mathcal{L}(\ell, \mathsf{E}^\mathsf{B}()) = 1] \geq \mathsf{noti}(\lambda)$, where $\mathsf{noti}(\lambda)$ is some noticeable function of the security parameter. Here $\mathsf{E}^\mathsf{B}$ means that the algorithm $\mathsf{E}$ has black-box access to $\mathsf{B}$, meaning that $\mathsf{E}$ is allowed to interact with $\mathsf{B}$ through messages that have the format of the proof system but $\mathsf{E}$ is not allowed to view or alter $\mathsf{B}$'s state. The literature also refers to this notion as witness-extractability and, confusingly, as soundess. Proof systems with this property are proofs of knowledge.

For many languages, knowledge-soundness is the relevant property and plain soundness is not. Consider for instance the standard Schnorr proof of knowledge of a discrete logarithm, whereby knowledge of an exponent $x \in \mathbb{Z}_{|\mathbb{G}|}$ is proven such that exponentiation-by-$x$ sends $g \in \mathbb{G}$ to $X = g^x \in \mathbb{G}$. When $g$ is a generator, as it usually is, plain soundness is trivial: since $X$ is a group element it must have a discrete logarithm with respect to $g$. However, for circuit-satisfiability type languages, plain soundness is usually more important than knowledge-soundness.

To prove plain soundness, it suffices to count the number of possible challenges from the verifier that expose a cheating prover; and the number of possible challenges that allow him to get away with the fraud. The ratio between the number of challenges that do not expose the cheating prover and the total number is known as the soundness error --- the fact that the verifier chooses his challenges at random makes this ratio equal the cheating prover's success probability and if it is negligible in the security parameter then plain soundness is satisfied. With the Fiat-Shamir transform, it suffices to argue from the difficulty of finding particular preimages to the random oracle. Formally, you can model the (classical) random oracle as a procedure that samples a random output only when it is needed and no sooner. Then the only way to find an input that leads to an answerable challenge is to test enough of them.

To prove knowledge-soundness, one must provide a description for the witness-extractor $\mathsf{E}$ and show that its success probability is noticeable if $\mathsf{B}$ has a noticeable success probability of convincing the verifier. The Forking Lemma provides such a description:

$\mathsf{E}$ plays the part of $\mathsf{V}$ honestly and runs the protocol with $\mathsf{B}$ thereby obtaining one transcript $T_1$.
$\mathsf{E}$ rewinds $\mathsf{B}$ to just after one of its messages, typically where it commits to something.
Once again, $\mathsf{E}$ plays the part of $\mathsf{V}$ honestly but with different randomness, thereby obtaining a second transcript $T_2$.

The language is structured in such a way that it is easy to extract a witness from two valid transcripts with the same commitments but different challenges. This description involves only one instance of rewinding; it may be necessary to rewind multiple times to obtain a set of transcripts satisfying very particular constraints.

Intuitively, the success probability of the extractor $\mathsf{E}$ should be somehow related to the success probability of the proof-forger $\mathsf{B}$. However, Bellare and Neven show that there is necessarily a square-root security degradation. In particular, if the extractor $\mathsf{E}$ splits into 2 branches, then $\mathrm{Pr}[\mathsf{B} \, \mathit{success}] \leq \sqrt{\mathrm{Pr}[\mathsf{E} \, \mathit{success}]}$, because the proof-forger $\mathsf{B}$ has to be successful in both branches. This means that even if the discrete logarithm problem takes $2^{128}$ units of work to compute, the proof shows only that the adversary as to perform at least $2^{64}$. In general, if the extraction requires $b$ branches, then the proof technique will induce a $b$th root degradation.

With the Fiat-Shamir transform, the random messages from the verifier are replaced with the response from the random oracle upon being queried with the list of protocol messages up until that point. This random oracle is simulated by the extractor $\mathsf{E}$, meaning that it can choose which responses the random oracle will provide. The trick is that by rewinding the proof-forger $\mathsf{B}$, the extractor $\mathsf{E}$ can reprogram different outputs for the random oracle. In particular, the extractor $\mathsf{E}$ proceeds as follows.

$\mathsf{E}$ runs $\mathsf{B}$ and provides it access with a random oracle $\mathsf{RO}$ whose responses are sampled uniformly at random when they are needed, and obviously conformant to the responses of previous queries. This provides the extractor $\mathsf{E}$ with the first transcript $T$.
$\mathsf{E}$ rewinds $\mathsf{B}$ to just after one of its messages, typically where it commits to something. Note that the list of all messages up until this point is fixed; denote this list by $L$.
$\mathsf{E}$ replays $\mathsf{B}$ again from this point but provides it with access to a random oracle $\mathsf{RO}'$ whose only difference is its response to $L$. In particular, this response has been sampled at random. This second execution of $\mathsf{B}$ provides $\mathsf{E}$ with the second transcript $T_2$.

With $T_1$ and $T_2$, the extractor $\mathsf{E}$ should be able to extract the witness. If more transcripts are needed then the extractor rewinds and replays the proof-forger as often as necessary.


Cryptography standards on key size There are many limits on key size. As far as I know 56 bit in USA  and 40 bits in India without license. On the other hand much higher 128 bit or 1024 or 4096 bit for banking and other purposes. So what will one do (I am not starting any banking business or something, just asking in case a man wants to make a secure app must he take license?) Without license one cannot comply with both.
Secondly I am new to TLS and cryptography in general. In case of https connection who decides the encryption strength the server or client. How can I force a less than 32-bit encryption on server and clientside. If the data is read then it's not a problem but want to prevent man in the middle attacks.

There are many limits on key size. As far as I know 56 bit in USA and 40 bits in India without license.

In general, this is incorrect, at least for the US. However, when exporting cryptography you should be aware of export regulations for countries. It does generally matter how the cryptography is made available and to who. This site however doesn't give any legal advice.

In case of https connection who decides the encryption strength the server or client.

The client sends out the cipher suites, but the server gets to choose. Generally the server will support a small subset of ciphers for TLS 1.2. For TLS 1.3 the set of cipher suites was deliberately made smaller in the protocol specification.

How can I force a less than 32-bit encryption on server and clientside.

Generally you cannot get any cipher suite with so little security. Basically it would equate to no security at all, so you'd just be fooling yourself.

If the data is read then it's not a problem but want to prevent man in the middle attacks.

This means you need to authenticate the handshake and provide message integrity. "Unfortunately" if the key agreement and authentication is strong, then the encryption will be strong as well.
The only way to have weak encryption and strong authentication is therefore to deliberately weaken the encryption component.


How are AEAD, GCM, CBC, Poly1305, EtM, MtE and E&M related? I am using OpenSSL 1.1.1 to implement a TLS 1.3 communication module so I tried to learn how data integrity and authentication is ensured. I read a lot about AEAD, GCM, CBC, Poly1305, EtM, MtE and E&M to the point that I know what they are, but I do not know how they are related to each other. My Questions are

I know that TLS 1.3 uses AEAD. Does that mean that it is EtM, MtE or E&M?
Is GCM an EtM algorithm for block ciphers?
What does OpenSSL use by default? EtM, MtE or E&M? Which are supported?

I do not know how they are related to each other.

EtM, MtE and E&M are generic constructions that take pairs of schemes that satisfy weaker security notions (chosen-plaintext security and unforgeability) and turn them into AEAD-secure schemes.
GCM is a construction that takes a 128-bit block cipher and turns it into - an AEAD-secure scheme and internally uses something like EtM for that.
CBC is one construction that takes a block cipher and turns it into something that is suitable for the encryption part of the EtM, MtE and E&M schemes (though it is admittedly not easy to do this right in face of padding / timing attacks).
Poly1305 is a one-time MAC (that is a MAC that is only secure when used at most once for a given key) which can be paired up with e.g. a block cipher (to generate one-time keys from nonces) to become a regular MAC suitable for the MAC part in EtM, MtE and E&M schemes.

  What does OpenSSL use by default?

Apparently OpenSSL will default to using either AES-GCM or ChaCha20-Poly1305 for symmetric encryption

  Which are supported?

TLS 1.3 abandoned the concept of these generic compositions so you will only find complete AEAD schemes to be specified as ciphersuite.


Session-specific Symmetric Key Derivation Using SHA256 I was wondering if there were any security implications of deriving session keys from a symmetric key using SHA256 in the following manner: $Ks = SHA256(Nonce||K)$, where $Nonce$ is the session specific nonce and $K$ is the pre-shared symmetric key. And $Ks$ will be derived at both ends as mentioned.

As far as I am aware, length extension attacks are not applicable here as being able to append additional data to the input makes no difference. Would $Ks = HMAC(Nonce, K)$ be any different security-wise? What would be an advisable way of going about my requirement?

HMAC: The hmac version is considered slightly more secure than sha-256, assuming it's also based on SHA-256, because the HMAC formulation folds in the key material with 2 rounds of hashing, making it harder to use a chosen plaintext attack on the digest.

SHA-256: SHA-256 should be relatively secure against chosen plaintext attacks, but it's better to be safe than sorry.

You can also achieve a higher level of assurance and forward security provided $K$ is not long-lived, but rather is chained to the immediately previous session.

For some stored value D1:

K2 = HMAC(Nonce,D1)     // session key
D2 = HMAC(Nonce,K2)     // stored material for a future session
authtoken = E(K2,Nonce) // auth token proving client derived K2 correctly

If you want to authenticate the server, you can also pass a token from server to client, thus proving the server knows D1.  Something like,

servtoken = E(K2,authtoken)   // proof server knows D1

Client checks servtoken before sending authtoken.  D1 is discarded and replaced with D2. So you have bidirectional authentication and forward security.


"Order" in cryptographic terms for generators Frequently I have seen people use the term order in cryptography (the group theoretic one). I have a mathematical background and order (say for prime modulus $p$) is defined as the smallest integer such that

$$a^r \equiv 1 \pmod p$$

So a generator (something which has the max possible order i.e order is $\phi(p)=p-1$) will have order (p-1). In case of a composite group, the generator should have an order $=\phi(N)$.

How is it that frequently I read in Crypto literature that people say generator has order N?

For example: The first answer at: When do we need composite order groups for bilinear maps and when prime order?

Am I missing some details or is my understanding incorrect?

You probably know that cyclic groups of any order exist, so it is perfectly possible to have a cyclic group of order $pq$, and to consider a generator thereof.


How insecure in practice? I am in attempt to understand relative insecurity of certain encryption schemes. Particularly of interest is DES and RC2. I know AES is better and should be used to encrypt. But practically, if something is encrypted with (1) DES or (2) RC2 (3) RC4 what level security is achieved.

In affect I am asking:

If a adversery is given a {DES/RC2/RC4} ciphertext, is it possible that they can decrypt or can a determined adversary definitely decrypt?

Yes, an adversary can definitely decrypt a DES message, given sufficient funding.  Fifteen years ago, in 1998, the EFF built a DES cracker (nicknamed Deep Crack) that can recover a DES key in a day.  Today, anyone with the money can purchase a commercially available DES cracker named COPACOBANA.

For RC2, I'm not aware of any practical attacks.  (You still shouldn't use it.)

For RC4, the answer is complicated.  It depends.  It depends upon how you use RC4.  There are lots of attacks known, and whether they will be applicable or not to your particular situation will depend upon many fine details of your particular situation.


Why are there limitations on using encryption with keys beyond certain length? I am writing a java program to encrypt a message using 256-bit AES encryption, but I am getting illegal key size error, I have read that I have to use some JCE Unlimited Strength Jurisdiction Policy Files to encrypt/decrypt message with key of 256-bit or longer, but I do not understand why there is a limit on using a key size? Why using 256-bit encryption is disabled in Java by default?

Is it a crime to encrypt/decrypt files using 256-bit keys?

There are many different cryptography laws in different nations. Some countries prohibit export of cryptography software and/or encryption algorithms or cryptoanalysis methods.

In some countries a license is required to use encryption software, and a few countries ban citizens from encrypting their internet communication. Some countries require decryption keys to be recoverable in case of a police investigation.

Issues regarding cryptography law fall into four categories:

Export control, which is the restriction on export of cryptography methods within a country to other countries
or commercial entities. There are international export control agreements, the main one being the Wassenaar Arrangement. The Wassenaar Arrangement was created after the dissolution of COCOM (Coordinating committee for Multilateral Export Controls), which in 1989 "decontrolled password and authentication-only cryptography."
Import controls, which is the restriction on using certain types of
cryptography within a country.
Patent issues, which deal with the use of cryptography tools that are
patented.
Search and seizure issues, on whether and under what circumstances, a
person can be compelled to decrypt data files or reveal an encryption
key.

Restrictions on the import of cryptography

Countries may wish to restrict import of cryptography technologies for a number of reasons:

Cryptography may increase levels of privacy within the country beyond
what the government wishes.
Citizens can anonymously communicate with each other, preventing any
external party from monitoring them.
Encrypted transactions may impede external entities to control the
conducting of business.
Imported cryptography may have backdoors or security holes,
intentional or not, which allow foreigners to spy on persons using
the imported cryptography; therefore the use of cryptography is
restricted to that which the government thinks is safe, or which it
develops itself.

The Electronic Privacy Information Center and Global Internet Liberty Campaign reports use a color code to indicate the level of restriction, with the following meanings:

Green: No restriction
Yellow: License required for importation
Red: Total ban

Here is List of Countries, each with their level of import restrictions.

and List of Countries with their import/export restrictions details and explanation

Import Limits on Cryptographic Algorithms in Java

Due to import regulations in some countries, the Oracle implementation provides a default cryptographic jurisdiction policy file that limits the strength of cryptographic algorithms.

If stronger algorithms are needed (for example, AES with 256-bit keys), the JCE Unlimited Strength Jurisdiction Policy Files must be obtained and installed in the JDK/JRE.

It is the user's responsibility to verify that this action is permissible under local regulations.


How to attack RSA-CRT with large public exponent? Suppose we have $(n,e)$ and the ciphertext $c$ where the public exponent $e$ is of the same length, 1023-bit, as the modulus $n$. It is also assumed that the factors of $n$ are balanced. The message is decrypted using CRT with small exponents but unknown to us, attacker. Is it possible to decrypt $c$ in such a scenario?

I have checked the Wiener's attack on https://en.wikipedia.org/wiki/Wiener%27s_attack but the example requires those parameters that are not available to us in this situation.

There is a paper by Daniel Bleichenbacher and Alexander May called "New attacks on RSA with small secret CRT-Exponents" (you can find it under http://www.cits.rub.de/imperia/md/content/may/paper/crt.pdf). They are not quite able to break the RSA under your assumptions. I'm not aware of better results, but I didn't look at the list of articles citing this paper.


Should we use modulus switching when dealing with ciphertexts encrypted in different rings? Having a homomorphic encryption scheme like BGV or LTV-FHE at some point it is possible in the homomorphic evaluation to deal with ciphertexts that are encrypted with respect to different moduli.

For the chosen scheme we have a ladder of decreasing moduli $q_0 > ... > q_{t-1}$. If there is a ciphertext $c_1$ w.r.t $R_{q_2}$ and another ciphertext $c_2$ w.r.t to $R_{q_4}$, the first ciphertext should be "switched" into the ring $R_{q_4}$ and only then the homomorphic computation could be done ?

Or maybe this situation should be avoided ? Then, if this is the case, how about computation represented as an unbalanced tree of multiplications? At some point there will be a need to multiply two ciphertexts encrypted in different subrings.

The problem is that operations between such $c_1$ and $c_2$ are not even defined. You have to reduce the coefficients of the resulting polynomial modulus either $q_2$ or $q_4$, so, you have to switch one of them.

Switch $c_2$ into $R_{q_2}$ would work as well, but since it would increase the noise in $c_2$, it is smarter to switch $c_1$ into $R_{q_4}$ (which gives you meaningful operations and also decrease the $c_1$'s noise).

I think the only way to avoid this switching is to treat both the polynomials as elements of $R$ and check if the coefficients of the resultant polynomials are not greater than $q_4$, because this means that no reduction would be done in the coefficients if operations were done in  $R_{q_4}$ and so the resultant polynomial is a valid ciphertext in $R_{q_4}$ and in $R_{q_2}$.

Anyway, the modulus switching operations is not expensive, and it also reduces the noise, so, I don't see advantages in avoiding to do them.


Please prove distinguishability given a non-perfectly secure cipher I'm trying to prove that a perfectly secure cipher yields indistinguishability. I already know and can prove that a perfect cipher => indistinguishability by the following proof:

\begin{align}
\Pr(Enc(m_1) = c) = & \Pr(C = c | P = m_1) \\
 & = \frac{\Pr(C = c \land P = m_1)}{\Pr(P = m_1)} \\
 & = \frac{\Pr(C = c) | \Pr(P = m_1|C = c)}{\Pr(P = m_1)}\\
 & = \frac{\Pr(C = c) | \Pr(P = m_1)}{\Pr(P = m_1)}\\
 & = \Pr(C = c)\\
\end{align}

Please help me prove indistinguishability will yield a perfect/secure cipher (indistinguishability => perfect cipher) which is the opposite direction.

The proof in the question is not about the perfect secrecy $\implies$ indistinguishability. It is about proving that; if perfect secrecy than we have $$ Pr[C=c| M=m] = Pr[C=c]$$ Also, we don't need the $\wedge$ step, just use Bayes' Theorem directly. The reverse (1) of this also true that is if we have $$ Pr[C=c| M=m] = Pr[C=c]$$ that we have perfect secrecy.

Now assuming that we have indistinguishability. That is; for every probability distribution over the message space $\mathcal{M}$ and every $m_0,m_1 \in \mathcal{M}$, and for every $c \in \mathcal{C}$;

$$Pr[C=c| M=m_0] = Pr[C=c | M=m_1] $$ we will show that we have prefect secrecy.

Since, the equation holds for ever $m_0,m_1$ we can say $Pr[C=c| M=m_0] = Pr[C=c | M=m_1] = p$ (2).

Now, write $Pr[C=c]$ as;

\begin{align}
Pr[C=c] & = \sum_{m\in\mathcal{M}} Pr[C=c | M=m] \cdot Pr[M=m] \\
 & = \sum_{m\in\mathcal{M}} p \cdot  Pr[M=m] \\
 & = p \sum_{m\in\mathcal{M}} Pr[M=m] \quad\quad\quad\quad \\
 & = p \\
 & = Pr[C=c| M = m_0]  \quad\quad\quad\quad\quad\quad//(\text{use }2)
\end{align}
we have;

$Pr[C=c] = Pr[C=c| M = m_0]$ ,

now use (2);

$$Pr[M=m | C=c] = Pr[M = m_0]$$ therefore, indistinguishability $\implies$ perfect cipher


Problem about complexity of Chinese remainder theorem I have a question about CRT.
Assuming, that we have this system (S):
x=a0 mod n0
x=a1 mod n1
with N=n0*n1 and n0,n1 are two distinct prime numbers.
Then the complexity in terms of binary operation is O(log(N)^2) in order to find x.
My problem is that I study  the complexity of Pohlig–Hellman algorithm in term of the number of multiplication in a cyclic group G of order N=n1*n0. Pohlig–Hellman algorithm use CRT algorithm.
So, I don't see how can I measure the complexity of Chinese remainder theorem in term of the number of multiplication in G of order N.
Any ideas?

So, I don't see how can I measure the complexity of Chinese remainder theorem in term of the number of multiplication in G of order N.
Any ideas?

Well, the standard way to solve for $x$ (given that $n_0, n_1$ are relatively prime) is to compute:
$$x = n_1 ((a_0 - a_1) n_1^{-1} \bmod n_0) + a_1$$
(where $n_1^{-1}$ is computed modulo $n_0$)
It is straightforward to verify that:
$$ 0 \le x < n_0n_1$$
$$ x \equiv a_0 \pmod{ n_0 }$$
$$ x \equiv a_1 \pmod{ n_1 }$$
As for the cost of the computation, $n_1^{-1}$ can be computed with $O(\log N)$ multiplication operations; the rest of the operations are two multiplication operations (one modulo $n_0$), and two addition/subtraction operations.

So, I don't see how can I measure the complexity of Chinese remainder theorem in term of the number of multiplication in G of order N.

So, in Pohlig-Hellman, you compute $H = a_0(n_1G)$ and $H = a_1(n_0G)$, and combine $a_0$ and $a_1$ to form the value $x$ s.t. $H = xG$.  Computing $a_0, a_1$ takes $O(\sqrt{\max(n_0, n_1)})$ multiplications (assuming the curve does not have any special form that allows us to compute the discrete logs faster); combining $a_0, a_1$ doesn't take any (because those are computed using integer computations, not elliptic curve operations).


What is the difference between a digest and a hash function? I was wondering about the difference between these two terms...
What is the difference between a digest and a hash function?

The digest is the output of the hash function.

For example, sha256 has a digest of 256 bits, i.e. its digest has a length of 32 bytes.

That's it really.


Do key-dependent S-boxes make efficient constant-time software implementations almost impossible? It seems to me that algorithms like Blowfish and Twofish with key-dependent S-boxes are almost impossible to implement without table lookups, and thus are almost impossible to implement in software without being vulnerable to timing attacks (other than by linear search through a large array, which is much, much slower).  Since these algorithms are also ill-suited to hardware implementation (since the S-box must be stored in RAM), this seems to make the algorithms suboptimal for all purposes.

Is this assessment correct?  It seems strange to me that I can come to such a strong conclusion.  Yet I cannot think of any way to (reasonably) implement key-dependent S-boxes in constant time, so my point seems to still stand.

The point in the question makes senses, especially if one restricts to portable software implementations. But:

Small or moderately large constant-time RAM tables are reasonable, efficient, and (thus) common hardware building blocks. They are often used in DPA-protected DES and AES hardware coprocessors. Thus we can't dismiss key-dependent S-tables in hardware.
When knowing and controlling one's CPU well enough, constant-time table lookups are often possible (e.g. if there is no cache for data RAM, as is the case on many embedded CPUs).
There are other conceivable methods to guard against purely timing attacks, including releasing results with a fixed delay counted from start of computation, e.g. with the help of a hardware timer (however there often are other side-channels than pure timing, and that complicates things, a lot).


Why is the whole initial state used in the final addition of Salsa20 and ChaCha? Both Salsa20 and ChaCha basically work like this:

Put the key, the nonce, the sequence number and a constant into a 4x4 matrix of 32-bit words.
Transform the matrix invertibly with a number of ARX rounds.
Add the initial matrix into the current state to produce the output block.

Now, as discussed e.g. in this currently featured question, the final addition is required to prevent simple backwards computation from revealing the key. However, my question is: why is the whole initial matrix added in, rather than only the key part?

It seems that the addition of the rest of the matrix is mostly wasted effort, since they are publicly known numbers that an attacker with a known plaintext can simply subtract again.

On the other hand, there is a clear downside of extra memory and computation required. The latter is probably negligible compared to the whole cipher, but the former could be important, especially for hardware implementations. If only the key was added, the nonce and the sequence number would not need to be accessed again, saving a sixth of the state required (if you ignore constants).

Note that, in Salsa20, the loads and additions of the key words ($x_1$, $x_2$, $x_3$,
  $x_4$, $x_{11}$, $x_{12}$, $x_{13}$, $x_{14}$) are critical for security, since the double-round function is
  trivially invertible. One might think that the remaining loads and additions could
  be skipped without sacrificing security, achieving almost half of the HSalsa20
  savings. However, this change would interfere with the vector loads and vector
  additions used in many high-speed Salsa20 implementations.

from D. J. Bernstein - Extending the Salsa20 nonce

Since you need to supply the nonce/counter to pass them to the next block, you need to keep track of them anyways, eliminating the space savings.


Security of AES under modification of Sboxes and/or MDS mixing layer Is the security of AES algorithm increased by using many s boxes at the same time instead of using only one s box , and the same question for using many MDS  instead of only one.

Depends on what exactly you’re doing.

Assuming the regular AES algo being implemented like that, it might merely buy you some time/speed – but the standard AES algorithm can and will not get “stronger” (as in ”more secure”).

See, just because you implement the algorithm in a way that it works through several boxes “at the same time” (no  matter what exactly you mean when saying “at the same time”, as there are multiple ways to interpret that), that doesn’t mean you influence or even increase the AES algorithm’s security.

AES will always be AES. If it weren’t, you’ld quickly crash into incompatibilities due to practically having changed the AES algorithm… which would end up in being a completely different cipher, which might (or might not) be based on the AES algo and/or inherit some of its security features.

Which brings me back to my first line: “Depends on what exactly you’re doing.”

If you’re talking about standard AES, the answer boils down to “no, it won’t buy you any security… at all”. AES will always provide the same security, no matter how you implement it. (Off course, I’m assuming you implement it correctly and adher to the AES specification.)
If you’re talking about changing/modifying the AES standard, the answer ends up being a “maybe, but it will be hard to prove your new AES-inspired block cipher is actually safer than AES and it will be even harder to convince people that prefering your new block cipher indeed makes sense. Also, your new AES-inspired block cipher will definitely end up being incompatible to the standard AES algo as well as the several AES implementations out there”.


Elgamal problem on $\mathbb{QR}_p$ with $p$ a safe prime I need some orientation to solve the following problem:

Let $p = 2q+1$ be a safe prime and $s(x)$ the smallest of the two square roots of $x$ modulo $p$. Then:

Determine the distribution of $s(g^{ab})$ for $a,b$ chosen uniformly in $\mathbb{Z}_q$.
Explicitly formulate Elgamal wrt $\mathbb{QR}_p$ modulo a safe prime $p$. Use $s(x)$ from above for Dec.
Let $G = \langle g \rangle$ be any group of prime order $q$. Determine the distribution of $g^{ab}$ for $a,b$ uniformly distributed on $\mathbb{Z}_q$.

My solution

1) It seems I have to study the distribution of  $ab \; mod \; q = c$. Because the mapping $s^{-1}: \{1,\ldots,\frac{p-1}{2}\} \to \mathbb{QR}_p$ is one-to-one and efficiently invertible. Since $g$ can be assumed to be a generator of $\mathbb{QR}_p$ then it is sufficient to study the exponents (each exponent will correspond exactly to one "smallest" square root.

Now, considering the possible $q^2$ pairs. There are $q+(q-1)$ pairs yielding a zero. For $c \neq 0$, one can fix $a$ and solve immediately for $b$ which yields $q-1$ possibilities for $c$. Adding up, we have $2q-1+(q-1)^2 = q^2$ as expected.

So the distribution is $P[s(g^{ab}) = i] = \frac{q-1}{q^2}$ if $i \neq 1$ and $\frac{2q-1}{q^2}$ if $i = 1$.

2) I don't currently see how to take $s$ into play here.

3) I believe the reasoning is equal to point 1).

$P[s(g^{ab}) = i] = \frac{q-1}{q^2}$ if $i \neq 1$ and $\frac{2q-1}{q^2}$ if $i = 1$.

We assume that $g$ is a generator of $\mathbb{QR}_p = \mathbb Z_q$. Then, as you said, in order to study the probability that $g^{ab} = i = g^c$ for a fixed $c$, we can calculate the probability that $ab = c\bmod q$.

In general, the probability that a random pair $(a,b)\in\mathbb Z_q\times\mathbb Z_q$ gives you a fixed non-zero number $c$ is $(q-1)/q^2$, and if $c=0$ then this probability is $(2q-1)/q^2$.

  2) I don't currently see how to take $s$ into play here.

ElGamal encryption scheme allows you to encrypt elements $m\in\mathbb{QR}_p$ as $m\cdot g^{ab}$. However, the message you want to encrypt is likely not to be an element of this set.
In practice, you encrypt bit-strings, which are easier to map into $\{1,\ldots,(p-1)/2\}$. Then you take an element $y$ in this interval and map it to $m\in\mathbb{QR}_p$ via $m = y^2$, and use $m$ as above.
Now you can see that you need $s$ for decryption in order to recover $y$ from $m$.

  3) I believe the reasoning is equal to point 1).

Agreed. The idea is that with a safe prime $p = 2q+1$ you know that $\mathbb{QR}_p = \mathbb{Z}_q$, whereas in general this structure could be more involved.
However, once you're working over $\mathbb{Z}_q$, the analysis is the same.


Direct sum of Binary numbers In Mixcolumns I have just started learning cryptography and I am trying to make sense of the direct sum on some binary numbers.

I am trying to find a column of a state space after a Mixcolumns operation has been performed.

For example, to find $c_0$, I have

$c_0=((02)\cdot10000100)\oplus((03)\cdot(10000001))\oplus10000001\oplus00100001$
$=(100001000\oplus100011011)\oplus(110000011\oplus100011011))\oplus10000001\oplus00100001$

So i understand exactly what is going on up until the next line:

$=00010011 ⊕ 10011000 ⊕ 10000001 ⊕ 00100001$

How does the direct sum of

$(100001000\oplus100011011)\oplus(110000011\oplus100011011)=00010011 ⊕ 10011000$?

I dont understand how the 9 digit binary numbers direct sum makes an 8 digit binary number??

the next line reads

$= 00101011$

Again, I do not understand how this answer has been obtained!

Could someone please explain/show how this is done as my notes do not say and I cannot find a method for this online although I am sure I am searching the wrong terms probably.

Help much appreciated. Only a few weeks into learning this! Thanks

You misunderstand $(02) \cdot 10000100$; it is not integer multiplication (resulting in a 9 bit integer); instead, it is multiplication in $GF(2^8)$ (which results in an element in $GF(2^8)$, which can be represented in 8 bits).

AES uses a polynomial representation of $GF(2^8)$, using the polynomial $x^8 + x^4 + x^3 + x + 1$; what this means is that multiplication of two elements can be performed by multiplying the two values (however, disabling all internal carries); and then reducing the product modulo $11b$ (again, without doing any carries).

When we multiply by 2, this can be simplified to "shift all the bits left by 1, and then if the original bit 7 was a one, xor in the value 0x1b, and take the lower 8 bits of the result".

Given that, multiplying by 3 (which is also used as in the Mixcolumns operation) is easy, as $3 \times x = (2 \times x) \oplus (1 \times x)$, and we know how to evaluate both $2 \times x$ and $1 \times x$