Encrypting a string as smaller pieces vs. encrypting it as a whole Is there any difference between these two ways to encrypt a string using FPE?

Say the string has the format is specified by this rule
First part is in the set
$S = \{\text{AA,AB,AC,BA,BB,BC,CA,CB,CC}\} = \{0,1,2,3,4,5,6,7,8,9\}$,
second part is in the set
$T = \{0,1,2,3,4\} = \{0,1,2,3,4\}$

Example string = $\text{BA2}$

Usage 1.
Break the string as parts defined above, determine the integer representing each part as defined by the bijective mapping, and encrypt those integers individually using encryption function $E$.

$\text{BA = 3}$

$2 = 2$

$E(3) \Rightarrow 6 = \text{CA}$

$E(2) \Rightarrow 4 = 4$

Concatenate the parts together to get output

Output string = $\text{CA4}$

Usage 2
Encrypt the entire string by ranking all possible values.

$S=\{\text{AA0, AA1, AA2, AA3, AA4, AB0, AB1 ,AB2 ,AB3, AB4, AC0, AC1, AC2, AC3, AC4,}$ $\text{BA0, BA1, BA2, BA3, BA4, BB0, BB1, BB2, BB3, BB4, BC0, BC1, BC2, BC3, BC4,}$
$\text{CA0, CA1, CA2, CA3, CA4, CB0, CB1, CB2, CB3, CB4, CC0, CC1, CC2, CC3, CC4}\} = \{0,1,2,3...43,44\} $

$E(17) \Rightarrow 8 $

Output string  = $\text{AB3}$

Is Usage 1 equally valid as Usage 2?  Are there any negative side effects to breaking the string into pieces first compared to encrypting the string as a whole?

(1) correct a mistake here:

  set S = {AA,AB,AC,BA,BB,BC,CA,CB,CC} = {0,1,2,3,4,5,6,7,8,9}

should be
set S = {AA,AB,AC,BA,BB,BC,CA,CB,CC} = {0,1,2,3,4,5,6,7,8}

(2) According to your example. I would say the "Usage 2" is better than the "Usage 1", since the "Usage 2" has more possible mappings than the "Usage 1" does.
Proof:
Usage 1:
1. E function works for both set S (size = 9) and set T (size = 5).
2. When E function's input is in the {0,1,2,3,4}, its output must also be in the {0,1,2,3,4}. Or, you cannot map "the set T = {0,1,2,3,4} = {0,1,2,3,4}" by the E function.
3. This leads to a problem: the first 5 elements in S ("AA,AB,AC,BA,BB") can only be mapped to a subset of S ("AA,AB,AC,BA,BB"). For example, you will never map "AA0" to "BCX", "CAX", "CBX" or "CCX", where X is in the {0,1,2,3,4}.

"Usage 2":
All possible mappings are here.

(3) According to your two comments:

  @D.W.the string is only 3 bytes composed of characters only from the sets above. The output scope should be the same as the input - the function E puts you back into the same set from which the value came from – erotavlas 8 hours ago

  In Usage 1, I could encrypt them as separate entities (pass them to an integer FPE with different max value for each) – erotavlas 8 hours ago

I would also say that the "Usage 2" is better than the "Usage 1".
Proof:
A1. the E function now maps S(9) to S(9), T(5) to T(5), S'(45) to S'(45), where S' is the S of your Usage 2 example;
A2. "Usage 1": I will feed your E function 9 inputs to get all possible mappings(S=>S, T=>T). That is, {AA0, AB1, AC2, BA3, BB4, BCx, CAx, CBx, CBx}, where x is a number in the T set.
A3. "Usage 2": I will feed your E function 45 inputs to get all possible mappings(S'=>S'). That is, the whole S' set as specified in A1.
A4. The difference is that by dividing the string into small pieces, the spaces of clear text and cipher text are changed.


Why has the sponge construction's generic collision finding attack a complexity of O(min(2^(-n/2) , 2^(-c/2)))? I'm trying to learn about sponge function for creating hash functions and generic attacks on it.

I'm looking for the collision finding attack scenario which leads to $O(\min(2^{-n/2} , 2^{-c/2}))$ time complexity, where $n$ is the sponge output length(hash output length) and $c$ is the capacity length of sponge state.

I know that $2^{-n/2}$ comes from a traditional birthday attack on the output, but what is the attack scenario for $2^{-c/2}$ complexity?

Denote the internal sponge state by
$$
S = R\mathbin\|C,
$$
where $C$ has size $c$ — capacity.

Every iteration a message block of length $|R|$ is xored into $R$ and then the permutation $P$ is applied. Therefore, if we obtain a collision in $C$ (which can be obtained in $2^{c/2}$ steps with the basic birthday attack), we could cancel any difference in $R$ by injecting an appropriate pair of messages.

So, if $(M_1,M_2)$ yields a zero difference in $C$ and difference $\Delta R$ in $R$,
the pair
$$
(M_1\mathbin\|X,M_2\mathbin\|(X\oplus \Delta R))
$$
is a collision pair for the full function $F$ for any $X$.


What size should the HMAC key be with SHA-256? I'm trying to generate a secret key to be used for HMAC SHA-256 signature processing. I've seen many sample of keys with variable length from 32 characters to 96 characters.

What is the ironclad rule for this key size?

The only rule for the key is that it should at least contain 256 bits of randomness. If the key is smaller you may not get the full security of HMAC-SHA-256. The full security of HMAC is basically identical to the output size. Unless you are trying to protect yourself against quantum computers you should be able to get away with a key that contains 128 bits of entropy though.
Here's the text from the HMAC standard captured in RFC 2104:

The authentication key K can be of any length up to B, the
block length of the hash function.  Applications that use keys longer
than B bytes will first hash the key using H and then use the
resultant L byte string as the actual key to HMAC. In any case the
minimal recommended length for K is L bytes (as the hash output
length).

So preferably the entropy of the 256 bit key should be condensed into 32 bytes. What you are talking about is probably the hexadecimal representation of those 32 bytes. If the key is too large it may affect performance and efficiency of the HMAC function. Many libraries only allow binary to be inserted using octets bytes anyway, so in that case it makes sense to hex decode the key before you use it.

HMAC uses a hash internally, which is defined for any bit string. This hash is used both for the key as for the value. So in principle you can feed it anything you want up to the maximum hash size (which you will never reach).
Definition from Wikipedia:
$ {\begin{aligned}\operatorname {HMAC} (K,m)&=\operatorname {H} {\Bigl (}{\bigl (}K'\oplus opad{\bigr )}\parallel \operatorname {H} {\bigl (}\left(K'\oplus ipad\right)\parallel m{\bigr )}{\Bigr )}\\K'&={\begin{cases}\operatorname {H} \left(K\right)&K{\text{ is larger than block size}}\\K&{\text{otherwise}}\end{cases}}\end{aligned}} $
Note the repetition of the key with regards to efficiency.


Is there a standard for hashing a list of strings? I'm working in Python, and my goal is to hash a list of strings with a cryptographic hash function such as sha256. It would need the property that a change in any string, or the order of the strings, will affect the outcome. For example, this would not be sufficient.

sha256(''.join(['string1', 'string2'])).digest()

because ['string1', 'string2'], ['string1str', 'ing2'], as well as ['string1string2'] will all result in the same hash.

One idea I've had for this is to hash repr(strings), but I'm concerned this may be inefficient, as unprintable characters are converted to the 4-byte form \xAB.

strings = ['string1', 'string2', '\x00', '\\x00']
tohash = repr(strings) # tohash == "['string1', 'string2', '\\x00', '\\\\x00']"
result = sha256(tohash).hexdigest() # 2da24fba01c065fe1f33cb937dec2c865de20ebdbd8f172d59d82cd920d3266d

This method works, but I haven't seen it used anywhere else, and it seems inefficient. Is there a standard way to hash multiple strings?

There are two ways of going about this:

create a hash tree (or, as it is only one deep, a hash list);
create a canonical representation of the strings;

For the first option you simply hash each string, and then hash all the resulting hashes. As the hashes should not have collisions, you can be certain that the resulting hash doesn't collide either.

In the other option you create a canonical hash. You've got three options:

use escape characters or bytes;
define the structure and size of the elements outside the strings;
a combined approach of the above.

The first approach I won't explain much. It consists of appointing an escape character and use that for structural information. So e.g. a single 00 byte is used to indicate the end of a string and all the existing 00 in the string are doubled. Disadvantage  of this approach is that your string may grow significantly.

As for the second approach: take a look at how ASN.1 would create structures using DER. You would use a "tag" to indicate a set, then the length of the set. Then you would put one or two strings in the set. Each string again has a tag and a length. This structure is completely canonical without requiring any escape characters (as DER is a binary encoding). This will only add a limited amount of overhead.

The combined approach is e.g. applied by Python: you can perfectly distinguish between ['string1', 'string2'], ['string1str', 'ing2'], as well as ['string1string2']. The language is already showing you how to encode lists of string!


What is the standard way to generate a unique non-reproducible ID? Say that a manufacturer wants to label her products in such a way that a third party could verify that the manufacturer is the one that labeled the product, meaning it's not a counterfeit.

The manufacturer could have a serial number to each product, and have it signed with some signature scheme. However, this introduces some redundancy, as a verifier would have to use both the manufacture's public key and the serial number.

  Is there a different, more efficiently method create such labels?

Two cases are of special interest:

The label should be publicly verifiable.
The label should only be verifiable by an entity that share some secret information with the manufacturer (so perhaps encryption schemes are relevant).

It is desired a Unique Non-Reproducible ID (UNRID) which genuineness is publicly verifiable.

I know no standard for that. But we can take as UNRID the signature of a public fixed message (e.g. empty), if the signature scheme is randomized and EUF-CMA secure. Verification simply checks the signature. If probability of collision among signatures is satisfactorily low, security follows from EUF-CMA.

The signature scheme could be RSASSA-PSS of PKCS#1v2.2, with the advantage of fast signature verification. But for modern security that requires 256 bytes (342 Base64 characters), which is a lot.

A more compact option is a slight variant of ECDSA, where a signature $(r,s)$ becomes the UNRID $(r,\min(s,n-s))$, which is presented as EUF-CMA secure there, without proof but plausibly: EUF-CMA security of the signature scheme matters in Bitcoin, and was repaired with apparent success, in a manner equivalent to what's proposed. That would make the UNRID 64-byte (86 Base64 characters).

Using a signature scheme with message recovery, we can embed a serial number or other small ancillary information in the UNRID, without making it bigger. For RSA, ISO/IEC 9796-2 Scheme 2 would do (it's essentially RSASSA-PSS with message recovery). There are ECC-based randomized signature schemes with message recovery as compact as ECDSA, see bibliography.


Why is pseudorandom OTP (P-OTP) IND-CPA insecure My lecture notes state that P-OTP is IND-COA but not IND-CPA insecure. I understand IND-COA secure, assuming PRG is secure, as that is the whole point of a OTP, but why is it IND-CPA insecure? Surely, if the PRG is assumed to be secure, then the resulting ciphertext would be random, so whatever plaintext you feed into the oracle will reveal no information.

I ask this because PRF+OTP is IND-CPA secure and cannot figure out the difference.

$Enc_k(m)=m\oplus PRG(k)$

$Dec_k(c)=c\oplus PRG(k)$

and the IND-CPA adversary game:

Pick two messages $m_0$ and $m_1$ arbitrarily.
Send them to the challenger who chooses $b\in\{0,1\}$ uniformly at random and returns you $c_1=Enc_k(m_1)$.
Output your guess for $b$ named $b'$. You "win" iff $b=b'$.

Edit: screenshots of the relevant slides

The game you stated is not the IND-CPA game, it is the IND-EAV game, where the adversary is given only the challenge ciphertext and is asked to guess the message being encrypted. In the IND-CPA game,the adversary is given access to an encryption oracle that can encrypt arbitrary messages of his choice.

The main reason why P-OTP can not be CPA-secure is because it is deterministic, that is, if you encrypt the same plaintext twice you'll get the same ciphertext. In general, any scheme with this property can not be CPA-secure, can you figure out why?

On the other hand, PRF+OTP is not deterministic: it refreshes each encryption with a random value $r$. This key difference makes the scheme CPA-secure, the proof can be found in any basic book like Katz' Modern Cryptography (Thm 3.31 in the 2nd edition), but the basic idea is that if the value $r$ is not repeated in the oracle's queries, then the attacker get no information about the message being encrypted (so you have perfect secrecy in this case, just like in the OTP), and the probability that this does not occurre is small enough.


Using multiple cryptographic keys for encryption? I am setting up an encryption methodology for items in a database. To decrease the likelihood of data being compromised due to the keys being compromised I would like to use an application level key (stored outside the database on a different server), a database level key (stored in a table away from data), and a data level key (stored inline with the data).

All of the keys are all AES256, encrypted at rest, and generated in a cryptographically sound way; they require a key management service to generate them and decrypt them. I have two methodologies in mind.

Gather and decrypt the keys at the same time, and immediately hash them together with some data context that describes the data to make a new single 256bit encryption key specific to that data. Then immediately delete them from memory; the hash remains in memory long enough to perform a single encryption/decryption, but is eventually deleted and never stored to disk. If it is compromised in memory, only the data it matches could be compromised.
Keep all the keys in memory long enough to successively encrypt/decrypt with each key. This runs the higher risk of the decrypted keys being individually compromised since they are in memory longer, but it seems like since entropy is added on each encryption step, it’s probably a stronger encryption in the end. Certainly the number of stored bytes increases (partially because of storing initialization vectors).

Is one method more secure/standard? Is there a more standard way of achieving what I’m trying to do? References would be great.

A more standard way is not to make any of this yourself.  Use a proper database like Oracle 11g.  It's all built in.  And you can even use it for free in some circumstances.

You think that it's simple just to AES some records in, but there's a great deal more for a production system.  Oracle have spent millions developing all this functionality and vastly more like key and privileged user management and backup/restore whilst addressing all the performance issues.  How would you handle encrypted joins for example?  You won't do better building something yourself.

Have a look at their transparent data encryption FAQ.


Encryption method that reduces the cipher text to a single byte Has anyone encountered an encryption method that compresses the cipher text to a single byte at the expense of inflating the key. If yes does it have a practical use?

Single byte, no? How about 16 bytes? Sure. Encrypt using AES-128 with a random key. The key is now the "ciphertext" and the output of the encryption (what we normally call the ciphertext) is now the "key". Problem is, how do you distribute the "key"?

The thing is, from a real world perspective, the idea of shrinking the ciphertext and growing the key is a non-starter. Keys must be shared over a secure channel, ciphertexts do not. If you had a secure channel that was efficient enough to share large amounts of data, why not just share the plaintext directly over that channel and skip the whole encryption business?


What should I use for consequent AES key derivation? I am writing a small chat program to explore some methods and concepts in cryptography and currently I am using a shared AES key tunneled with RSA which upon further reading revealed many flaws both in the mode choice and the concept itself.  So after some more videos, articles and posts I decided to implement 2 ECDH pairs which will be used to derive 2 different AES-GCM keys which in terms will be used for message encryption in both directions. On top of that I would like to implement a key derivation per request so that every message is encrypted with its own key derived from the previous. (Synchronicity problems will be handled by the protocol)

Since the initial AES key is not a human password but a high entropy string (which eliminates bruteforcing) is it enough to just hash it with SHA-256 and get the first 128 bits for the seed of the new AES key for efficiency and ease of use? This would prevent decryption of previous messages if the key is compromised which in combination of re-establishing the ECDH pair every so often will limit the threat of a compromised key to minimum in both time directions.

Edit:

Just to make it clear because i added too much context around the question: I am asking if a simple hash function as SHA-256 would play a sufficient role of a KDF in a double ratchet?

This is the proof of concept that I am going to use: https://netnix.org/2015/04/19/aes-encryption-with-hmac-integrity-in-java

Yes, generally you can use a hash as a "poor man's KDF". For instance, look at the Q/A about KDF1 and KDF2 which are little more than glorified hash functions. Of course, as e-sushi noted, the theoretical requirements of a KDF is a little bit higher than those required of a hash.

Some differences:

A KDF doesn't have just one input; besides the Input Keying Material it may also have inputs such as Info containing e.g. a label for the key, a salt and the length of output material to generate;
The inputs of the KDF should be canonically encoded or there may be restrictions on the input parameter so that different input combinations will never generate the same output;
The output of many KDF's is configurable and may extend the output size of the underlying hash function or block cipher (depending if the KDF supports expansion);
The output of the KDF is generally well defined, usually if you want to take 128 bits from a 256 bit hash you take the leftmost bits, but a KDF will have formalized what output should be taken (and yes, I've seen weird / stupid ones);
The output of the KDF should be full randomized, which is theoretically not a requirement for hash functions.

Now e.g. SHA-256 or SHA-512 will have output that is indistinguishable from random, so the last point is mostly theoretical in nature. All the other differences can be ignored or implemented in your own hash function. So yes, it is possible to define your own KDF.

However, I'd suggest you use KDF1 so you'd at least be compliant to an existing KDF where all these design choices are already made. KDF1 is very basic and doens't seem to offer canonical encoding, so you  may want to make sure that OtherInfo has a static size. In the end, you'd still be left with a single call to a hash. A HMAC based KDF such as HKDF would be considered more secure, of course, as there are few primitives that match a PRF such as HMAC with regards to resilience.


What’s the difference between a Fast wide pipe and a Narrow pipe construction? I'm learning more about the Merkle–Damgård construction, including its "alternatives".

I learned about the fast wide pipe construction and the narrow pipe construction, explained here. However, I can't find any images showing the process of the narrow pipe scheme in detail (presuming it's not the same as the FWP construction).

What is the difference between these two constructions? And is there one construction proven to deliver better results than the other?

Of an iterated hash function $$H(m_0 \mathbin\Vert m_1 \mathbin\Vert \cdots \mathbin\Vert m_{n-1}) = g(f(\cdots f(f(\mathit{IV}, m_0), m_1)\cdots, m_{n-1})),$$ for functions $f\colon \{0,1\}^s \times \{0,1\}^k \to \{0,1\}^s$ and $g\colon \{0,1\}^s \to \{0,1\}^h$, narrow pipe, as introduced by Stefan Lucks, just means that the intermediate state is no larger, or not much larger, than the final output: $s = h$.  Wide pipe means $s \gg h$.

In SHA-256, the intermediate state has $s = 256$ bits just like the output; thus SHA-256 is a narrow-pipe iterated hash function.  In SHA-512/256, the intermediate state has $s = 512$ bits and the output has $h = 256$ bits; thus SHA-512/256 is a wide-pipe iterated hash function.  In SHA3-256, the intermediate state has $s = 1600$ bits while the output has $h = 256$ bits; thus SHA3-256 is also wide-pipe.

In principle, SHAKE256-1600 would be considered narrow-pipe too, but such distinctions are not really used much these days; they don't illuminate relevant security properties very well.  The attacks that Lucks hoped to thwart with wide-pipe constructions are usually addressed in other ways instead, and we aim for security targets rather than pipeyness.


Attack RSA with PKCSv1.5 padding I was reading an article about breaking RSA with PKCSv1.5 padding (http://mslc.ctf.su/wp/google-ctf-spotted-wobbegong-crypto-100/).
It says that while retrieving the message we multiply by the inverse fraction and take modulus of a power of 2 rather than modulo N.

But how do we determine which power of 2 to be used ? Is it a trial and error or can we determine it from the length of the message ?

First of all, this attack assumes that we have a decryption Oracle; that is, an Oracle that we can submit any ciphertext to (except for, apparently, the challenge ciphertext), and it will tell us that the padding is bad, or it will give us the decrypted message (minus the padding).

In the attack, we're given the challenge ciphertext $(Pad + M)^e$, and we select a simple rational value $r/s$ near 1, we submit to the Oracle the ciphertext $(r s^{-1})^e (Pad + M)^e$, and if $Pad+M$ happens to be a multiple of $s$ (and the padding looks valid), we get the lower $n$ bytes of $r/s (Pad + M)$

Your question really is: given the lower $n$ bytes of $r/s (Pad + M)$ (which we will call $R$), how can we recover the lower $n$ bytes of $Pad + M$?  That's actually fairly simple; essentially we need to compute $s/r R \bmod 2^{8n}$.  Now, the divide by $r$ is slightly tricky (and computing $r^{-1} \bmod 2^{8n})$ is the wrong approach); however we know that the full value $r/s (Pad + M)$ is a multiple of $r$, and so one way to do is is to find the value $0 \le k < r$ such that $R + ks^{8n}$ is a multiple of $r$, and then divide that by $r$; that'll give the same lower bytes as the original $r/s(Pad + M)$.

Now, going back to looking at this attack in general, we find this attack is less powerful than the Blechenbacker attack, which will allow us to decrypt any message, and makes weaker assumptions on the Oracle (namely it doesn't have to give us the decrypted text on success; only notify us that success did happen).  This attack does have the advantage that, if successful, it requires fewer queries (but it won't always be successful, perhaps $Pad+M$ doesn't happen to have any small divisors), and it is easier to understand.


learning with errors is hard even when given some information about the secret vector In this case we are given the distribution D from which secret s is sampled. If I can get some hints to proceed with the questions, it would be of help.

Thanks,

There is on one hand a recent preprint Hardness of LWE on General Entropic Distributions by Zvika Brakerski and Nico Döttling, and on the other hand it's well known that you can assume that the secret is sampled from the error distribution (see for example the last paragraph on page 7 of Classical Hardness of Learning with Errors by Zvika Brakerski, Adeline Langlois, Chris Peikert, Oded Regev and Damien Stehle).


Which data encryption mechanism to use for data transfer? I have high performance nodes communicating with each other sending logs and data over network.
The communication is heavy and over public network.

I would like to know how to know which is the best encryption algorithm to be used to encrypt and decrypt the data so that it has minimal affect over performance simultaneous making the encrypted data unbreakable and secure?

Currently according to my survey i have considered 2 Algorithms to be best i.e.

TwoFish - Have heard that this is the fastest
AES 128 - Have heard that this is the most efficient
AES 256 - HAve heard that this is the most secure
Any other algorithm would also do fine

  Security and performance overload of the system is to be kept in mind

You should use AES. If you have the AES-NI instruction (which most modern chips have), then this performs very fast. For most applications today, AES-128 is certainly sufficient. However, I want to stress that it's not just the algorithm, it's also the mode of operation. You should use GCM. If you use OpenSSL then with AES-128-GCM you'll get speeds of about 0.7 cycles per byte for encryption (with AES-NI).


TimeStamp in Cache-time attacks on AES I have recently read about AES cache timing attacks. More specifically, I read Daniel Bernstein paper Cache-timing attacks on AES. I have a question about the code in Appendix A:

unsigned int timestamp(void)
{
unsigned int bottom;
unsigned int top;
asm volatile(".byte15;.byte 49" : "=a"(bottom),"=d"(top));
return bottom;
}

What does timestamp methode do?

The opcode 15 49 (0F 31 - Intel opcodes are more typically listed in hexidecimal) is the RDTSC instruction; this loads the number of cycles since the last rest into EDX:EAX.

By running this function, running some code, and then running this function again, and subtracting the results, you get precisely how long the code takes (in number of CPU cycles).


Is inverse of a combination function negligible? Can anyone help me in determining whether $1/{n\choose a}$ negligible function for sufficiently large value of $n$, say for example $n=p^2$ and $a=p$, for an integer $p$?

Hint:

$$1/{n\choose a}=\frac{a!(n-a)!}{n!}=\frac{p!(p^2-p)!}{(p^2)!}=\frac{p!(p^2)!}{(p^2)!\prod^{p-1}_{i=1}(p^2-i)}=\frac{p!}{\prod^{p-1}_{i=0}(p^2-i)}$$

Now write the nominator as a product series as well. Then adjust the indices and use multiplicative factors to shift indices. Then write it as one big product. Find an upper bound for the fraction inside the product. Replace the fraction, making the multiplied term independent of the variable. Conclude.


What happens if five messages are generated in IND-CPA security? I am wondering why in IND-CPA security game, the adversary generates two random messages. What happens if for example 5 messages are generated? What would be the advantage for the adversary?

First things first: The adversary doesn't have to randomly pick messages, they can pick any messages they like, including heavily related ones.

Now as for why the adversary has to identify the message under $2$ instead of $n$ options.

Two allows for 1-bit plaintexts. Suppose you had a scheme that is secure for all messages of 2 bits and longer, picking $n>2$ and enforcing same-length and distinctness would mean you have no statement about 1-bit messages.
It's the most natural choice. 2 does the job, why pick a higher number?
Two is perfectly sufficient to express the meaning of the messages. This would be to decide the which message was "picked" with all messages but one (so exactly one for $n=2$) being "not picked".
Two makes the adversary the strongest and thus also our security model. By default the adversary has a 50% chance of getting the answer right, with other numbers this would be $1/n$.


Best way to get 32 bytes from PBKDF2 Use the PBKDF2 output as an HMAC key, hashing two different inputs - once for 20 bytes and once for 12 :

using (var PBKDF2 = new Rfc2898DeriveBytes(passwordBytes, salt, 100000))
{
    HMACSHA1 hmac = new HMACSHA1(PBKDF2.GetBytes(20));
    hmac.Initialize();
    byte[] aesKey = hmac.ComputeHash(new byte[] { 1, 0, 1 })
        .Concat(hmac.ComputeHash(new byte[] { 1, 1, 1 })).Take(12).ToArray();
}

Or perform PBKDF2 twice, splitting the iterations, and using 2 different salts :

byte[] aes2;
using (var PBKDF2 = new Rfc2898DeriveBytes(passwordBytes, salt1, 50000))
    aes2 = PBKDF2.GetBytes(20);
using (var PBKDF2 = new Rfc2898DeriveBytes(passwordBytes, salt2, 50000))
    aes2 = aes2.Concat(PBKDF2.GetBytes(12)).ToArray();

References: Rfc2898DeriveBytes ,  HMACSHA1  .

It would help to understand the context a little.  I'm assuming you're trying to arrive at a password-based key and you're trying to maximize the brute-force time required to guess the key.  But maybe this data will be used as a tag, or you're interested in maximizing the time to create a password-key dictionary or something.

I would consider the search space an attacker would have to go through in making your decision.  The first one has a search space of $|passwordBytes|\times|salt|$.  The second has a search space of $|passwordBytes|\times 2\times|salt|$, so requires $O(2^{|salt|})$ more computation.  Doubling the iteration count just doubles the computation (i.e. adds one bit of complexity).  The time to compute a dictionary would be higher for your second option.

However, it would actually be easier to say something about just the first 20 or just the last 12 bytes in the second scheme (since it uses a lower iteration count), which could allow brute-forcing the other half even more trivially.  To prevent this, you'd do better to follow CodesInChaos's suggestion and cascade operations, but make sure the final output is a single output from a secure primitive.  For instance, you might use $tmp = PBKDF2(passwordBytes, salt1, 50000)$ to get $|passwordBytes|$ of data, then use $SHA256(PBKDF2(tmp, salt2, 50000))$ (or even just $SHA256(tmp || salt2)$) to get 32 bytes.  This makes the search space as big as $|passwordBytes|\times 2\times|salt|$ but doesn't leak information from just one or the other halves of the output.

In any case, depending on how you're using the data, I suspect some other primitive (like SHA-256) might be useful for you.


Is Guillou-Quisquater existentially unforgeable against adaptive message attack under a random oracle model? First of all, the Guillou-Quisquater digital signature scheme is:

Note everything is $\bmod n$. Message is denoted by $m$.
Private key: $s$
Public key: Hash function $H$, $e$, $L=s^e\bmod n$
To sign: Alice chooses random $r$. Computes $c=H(m||x)$ with $x=r^e\bmod n$; $y=r\cdot s^c\bmod n$;  send Bob $x$ and $y$.
To verify: Bob computes $c=H(m||x)$ and accept if $y^e \equiv x\cdot L^c\pmod n$.

I'm wondering what the strongest known security of this is, in particular the question in the title. If not, what's the best research that's been done on this scheme?
I've scoured the internet for such a proof, but I can't find anything. I was also told by my supervisor that if I could find such a proof for El Gamal it might be easily adaptable, so that would also be much appreciated. Thanks!

Guillo-Quisquater scheme uses the Fiat-Shamir trick to convert a proof of knowledge into a signature. There is a paper out there about the security of such schemes in the random oracle model here which seems to give what you want.


GPG Details of Anatomy What is the "created" field below? How can you translate that into an actual date?

Source: https://davesteele.github.io/gpg/2014/09/20/anatomy-of-a-gpg-key/

It is a date that the creator of the signature chose to sign, usually representing the time at which the signature was created, in POSIX time, namely the approximate number of SI seconds that have elapsed on Earth's surface since January 1, 1972 at 00:00 in UTC, plus 63072000, minus the number of those that were labeled as leap seconds in UTC.

The Wikipedia article currently (2018-03-02) names January 1, 1970 at 00:00 in UTC as the reference point, but that must be interpreted as proleptic UTC because modern UTC, or just ‘UTC’ today, did not begin until 1972.  The OpenPGP standard, RFC 4880, §3.5 ‘Time fields’ makes the same mistake, and does not mention leap seconds, but basically all implementations agree to subtract the number of seconds that were labeled as leap seconds.

You can print a UTC representation of the same date and time given its POSIX time representation using the GNU coreutils date(1) utility as follows:

$ date -u --date=@1281838967
Sun Aug 15 02:22:47 UTC 2010


Is it a good idea to use bitwise XOR on a set of MD5 sums? I have designed an SQL aggregate function in Oracle that bitwise XORs all MD5 sums of the values stored in a column.

For example, if my table is:

+-----+----------+---------+
| Key | Sequence |  Value  |
+-----+----------+---------+
|   1 |        1 | 'Hello' |
|   1 |        2 | 'World' |
|   2 |        1 | '1234'  |
|   3 |        0 | (empty) |
|   4 |        1 | 'Hello' |
|   4 |        3 | 'World' |
+-----+----------+---------+

I can run the following query in Oracle:

with t AS (select 1 key, 1 sequence, 'Hello' value FROM dual
           union all select 1, 2, 'World' from dual
           union all select 2, 1, '1234' from dual
           union all select 3, 0, '' from dual /* ... */
          )
   select key, md5_agg(value) from t group by key

and get (unfortunately aggregate functions in Oracle ignore NULL values and '' is considered as NULL)

+---+----------------------------------+
|key| md5_agg(value)                   |
+---+----------------------------------+
| 1 | 7EBD0B1DA67F965F802D31DF25C4B321 |
| 2 | 81DC9BDB52D04DC20036DBD8313ED055 |
| 3 | 00000000000000000000000000000000 |
| 4 | 7EBD0B1DA67F965F802D31DF25C4B321 |
+---+----------------------------------+

I would like to use this approach to compare if the contents of some columns are equal when I compare subsets of the same table (think of finding duplicates in a complex structures that spans over multiple rows in the same table). Here with this results I know that I have the same subsets for keys 1 and 4.

What are the limits of such an approach? Here are the ones I could list:

This is interesting only if my column contains distinct values. If my columns contains twice the same string, the xor operation will be a no-op.
Due to Oracle limitations, if my column contains empty values, they do not count.

With those limitations in mind, is it still possible to infer, from two equal md5_agg results computed from distinct and non-empty values, that the original values make up the same sets?

In order to reformulate, are there odds that the MD5 sums of distinct strings XOR to 0?

The short answer is no. The scheme gives poor protection against collisions, that is inputs detected as having the same content (within order) when they have not.

As noted in the question, this can occur when entries in an input are duplicated; e.g. ("O","X","O") and ("X") collide.

This can also occur for maliciously crafted entries. For a start, MD5 is broken, in the sense that it is now easy to create different strings/entries that hash to the same MD5 result; replacing one by the other will go undetected. And even if one uses a collision-resistant hash such as SHA-256, it is very easy to construct a set of messages such that the XOR of their hashes equals a given value, by mere Gaussian elimination. See the answer to this question.

On the other hand, short of the issue of duplicated entries in an input, there is little chance that the scheme fails by accident.

A robust scheme would be:

hash each string using SHA-256
sort the hashes by ascending value
hash the concatenation of the sorted hashes using SHA-256


Encryption scheme with equivalent keys? I've long been looking for a symmetric encryption scheme (or algorithm) with equivalent keys. Let me define what I want:

Symmetric encryption algorithm with encryption function $E_k$ and inverse decryption function $D_k$.
Existence of equivalent keys. Keys $k_i \neq k_j$ will be called equivalent if $E_{k_i}(\cdot) \equiv E_{k_j}(\cdot)$ as functions and the same for the decryption operation $D_{k_i}(\cdot) \equiv D_{k_j}(\cdot)$.
Without knowledge of some master secret, it would be computationally infeasible to derive an equivalent key $k' \neq k$ from a key $k$.
With knowledge of some master secret, it would be straightforward to derive at least "many" equivalent keys (let's just say that the equivalent keys should not be scarce compared to the size of the entire keyspace, e.g. 4 equivalent keys in the entire keyspace are not enough).
No trivial intermediate value: of course it's trivial to come up with a scheme satisfying all of the above in which all equivalent keys map to one intermediate value (for example take 128 bit keys with an additional 16 bits at the end, then discard these as a first step before applying standard AES-128). This is perhaps the most important feature and the hardest to define. Let's say then that it requires knowledge of some master secret or some special trapdoor to reduce equivalent keys to an intermediate value.

Does anyone know of existing schemes/algorithms satisfying at least most of the requirements above, or any interesting papers on the subject, or just have some bright idea to share with us?

I don't know of any scheme that provides this, and it sounds tricky to build one.

Here's the closest I can come up with.  Let $n=pq$ be a 2048-bit RSA modulus, $d$ be a random 2048-bit number that is relatively prime to $(p-1)(q-1)$, and $e = d^{-1} \bmod (p-1)(q-1)$.  The master secret is $d$; $n$ will be baked into the description of the encryption algorithm $E$.  Let $\text{truncate}(z)$ be the result of truncating $z$ to 128 bits: say, deleting the low 1920 bits and keeping the high 128 bits.  Then, define $$E_k(x) = AES(\text{truncate}(k^e \bmod n), x),$$
and similarly for $D_k(x)$.  In other words, the key $k$ is a 2048-bit string.  To encrypt under $k$, we raise the key $k$ to the power $e$ modulo $n$ (a textbook-RSA encryption of $k$), keep the first 128 bits, and use that as an AES key to encrypt the message $x$.

Given a key $k$ and knowledge of the master secret, it is easy to derive many other keys that will be equivalent (just tweak the low bits of $k^e \bmod n$ randomly, then raise that to the $d$th power modulo $n$, and you've got an equivalent key).

This satisfies your requirements 1-4, but not requirement 5.  Why do you need your requirement 5?  I wonder if we might be able to weaken the requirement somehow and still get something that is sufficient for your application.


Design flaws when designing a MAC-function Suppose we want to build a very basic hash function like this:
$$c_i = h(c_{i-1},x_i) = c_{i-1}\oplus x_i \quad\quad mit \;\; i\geq1, c_0 = \operatorname{IV}$$
Now suppose we'd use this hash-function to construct a custom-MAC-function in this fashion:
$$\operatorname{MAC}_k(c) \equiv c_n +k_1 + k_2 + \cdots + k_{16} \bmod 256$$
The function uses two operations, namely $\left(\left[\oplus, 2^{8}\right] \text { and }\left[+, 2^{8}\right]\right)$ and we use a 128-bit key, where $k_1 , k_2 $ etc. represent the corresponding bytes of said key
Needless to say, this MAC-function has some horrible design flaws and I've spent some thoughts on what these are specifically
My question is which design flaws, apart from the following, could be pointed out. I am particularly interested in which design flaws this function has, which also apply to other cryptographic functions, such as block-ciphers and hash-functions In other words: Which properties do we generally aim for when designing cryptographic functions, and which of these does our custom MAC-function violate?
These are my points:

$+$ Addition does not actually increase the key, because of mod 256
very small modulo
low collision resistance, for example by flipping two bits in any $x_i$ we get the same MAC.

Question: Collision resistance is usually a property of hash-functions, would that also be a proper term to describe block-ciphers? E. g. Is this a proper statement: "AES was designed to have low collision resistance"

No diffusion effect: Making small changes in the plaintext or key result in roughly the same output

Have I missed something or misunderstand something?

Collision resistance is usually a property of hash-functions, would that also be a proper term to describe block-ciphers?

Well, kind of.
The message space of a hash function is huge. It contains about 2 ^ 2 ^ 129 separate messages for SHA-512, for instance. So it will have collisions as the output size is limited to 512 bits.
On the other hand a keyed block cipher is a permutation, a mapping from all input elements to a specific output element each. As all the input is mapped to a unique value in the output, there cannot be any collisions on the block cipher itself.
You haven't specified any method of using the block cipher for messages with a different size than that of the block size. If the block cipher is used in a specific way then you may well have a possible collision and therefore collision resistance when those are hard to find. Many hash functions are build on top of block ciphers after all, but it depends on the block cipher specifics and the way that it is used if that's secure.


Is cryptanalysis of CTB-Locker really impossible? It seems that CTB-Locker make a lot of victims nowadays, and yet, the full encryption scheme of it is now publicly known [1,2].

Would any of you could find a weakness to exploit in this encryption scheme that would be able to take it down once for all ? The point would be to recover the Master key or a way to circumvent the encryption.

See also:

« Where to find a full analysis of the encryption scheme of CTB-Locker? » on Reverse-engineering Stack-Exchange.
« Decrypt files with original file CTB-Locker », another question about CTB-Locker on Cryptography Stack-Exchange.

No. One of the most important principles of cryptography is that knowing the encryption scheme cannot help someone attempting to decrypt the material without the key. The encryption used seems to be a reasonably well-written implementation of several standard algorithms, for which no practical attacks are known. Finding a way to crack these would be a major undertaking, one which many skilled cryptographers have already failed at.


Bandwidth and block size for Paillier cryptosystem Can someone clarify what is meant by the terms cryptosystem bandwidth and block size for public key cryptosystems;
The context is the Paillier cryptosystem and its Damgård-Jurik generalisation. My intuition is that they refer to the modulus. Since the modulus is $n^2$ and $n^s$ respectively does it apply that they have more bandwidth/block size than ElGamal which computes $mod \;\; q$;
Is this intuition correct;

Let $c$ denote a ciphertext and let $m$ denote a plaintext.
To my best knowledge, researchers in cryptography employ "bandwidth" as different meanings, say, ciphertext expansion ($|c|/|m|$) or a number of bits of plaintexts contained in a ciphertext ($|m|$). @owlstead refers "overhead," which is $|c| - |m|$.
For example,

Joye and Libert (EUROCRYPT 2013, ePrint 2013/435) wrote that "the scheme is computationally efficient but somewhat wasteful in bandwidth as $k \cdot \log_2{N}$ bits are needed to encrypt a $k$-bit message." Here, the scheme is the Goldwasser-Micali scheme and it encrypts a bit into a ciphertext of length $\log_2{N}$ and "bandwidth" seems to be $|c|/|m|$.
Chevallier-Mames, Naccache, and Stern (SCN 2008, ePrint 2008/119) defined "bandwidth" as the number of bits contained in a ciphertext, that is, $|m|$.

I think you mean the latter, i.e., $|m|$ and "block size" seems to be $|c|$.

Let us calculate $|m|/|c|$.

Paillier: The plaintext space is $\mathbb{Z}_n$ and the ciphertext space is $\mathbb{Z}_{n^2}$. Hence, the ratio of bandwidth/blocksize is $1/2$.
DJ with $s\geq 1$: The plaintext space is $\mathbb{Z}_{n^{s}}$ and the ciphertext space is $\mathbb{Z}_{n^{s+1}}$. Hence, the ratio is $s/(s+1)$.
ElGamal: The plaintext space is $\mathbb{G}$ and the ciphertext space is $\mathbb{G}^2$. Hence the ratio is $1/2$.


DES f function injective for no fixed subkey? Let $f$ be the function used in a round of DES, as defined in FIPS 46-3:
$$\begin{align}
f:\{0,1\}^{32}\times\{0,1\}^{48}&\to\ \{0,1\}^{32}\\
(R,K)\ &\mapsto f(R,K)\underset{\mathsf{def}}=P(S(E(R)\oplus K))\end{align}$$
where $E$ is the expansion, $S$ is the combination of S-boxes, and $P$ is the permutation.

Prove or disprove:

$$\forall K\in\{0,1\}^{48},\ \exists R,R'\in{\{0,1\}^{32}}\text{ with }f(R,K)=f(R',K)\text{ and }R\ne R'$$

or equivalently: the DES $f$ function is injective for no fixed subkey.

The answer is independent of $P$, because a permutation is injective, and injective functions compose. It depends on $S$ and $E$. If it is trivial for those of DES, I missed it.

Inspired by the question DES F function never injective?, where the OP intends never to mean if we change the S-boxes, a possibility that we disregard.

First thing to observe is that a DES-like confusion function can be a permutation, depending on the contents of the S-boxes. DES S-boxes are formally defined as $6\rightarrow 4$ functions, with the leftmost and rightmost bits selecting a row, which itself defines a $4\rightarrow 4$ function applied on the four central bits of the input. This last function is, in DES, a permutation (over the space of 4-bit strings). If we change S-boxes such that all these $4\rightarrow 4$ permutations are the identity function, then, for subkey $0$, the whole confusion function is the identity, which is bijective. Therefore, we must take into account the exact definition of the S-boxes in DES, since the answer will depend on that.

Some notations:

We number bits from left to right, starting at 1 on the left (this is the notation used in the DES specification).
Subkey is $K$ and has length 48 bits.
We consider the function $f(K,R)$ for a 48-bit subkey $K$ and 32-bit input $R$. This is the DES confusion function, with the expansion step, but without the permutation $P$.

We can observe that changing bits 3 of the subkey does not change the injectivity status of the function: if there are two inputs $R$ and $R'$ such that $R \neq R'$ and $f(K, R) = f(K, R')$, then $f(K \oplus M_1, R \oplus M_2) = f(K \oplus M_1, R' \oplus M_2)$ for masks $M_1 = 2^{45}$ (i.e. bit 3 is set, all other bits are cleared) and $M_2 = 2^{30}$ (i.e. bit 2 is set, all other bits cleared). This applies to all bits $6j+3$ and $6j+4$, for $0 \leq j \leq 7$.

Similarly, if we flip both bit 5 and 7 of $K$, the injectivity status of the function is not changed: the assertion above stands for $M_1 = 2^{43}+2^{41}$ and $M_2 = 2^{28}$. This applies to all pairs of bits $6j+b \bmod 48$ and $6j+b+2 \bmod 48$ for $0 \leq j \leq 7$ and $b \in \{5,6\}$.

Using these two facts, we can say that $f$ is be injective for a subkey $K$ if and only if it is injective for subkey $K'$ such that:

$k'_i = k_i$ if $i \bmod 6 = 1$ or $2$;
$k'_i = 0$ otherwise.

Thus, if we want to check things exhaustively, we only have $2^{16}$ possible subkeys $K'$ to investigate.

At that point, I made a small program which tries all subkeys $K'$, using Floyd's cycle detection algorithm to find a collision. The program is written in C and can be found there. On my laptop, this program takes on 66 seconds to go through all possible $K'$, and finds a collision for each one.

Therefore, assuming that this program is correct (you can check the collisions, there are "only" 65536 of them), and modulo the epistemological reservations that some mathematicians have about computer-assisted proofs, one can say that it is proven that the DES confusion function is never a permutation, for any possible subkey $K$.


Does the prime modulus have to be bigger that the generator? In the DH algorithm $ a^x \bmod b $ where $ a $ is the generator and $b $ is the prime modulus does $b $ have to be bigger than $ a $ or could $ a $ be larger for example $ 19^x \bmod 17 $ . Because I don't see a problem with the generator being larger because the answer can still only be $ b \ge \text{answer} > 0 $ . Obviously the prime modulus would still have to be large enough to provide good security but I was just curious if the generator could be larger.

I suppose there is really no requirement to have $a <b$. But then again, if you are using an $a>b$ why not reduce it modulo $b$ and save space?


Simulating a joint distribution of an *almost* deterministic function The following is in the context of secure MPC.
Suppose that there is a functionality $f(x,y)$ which outputs 'answer' with probability $1-\textrm{negl}(n)$ for some security parameter $n$, and 'other answer' with negligible probability. Consider a Simulator $\mathcal{S}_1$. Now wlog, if I show that $\textrm{view}_1(\Pi)$ is computationally indistinguishable from $\mathcal{S}_1(x, f_1(x,y))$, can I conclude that the joint distribution $[\mathcal{S}_1(x, f_1(x,y)), f(x,y)]$ is computationally indistinguishable from $[\textrm{view}_1(\Pi), \textrm{output}(\Pi)]$?
The reasoning would be that the joint distribution is only affected by a negligible factor of the uncertainty of the output.

Lets first state the definitions. Consider a two party computation, where $i\in(1,2)$
Definition 1 Let $f$ be a functionality, and $f_i$ be it's view from Party $P_i$. Let $\mathcal{S}_i$ be a simulator executing a probabilistic polynomial time algorithm for Party $P_i$. We say that $\pi$ securely realizes $f$ if there exist some $\mathcal{S}$ exists that satisfies the following property:
$$[\mathcal{S}_i(x, f_i(x,y)), f(x,y)]\overset{c}\equiv [\text{view}_i(x,y), \text{output}(\pi)]$$
Definition 2 Let $f$ be a functionality, and $f_i$ be it's view from Party $P_i$. Let $\mathcal{S}_i$ be a simulator executing a deterministic algorithm for Party $P_i$. We say that $\pi$ securely realizes $f$ if there exist some $\mathcal{S}$ exists that satisfies the following property:
$$\mathcal{S}_i(x, f_i(x,y))\overset{c}\equiv \text{view}_i(x,y)$$
Definition 3 Probability distributions A(x,n) and B(x, n) are said to be Computational indistinguishably, denoted by $A\overset{c}\equiv B$ if $\exists$ a distinguisher D and negligible function $negl(.)$ s.t
$$\text{Pr}(D(A(x,n)) - Pr(D(B(x,n))) \leq negl(n)$$

Now notice the difference in the above definitions. The first definition talks about a probabilistic algorithm, while the second talks about a deterministic one. We're not talking about the $negl(n)$ difference in the output of the distinguisher, since that is already taken care of by the definition of Computational Indistinguishablity.
A functionality that has randomness is modeled by a probabilistic algorithm. In such a case, the functionality would present different output to both the parties.
So, the security definition for such a protocol would have to ensure that the joint distribution of simulator output and the functionality output are indistinguishable from the real world. If it was not indistinguishable, the simulator would be able to tell you the output for other party. Which would eventually mean that your protocol is insecure.
If the functionality presents the same outputs for the parties, the wouldn't be truly random. We call this functionality a deterministic functionality and we use Definition 2 to prove the security of the protocol that realizes it. Functionality $f(x,y)$  produces the same output for both the parties, so we don't need to care for whether it's joint distribution with the output of the simulator is indistinguishable from the real world.
Coming back to your question,you can certainly apply Definition 1 in your case (where the functionality is deterministic) since definition 1 is stronger notion than definition 2. However, you should go for Definition 2 since the presence of $negl(n)$ does not make your functionality probabalistic.
You can also refer to $\S$4.2 of https://eprint.iacr.org/2016/046.pdf by Lindell


On the initializaton of the "xorwow" PRNG In the original paper, Marsaglia defines the xorwow() function and gives some example values for the initial state of $x$, $y$, $z$, $v$, $w$ and $d$. But it is not clear to me, how these values have been chosen, or how they can be "randomized" from a seed. The paper doesn't go into detail here. Wikipedia has a slightly different xorwow() code  (should be equivalent, I think), but again doesn't say how to initialize the state - except that "the state array must be initialized to not be all zero in the first four words".
So, it is "safe" to initialize all 6 state variables with completely random data, e.g. taken from  the operating system's entropy source? Or do any of these variables need to be initialized in a specific form to get "good" random numbers? For example, did Marsaglia choose some "magic" values that perform best? Also, what about the counter $d$? Should $d$ even be randomized?

OK, first things first. DO NOT UNDER ANY CIRCUMSTANCES USE XORWOW TO GENERATE ANY CRYPTOGRAPHIC SECRETS OR VALUES THAT SHOULD BE UNPREDICTABLE TO AN ADVERSARY.
Sorry to shout, but it is very important to point out that xorwow is not a cryptographically secure random number generator; it's an LFSR with a fake moustache.
I'm not sure why the wikipedia comment says that the first four need to be non-zero. In particular the states (0, X, 0, 0, 0), (0, 0, X, 0, 0), and (0, 0, 0, X, 0) would all transition to (0, 0, 0, 0, X) and would therefore presumably also be weak. It's important as with all LFSRs not to load up the register with all zeroes (so the first five variables should not all be zero). Also avoid setting the increment to an even value (the number 362437 in the wiki code). If you follow these two conditions the state will cycle through all $2^{192}-2^{32}$ values and different seeds just make you start at different points on the cycle and are pretty much equivalent. There's a small issue if the registers begin in a very spare state, they only slowly evolve out of being sparse, but over a large number of calls this will smooth out.
This would make the generator suitable for e.g. generating values for Monte-Carlo integration of a real valued function. BUT IT'S STILL NOT SUITABLE FOR ANY CRYPTOGRAPHIC PURPOSE. (sorry again for shouting).


Can files be 'over-encrypted'? First a hypothetical situation:

Key1: Is a password (let's say "TooMuchEncryption") and then hashed with SHA256

Let's say you have 3 files, first you encrypt the files with AES256 with Key1 and then package them into a zip file. Then when you send it to a friend, you encrypt that whole zip file with the public key of your friend with PGP and you send it to him via a TCP channel.

Forget the time, because of course: this road would take a 'very' long time on a avarage computer (4 cores, 8 threads) (right?).

But it is secure. The chance anyone will decrypt those 3 files, is quite small (assuming they don't have those keys and they intercepted it by listening to the TCP channel).

But are these files 'over-encrypted'? Does it even make sense to apply so much encryption (first AES then PGP)? Would just zipping that file and protect that with Key1be enough?

With the current computers this would not take so much time. There is a high chance that reading / writing the files or sending the files over the network will take more time. If you've got trash like the McAfee virusscanner installed on either PC then that will take much more time as it will try and scan the files in the zip file at lower than 1 MiB/s.

Passwords are generally not very strong, while encryption using a hybrid cryptosystem such as PGP using an RSA public key is very strong. The password based encryption (PBE) is made worse as you're using SHA-256 instead of a password based key derivation function (or PBKDF). So an additional encryption would indeed not be a bad idea. In general you could do without the password encryption, but not without the PGP encryption the way you write it down. Note that the PGP encryption is also protecting the file names; it could be that the file names are sensitive too.

Even when using PGP you should check if you're not vulnerable against Bleichenbacher attacks, padding oracle attacks. This would mainly a problem if you automate the decryption when the files are received. Protection should also be in placed to disallow changes of the plaintext, for instance by signing the .zip file.

So I don't think you're over encrypting, rather the opposite. That said, performing encryption right once makes more sense than performing it badly twice.


Leighton-Micali Hash-Based Signature key sizes I am working with the RFC for Leighton-Micali Hash-Based Signatures: RFC-8554.
The question is if I understood it correctly and my calculations of the key sizes are correct.
Basically, LMS uses several Winternitz-One-Time-Signature keys.

Winternitz-OTS
In chapter 4.1 of the RFC the parameter sets of the OTS keys are mentioned:
  |------------------------------------------------------------|
  | Parameter Set Name  | H      | n  | w | p   | ls | sig_len |
  |------------------------------------------------------------|
  | LMOTS_SHA256_N32_W1 | SHA256 | 32 | 1 | 265 | 7  | 8516    |
  |                     |        |    |   |     |    |         |
  | LMOTS_SHA256_N32_W2 | SHA256 | 32 | 2 | 133 | 6  | 4292    |
  |                     |        |    |   |     |    |         |
  | LMOTS_SHA256_N32_W4 | SHA256 | 32 | 4 | 67  | 4  | 2180    |
  |                     |        |    |   |     |    |         |
  | LMOTS_SHA256_N32_W8 | SHA256 | 32 | 8 | 34  | 0  | 1124    |
  |------------------------------------------------------------|

Where n is the number of bytes of the output of the hash function and p is the number of n-byte string elements. This means basically for the OTS private key we have n * p keys (+ 4 bytes for the typecode). This would also fit for the given signature length sig_len (n * p + 4 + 32 bytes for the checksum). The OTS public key is of equal length of the private key.
LMS
In chapter 5.1 of the RFC the parameter sets of the LMS keys are mentioned.
+--------------------+--------+----+----+
| Name               | H      | m  | h  |
+--------------------+--------+----+----+
| LMS_SHA256_M32_H5  | SHA256 | 32 | 5  |
|                    |        |    |    |
| LMS_SHA256_M32_H10 | SHA256 | 32 | 10 |
|                    |        |    |    |
| LMS_SHA256_M32_H15 | SHA256 | 32 | 15 |
|                    |        |    |    |
| LMS_SHA256_M32_H20 | SHA256 | 32 | 20 |
|                    |        |    |    |
| LMS_SHA256_M32_H25 | SHA256 | 32 | 25 |
+--------------------+--------+----+----+

Where m is the number of bytes associated with each node and h is the height of the Merkle tree.
One LMS private key consists of 2^h OTS private keys.
Questions

Is it correct that any LMS parameter set can be used with any OTS parameter set?
e.g. LMS_SHA256_M32_H25 for the Merkle tree and LMOTS_SHA_256_N32_W2 for the OTS keys.

Are those calculations of LMS private key sizes correct:
Formula: 2^h * ((n * p) + 4)

LMS_SHA256_M32_H5 & LMOTS_SHA256_N32_W8: 2^5 * ((32 * 34) + 4) = 34 944 bytes ~ 34 KB
LMS_SHA256_M32_H5 & LMOTS_SHA256_N32_W1: 2^5 * ((32 * 265) + 4) = 271 488 bytes ~ 271 KB
LMS_SHA256_M32_H20 & LMOTS_SHA256_N32_W8: 2^20 * ((32 * 34) + 4) ~ 1.1 GB
LMS_SHA256_M32_H20 & LMOTS_SHA256_N32_W1: 2^20 * ((32 * 265) + 4) ~ 9 GB
LMS_SHA256_M32_H25 & LMOTS_SHA256_N32_W8: 2^25 * ((32 * 34) + 4) ~ 37 GB
LMS_SHA256_M32_H25 & LMOTS_SHA256_N32_W1: 2^25 * ((32 * 265) + 4) ~ 285 GB

If those key sizes are correct then how would someone store them securely? Are those deep Merkle trees realistic? I guess calculating the corresponding public key can be done on demand.

Yes, each LMS parameter sets can be used with any OTS parameter set.
In the final NIST Recommendation for Stateful Hash-Based Signature Schemes there are even more parameters defined.

Those calculations are correct but we do not need to store the entire LMS tree in memory. The solution is to store the seed for the RNG in the private key and calculate the tree on demand. Requires more work but requires much less memory.

Calculations
LMOTS private key:
Size = 4 byte LMOTS typecode + 16 byte identifier + 4 byte q + n byte seed
Example: LMOTS_SHA256_N32_W8 = 4 + 16 + 4 + 32 = 56 byte

LMS private key:
Size = 4 byte LMOTS typecode + 4 byte LMS typecode + 4 byte q + 16 byte identifier + 2^h LMOTS private key size
Examples:
LMS_SHA256_M32_H5 & LMOTS_SHA256_N32_W8: 4 + 4 + 4 + 16 + 2^5 * 56 = 1 820 byte
LMS_SHA256_M32_H25 & LMOTS_SHA256_N32_W1: 4 + 4 + 4 + 16 + 2^25 * 56 = 1 879 048 220 byte ~ 1.9 GB


How is the x coordinate of a "point at infinity" encoded in a Secp256k1 signature? I'm testing an implementation of Bitcoin, which uses the curve Secp256k1 for ECDSA, and I want to see how it handles the point at infinity ($0$) if present in a signature. For example, r could be the x coordinate of the encoding of the point at infinity.

How is the $0$ encoded? Can it be encoded?

I found that bouncycastle prefixes the encoding of 0 with 0x00, and has some other defined prefixes (ECCurve.decodePoint()) but I don't known how this information applies (or even if it does apply to) to the encoding of $(r,s)$. This info seems to be in the X9.62 standard.

Standard encoding of the point at infinity is a single byte of value 0x00 (it is defined as such as least in P1363, possibly also in X9.62). Other representations may exist (such as a lot of bytes of value 0x00), but, in truth, the "point at infinity" does not have well-defined X and Y coordinates.

In the case of ECDSA, you generate a random value k which must lie between 1 and r-1, where r is the (prime) order of the conventional generator point G. Therefore, kG cannot be the point at infinity -- if it is, then the implementation got it wrong, or the key is not correct. Since kG is not the point at infinity, then it always has a well-defined X coordinate, and the problem does not arise. Similarly, if the point at infinity is obtained during the verification algorithm, then something definitely fishy is happening, and therefore the signature should be rejected (this cannot happen with a valid signature).

The same can be said about elliptic curve Diffie-Hellman. To sum up, if the encoding of the point-at-infinity begins to matter, then something went wrong and the best thing to do is to declare a failure (e.g. reject the signature as invalid).


ZKP for product of two primes I'm struggling to understand the intuition of the zero knowledge-ness of this proof from the following paper.
The proof is a 2 round where the verifier asks the prover to extract square roots of quadratic residues.
I've read the HVZK proof (shown in the picture below) and I agree that you can produce a transcript that distributes like a normal proof, however I still can't get over the simple fact that:

Without the witness (factorization) you can't extract a square root modulo $N$.
When the proof is turned into a NIZK via the Fiat-Shamir transformation, the prover records square roots in their raw form inside the proof, so the verifier learns square roots of numbers in the group which it could not compute on its own before.

Isn't that a "knowledge" leak? Why can this proof be turned into a NIZK?
Many thanks in advance.

I'm guessing:
"HVZK" stands for "honest-verifier zero knowledge", right? Your objection is that a dishonest verifier can choose a random $x_i$, compute $\rho_i\equiv x_i^2\mod N$, and then when they get $\sigma_i$ from the prover, there is a $1/4$ chance that $gcd(\sigma_i-x_i,N)$ is a non-trivial factor. But an honest verifier should generate random $\rho_i$.
This should be secure, based on the following: Suppose $A$ is an algorithm that can factor $N$ given random $\rho_i$ and $\sigma_i$ such that $\sigma_i^2\equiv \rho_i\mod N$. Then we can factor any $N$ with $A$ by picking a random $\sigma_i$, computing $\rho_i\equiv\sigma_i^2\mod N$, and sending $\rho_i$ and $\sigma_i$ to $A$.
It seems intuitively true that the Fiat-Shamir tansform should be able to turn HVZKs into NIZKs (probably with some extra conditions). An HVZK could fail because a dishonest verifier can send a "dangerous" challenge which reveals information, but a Fiat-Shamir forces the challenges to be random. As long as such dangerous challenges are sufficiently rare, then the Fiat-Shamir transform should produce a NIZK.


Complexity leveraging in case of exponentially many hybrids Complexity leveraging is a proof technique in cryptography where the reduction algorithm runs in super-poly time. (see this). Many papers use complexity leveraging when there are exponentially many hybrids. Here is an example.

Suppose, we need to prove that two experiments $Expt \;0$ and $Expt \;1$ are computationally indistinguishable. Then, we come up with a sequence of hybrids $Hybrid \;1, Hybrid \;2, \ldots Hybrid \;N$ and prove

$Expt \;0 \approx_c Hybrid \;1$ assuming, say, one way functions.

$Hybrid \;i \approx_c Hybrid \;i+1$ assuming one way functions.

$Hybrid \;N \approx_c Expt \;1$ assuming one way functions.

If $N = poly(\lambda)$, then $Expt \;0 \approx_c Expt \;1$ assuming one way functions.
How to apply complexity leveraging argument if $N = 2^\lambda$? (Here there are many reduction algorithms each running in poly time).

You would have to be very careful with this. First, complexity leveraging is not an ideal proof technique and requires non standard assumption. But let's put that aside and assume that you are happy with assuming exponentially hard one-way functions. You still have to make sure that you get a meaningful result. The way to do this is to be extremely explicit about the running time of the adversary in Hybrid i as a function of the adversary's running time in Hybrid i-1. Then, you would be able to say at the end what the running time of the final adversary is. You may get: if the original A in Expt0 runs in time $n^c$ then the final adversary runs in time $n^c + n^{\log n}$ (which would be reasonable), but you may get that the final adversary runs in time $2^{n^c}$ (which would be meaningless). So, it depends on the exact reduction and running times.

In addition to the above, you would need to do the same with the distinguishing probability. Here also, you have to be really careful. However, I can't say how much this makes a difference, since it would depend on the proof. One immediate thing is that you would need to assume that the distinguishing probability is not just non-negligible but way below $2^{-\lambda}$ and you have to think about how reasonable this is.


Some questions on building permutations from boolean functions I've seen multiple examples of boolean functions being used as a permutation.
For example the Keccak Chi : 2.3.1 function:

from https://keccak.team/figures.html
Or as a formula: for $i=\{0..4\}$ $A_i=a_i \oplus (\neg a_{i+1} \wedge a_{i+2})$ with indexes calculated modulo 5
The first question would be, what is the rationale (or proof) why this is a permutation?
The second, related one: What are the properties, the boolean function has to satisfy that it results in a permutation?

And now regarding the inverse of such a permutation.
Are there any generic methods/algorithms to find the inverse of such a construction?
Also, what are the major contributing factors for the complexity of the inverse (number of variables, algebraic degree etc.)?
And if such a method is applied to a larger input - say $i=\{0..127\}$, is the inverse more difficult to calculate, if the function has only a few (like the 3 for Chi) or many, say 128, input variables?
Any answers/pointers are appreciated.

The general algebraic question is multifaceted and can be quite complicated. Some depend on vector space, some on extension field properties.
As mentioned in the comments checking the property can be simpler.
I answered a related question Examples of multi output bit balanced Boolean functions
Nyberg’s articles mentioned there are
K. Nyberg, Differentially uniform mappings for cryptography, 1993 and
K Nyberg, Perfect nonlinear S-boxes, 1992
both easily locatable on google scholar.
Edit: The keccak $\chi$ maps $\{0,1\}^5$ to itself.
I will use $a_i$ as input and $A_i$ as output variables as in the edited question.
Counting indices modulo 5, if there is no $i$ such that $(a_i,a_{i+2})=(0,1)$ then $\chi$ has a fixed point for that input. Let $W=\{i: (a_i,a_{i+2})=(0,1)\},$ then the general mapping just inverts the bits belonging to $i.$
Note that the sets $J_i,J_j$ where $J_i=\{i,i+2\}$ are disjoint except when $j=i+2$ or $i=j+2.$ So there is no ambiguity for determining the inverse unless we are in this special case, thus the inverse exists except in this special case. But even in this case the patterns
$(a_i,a_{i+2},a_{i+4})$ which result in bitflips are unambiguous.
If $(a_i,a_{i+2},a_{i+4})=(1,0,0)$ then $a_{i+1}$ will be flipped but not $a_{i+3}$. So $A_{i+1}=1\oplus a_{i+1},$ and $A_{i+3}=a_{i+3}.$
If $(a_i,a_{i+2},a_{i+4})=(1,0,1)$ then $a_{i+1}$ will be flipped but not necessarily $a_{i+3}$, that will depend on the value of $a_{i+6}=a_{i+1}$. But that bit is not impacted by the previous argument since $J_i$ and $J_j$ are disjoint if $i=j+1\pmod 2.$
So a unique inverse mapping exists.
Remark: In general going between "basis independent" extension field formulations of permutations vs "basis dependent" bit vector permutations is hardly straightforward. I don't see an immediate basis independent extension field formulation for this permutation, and as pointed out in the comments to the question such formulations obtained (say) by Lagrange interpolation, can be quite complicated and high degree.


Are parts of a pseudorandom string also a pseudorandom string? I am working on an exercise that encrypts a message using only the first $n$ bits of a pseudorandom generator's output $G(k)$, i.e. $F_k(m) := G(k)_{0...n−1} \oplus m$.

$k$ is chosen uniformly at random and $k, m \in \{0, 1\}^n$.
My task is to decide whether an encryption scheme based on $F_k$ can be secure against a ciphertext-only attack, a CPA attack and whether it's indistinguishable.

My idea was that, if $G(k)_{0...n−1}$ is still a pseudorandom string, the exercise reduces to the case of using the whole output of $G(k)$. Then the scheme would be secure against a ciphertext-only attack and indistinguishable, but not secure against CPA attacks since it's a deterministic scheme.

My problem is that I couldn't find out, whether $G(k)_{0...n−1}$ can be treated exactly like the entire output of $G(k)$. Furthermore, I am not sure whether my intuition about solving the exercise is right. I would appreciate any hints!

If you have a stream, $s$, of $n$ bits that is computationally indistinguishable from random, then any truncation of that $n$ bit string must also be indistinguishable from random.

The proof of this is straightforward. If $s$ was computationally indistinguishable from random, but some truncation of $s$ was not then we could distinguish the larger sequence from random by enumerating all possible truncations of $s$ and testing them against the distinguisher.

If the distinguisher identifies that any truncation is not random, then this demonstrates $s$ is not random. It acts as a distinguisher on $s$. Obviously, that is a contradiction.


Digital certificate issuing man-in-the-middle attack While obtaining digital certificate the applicant trusts the certificate authority (or registering authority) as CA is digitally certified (and applicant  has CA's public key).

To certify a domain the protocol would go like this:

I generate my public-private keys and send the authority my public key encrypted by its public key.
She encrypts a nonce and sends me to put on my website
As I'm in control of the website I put this nonce and encrypt it with her public key
She checks and issues me a digital certificate for that site.

Is there a possibility for MIM attack here as follows:

attacker between me and the CA can pretend to be me and requests certificate for domain I control. He generates his public-private keys
he intercepts the nonce sent back by the CA
he mimics my site and puts on the received nonce
CA issues the certificate to the attacker?

Yes, that man in the middle attack is possible. The problem is that there is no direct way of providing initial trust to the CA. As long as that is not possible - traveling to the CA is rather expensive - there can be no complete trust.

The validation relies on the DNS and the fact that servers generally are on relatively secure connections. I presume that the CA itself doesn't run on public WiFi either. The challenge response protocol makes sure that you have control over the domain. It also makes sure that the challenge (nonce) cannot be copied without having the private key. But in the end it is protection so that nobody can initiate the connection with the CA

And that's what this protocol really does; it makes sure that somebody else doesn't request a certificate in your name. The amount of protection against man-in-the-middle is very limited. If the server or admin PC is hacked then an attacker will of course have little problem performing the steps himself.

Don't do these steps from an insecure PC or over an insecure connection and make sure that your server and server connection are secure as well. Otherwise the chances of MiTM are heightened. Note that this will still take an active attack, and I presume you checked that the connection to the CA is performed over TLS (right?).


What is the Common Reference String (CRS) model I came across the notion of Common Reference String (CRS) model while reading this paper on a protocol for UC Oblivious Transfer: https://eprint.iacr.org/2007/348.pdf

I did some research and it seems to me that the CRS model is just some way to model hash functions: What are alternatives to the random oracle model for modelling hash functions?

My questions are:

What is exactly the CRS model?
What are the main differences, comparing to the Random Oracle Model (ROM)?
What are the advantages and disadvantages of using the CRS model instead of using the ROM?

Thank you in advance

The CRS has nothing to do with modeling hash functions. Rather, it is a model where there is a public string that was generated in a trusted manner, and all parties have access to the string. It has two flavors: a common random string (where it is just a uniformly distributed string) and a general common reference string (which may have an arbitrary distribution).
The main difference between the ROM and CRS model is that proofs in the ROM are heuristic, since the actual protocol instantiation uses a hash function that is blatantly NOT a random oracle. In contrast, proofs in the CRS model have a standard reduction-based proof of security, and so are not heuristic.
The main advantage of the CRS model over the random oracle model is that security is standard, and doesn't rely on a heuristic belief system that the real protocol that uses a standard hash function is secure. The main disadvantage is that you need to somehow generate this CRS, and this isn't trivial if there's no trust. Zcash uses a CRS and ran a large MPC protocol between many parties to generate the CRS. As long as you believe that not all the participants colluded, then you can trust the system from that point on. This is a good example of where a CRS can be deployed in reality.


How can a collision attack using MD5 be used to break WOTS It is stated in
Winternitz One time signature security that MD5 is not safe for Winternitz due to collision attack. Given that WOTS generates multiple, say 32 private keys then hashing them a number of times to obtain 32 public keys. How does a collision attack from MD5 break the Winternitz OTS?  Does this mean I have to find 32 collisions of MD5 ?

I believe that, in the question you cited, the answer included:

BTW: this appears to be more about the proof technique used to prove W-OTS, rather than the actual security; we can create MD5 collisions (invalidating the proof), however we don't know how to use those collisions to actually attack W-OTS-MD5; hence it would appear to be secure (but we can't prove it).

That is, we don't know how a collision attack would break Winternitz; we just can't prove that it can't.


Research for video game: Novice cryptography concepts I'm making a video game which has some basic cryptography as a main base for puzzle design. I'm hoping players will get great puzzle challenge and learn a few cryptography concepts through playing the game.

Can you suggest some of interesting areas of cryptography that would be interesting/fun/easy to learn and understand that I could use as a game mechanic?
Are there any instances of a single thing that are fun/interesting/unique and could be used as a puzzle?

All of these concept are masked, so that player with no experience in cryptography will ever make a connection.
Some areas that are already included are basics in substitution and transposition (Caesar, Pigpen, Rail Fence, Grille...).
For example of puzzle design: Grid Grille puzzle was modified in such a way that other shapes are used instead of a square, most notably 4 triangles in 1 triangle.

Depending on your video game design you maybe can utilise a many-time pad. Many-time pad is many plaintexts encrypted by XORing them with a common string.

One-time pad cannot be broken but many-time pad can, especially if the players can make an educated guess about what the plaintext message might contain.

You can also try encrypting numbers with RSA but with small modulo n so that players can easily factor it.


Self-expiring symmetric keys, or: cryptography in absence of secure deletion I can encrypt some data D using a random symmetric key K, obtaining a ciphertext C, and then encrypt K with my public key Pub and obtain H. So far so good: I can only decrypt C if I have H and my private key Priv. My goal is to only bring around Priv, and keep both C and H on a public server. Assume C is too large to be re-uploaded, and we do not trust the server so secure deletion is not possible.

The question is: what if Priv gets compromised? In the above scenario, nothing good. C will be on the server forever, together with H, leaving to the attacker the time to read C and decrypt it.

This is bad in comparison with e.g. a mail server, where I have to log in to view my data: as soon as I notice that my password has been compromised, I can change it, and if the attacker did not download C yet, I'm safe.

So the real question is: are there any known, or standard, methods to create "self-expiring symmetric keys"? What I imagine is that I could avoid to store H on the server, but still be able to derive H from some smaller secret (kept on the server) and some external "aid" which should be as simple and less trusted as possible, e.g. a random stream of data, in such a way that it is possible to reconstruct H only for a limited amount of time.

After the key is expired, the data would be lost. Before, one should be able to refresh the key.

I don't believe there is any way to achieve what you want, within your constraints.

You stated as a requirement that a user must be able to get all of their data from the server, without storing anything other than their private key.  If an attacker learns the private key, the attacker then knows everything that the user does, so of course the attacker can decrypt too.

A random beacon (a continuous, public stream of random numbers) doesn't seem to help, since an attacker can record a copy of that entire stream.  Also, it would rely upon on some external trusted party to generate the stream; if you are willing to trust a third party, there are simpler solutions.  An example of such a solution: store $H$ on the trusted third party and return it only upon request to users who prove knowledge of the private key, and only if the expiration date has not yet passed.

A different solution is to have the user change their private key every so often.  To ease this, they can generate a long-lived keypair which is used only for signing, and then generate short-lived keypairs every so often.  The long-lived key is used to sign each short-lived public key and publish this certificate.  To send a message to this user, you look up the current short-lived public key, check its corresponding cert, then encrypt to the short-lived public key.  The user can then securely delete their short-lived keypair when it expires. (I think you might also be able to build sophisticated schemes that eliminate the need for a lookup, but I'm not 100% certain about that.)


What does an RSA signature look like? I am using OpenSSL libs to generate signatures. Internally, I learn that a signature is a hash of the message with some padding added to it.
I am trying to understand the structure of a signature. If I use SHA1 as the digest algorithm for the signature, and say a 1024 bit Key, can you please tell me how the signature format looks like?

My code snippet:

   const EVP_MD *md = EVP_get_digestbyname("SHA1");
   EVP_SignInit(ctx, md);
   EVP_SignUpdate(ctx, plaintext, plaintext_len));
   EVP_SignFinal(ctx, sig, &siglen, pkey));

From the source code I am trying to understand how 'signing' works.  What exactly is added to the hash value before actually "encrypting" it with the RSA key? Assuming the RSA signing takes the RSA_PKCS1_PADDING as default(?),How many bytes of this 'padding' does it append and how does it vary with the digest algorithm?

If I dissect such a signature, how should the bytes look like?

An RSA signature is a sequence of bytes of the same size of the modulus. If the key uses a 1024-bit modulus $n$, then the signature value is, numerically, an integer in the $1..n-1$ range, and the PKCS#1 standard specifies that this integer should be encoded as a sequence of bytes of the same length as would be needed to encode the modulus, i.e. 128 bytes for a 1024-bit modulus (big-endian unsigned convention).

The signature process looks like this:

The message to be signed $m$ is hashed with hash value $h$, yielding $h(m)$, which is a sequence of bytes (say, 32 bytes if $h$ is SHA-256).
The hash value is padded: a byte sequence is assembled, consisting of, in that order: a byte of value 0x00, a byte of value 0x01, some bytes of value 0xFF, a byte of value 0x00, a fixed header sequence H, and then $h(m)$. The header sequence H identifies the hash function (strictly speaking, there are for each hash function two possible header values, and I have encountered both). The number of 0xFF bytes is adjusted so that the total sequence length is exactly equal to the encoding length of the modulus (i.e. 128 bytes for a 1024-bit modulus).
The padded value is then interpreted as an integer $x$, by decoding it with the big-endian convention. Due to the sequence size and the fact that the sequence begins with a 0x00, the value $x$ is necessarily in the $1..n-1$ range.
The value $x$ is raised to the power $d$ (private exponent) modulo $n$, yielding $s = x^d \pmod n$.
The $s$ value is encoded into a sequence of the same length as $n$; that's the signature.

To verify, the signature is decoded back into the integer $s$, then $x$ is recovered with $x = s^e \pmod n$, and encoded back. The verifier then checks that the padding as explained above has the proper format, and that it ends with $h(m)$ for the message $m$.

All of the above is the "v1.5" PKCS#1 padding. The standard also defines a newer one, called "PSS", which is a bit more complex, but allows for some kinds of security proofs.


Is it possible to identify a Serpent encryption key in memory? It has been shown that AES keys that are in use can be identified in memory. This identification relies on discovering expected round keys in memory that are contained within the key schedule.

My question is: can we, by extension, assume that the same technique, at least theoretically, can be used to extract Serpent and Twofish keys from memory since they both have a key schedule as well??

(See also Extracting RC4 and 3DES keys from system memory.)

Yes, Serpent also does a deterministic well-known key expansion. So it should be possible to identify the sub keys in memory. You will want to know what implementation you are looking for since there is more than one sensible order for the key material to be in.


Definition of secure computation with more that two parties In Definition of secure computation in m-party case with respect to semi-honest adversary (Definition 7.5.1 in Foundations of Cryptography: Volume 2, Basic Applications by Oded Goldriech) we say protocol $\Pi$ is secure if there exists simulator $S$, such that for every $I\subset [m] = \{1,2,...,m\}$ output of simulation and $VIEW^\Pi_I$ be indistinguishable.

I don't understand why it is not enough to construct a simulator only for every party $p\in{1,2,...,m}$ (instead of any subset of parties). Besides order of quantifiers seems confusing to me too. It is mentioned in the footnote that (page 697):

  Note that for a fixed $m$, it may make as much sense to reverse the order of quantifiers (i.e., require that “for
  every $I$ there exists an algorithm $S_I$ ”).

What does "may make as much sense" mean? The original order of quantifiers doesn't make sense to me, but the reverse does. (Reverse order just seems like definition of two-party case.)

I would appreciate:

1) explanation (maybe including simple example) that give me the intuition about why security is defined this way.

2) Suggestion of good reference (almost as good as Yehuda Lindell's tutorial) as an example of security proof in multiparty case.

It is not enough to be able to simulate the view of a single party, because corrupted parties may cooperate. As mentioned in the book, it may be easier to view all the corrupted parties as a single entity. It is the view of this single entity that we must simulate.

If $m$ is fixed, the order of quantifiers does not matter, because the number of subsets $I$ is fixed and so a single simulator $S$ can of course incorporate the code of the simulator $S_I$ for each $I$ (since $S$ is given $I$, it knows which of the $S_I$ to run as a subroutine).

(Edited after a comment.) If $m$ is not fixed, this may not be possible (for example if $m$ grows polynomially with the security parameter, the number of subsets grows exponentially), so you get two possibly different definitions depending on the order of the quantifiers. The one with a single simulator is stronger (if there is a single simulator that can generate a valid view, there trivially is a family of simulators that can, but not the other way around), so it is the one that was used. In practice, no protocol is known which is secure for the first definition and not the second.


What problems with "random" data would cause this result from Ent? I'm playing around with a novel kind of source of "random" data and Ent is currently giving me results like this:

Entropy = 7.977080 bits per byte.

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

Chi square distribution for 13239 samples is 422.94, and randomly
would exceed this value less than 0.01 percent of the times.

Arithmetic mean value of data bytes is 127.5968 (127.5 = random).
Monte Carlo value for Pi is 3.180417044 (error 1.24 percent).
Serial correlation coefficient is 0.009151 (totally uncorrelated = 0.0).

The Monte Carlo Pi value and Entropy results get even better as you increase the N value, but the Chi squared results get higher and higher and over trivially small N values you keep seeing the chi squared percent at less than 0.01.

What kind of non-randomness in the data does this suggest we're looking at?

Edit: It was recommended I specify that I understand that these high chi squared values suggest that the data is non-random.  I'm trying to understand the data a bit better so I'm wondering what properties of the data would make it so good at all of these other entropy tests while failing at the chi square test in a specific way every time.

Edit 2: Running the program for a couple of days and I will report in with the Ent results and maybe put a hex dump of the data up when it's done.  It would be a really big help if someone could just figure out exactly what makes this data "less than" random

I've seen this before in the true random number generators I've been working on.  Look at the following test.  I've ent'd two jpegs, one 10 times the size of the other.  A jpg is highly compressed so can't be compressed much further, and incompressibility is one of the definitions of random.  It has however, some non random bytes such as control structures and the golden bytes.  So it's almost random, as is your data.

C:\scratch>ent lada.jpg
Entropy = 7.956933 bits per byte.

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

Chi square distribution for 4685491 samples is 319354.77, and randomly
would exceed this value less than 0.01 percent of the times.

Arithmetic mean value of data bytes is 132.0827 (127.5 = random).
Monte Carlo value for Pi is 3.027673947 (error 3.63 percent).
Serial correlation coefficient is 0.000597 (totally uncorrelated = 0.0).

C:\scratch>ent lena.jpg
Entropy = 7.947390 bits per byte.

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

Chi square distribution for 408932 samples is 33552.83, and randomly
would exceed this value less than 0.01 percent of the times.

Arithmetic mean value of data bytes is 116.3320 (127.5 = random).
Monte Carlo value for Pi is 3.357464603 (error 6.87 percent).
Serial correlation coefficient is 0.020913 (totally uncorrelated = 0.0).

Compressibility stays similarish as a jpeg is a jpeg.  pi improves for the larger lada file somewhat as you have more samples that are randomish.  However, Chi increased exponentially as you have more and more control structures (read non random values) and as Chi uses a squared function in the calculation this error builds rapidly.

In summary, there are some values in your data set that occur at way too wrong a frequency.  A histogram of the data over the full 0-255 range in a spreadsheet /gnuplot might help to show something obvious, but with  chi of only 400 it might be subtle. You're hampering your analysis with the small sample size.  ent is typically run against an 11 MB data set to get a target Chi of about 250.

One methodology I find useful is to draw a picture of the data.  Load your data file into a pixel editor like GIMP as raw data and create a square image.  Subtle patterns will show up if you sit and stare at it for a few minutes.

There are two questions you must consider.  One, have you cocked up your randomness extraction algorithm and it's something you can eventually fix?  Two more worryingly, is are you totally, utterly and willing to stake your puppy's life on it convinced that the original source of your numbers is really random?

Supplemental:

I don't see dips in your histogram.  I see waves.  The black line identifies at least to me, two halves of the histogram.  Eight less strong ones (pink line), then 16 (blue line) and so on in powers of 2.    That kinda corresponds to bit positions.  It seems fairly regular.  Does that mean anything to you?  I think that your seeing a strobe effect between threads and your timer /counter with some jitter overlaid.  I think that the strobe effect is probably totally uniform.  I think the jitter is the source of your randomness, and I think that it's true randomness.  Congratulations.

If you're interested in pursuing the random generator thing, ent is naff at measuring entropy.  Take the file you generated for the histogram, and compress it as hard as you can. I suggest the program fp8, but zipping will be a good start.  The resultant file will be a very good measure of how many truly random bytes you're generated.

See, printing out an image (in whatever form) is useful.

(Help Centre will be angry with us for having this discussion).


Problems with calculating inverse of finite field $GF(2^8)$ of AES I know this question is being asked to death here but please hear me out.
I was learning how to encrypt using AES and in one of the methods, we have to calculate multiplicative inverse in the finite field $\operatorname{GF}(2^8)$ to make $S-box$.
I learned finite fields and its operations but while calculating the inverse of $x^7+x+1$(83 in hex) with $\bmod x^8+x^4+x^3+x+1$(standard for AES).
Here my calculations using extended Euclidean algorithm:
\begin{align}
(x^8+x^4+x^3+x+1) &= (x^7+x+1)(x) + (x^4+x^3+x^2+1)\\
(x^7+x+1) &= (x^4+x^3+x^2+1)(x^3+x^2+1) + (x)\\
(x^4+x^3+x^2+1) &= (x)(x^3+x^2+x) + 1\\
\end{align}
now calculating $s$ and $t$ for $$(x^8+x^4+x^3+x+1) \cdot s + (x^7+x+1)\cdot t = 1$$

let $a = x^8+x^4+x^3+x+1$,
$b = x^7+x+1$,
$c = x^4+x^3+x^2+1$,
$d = x$

$$c + d(x^3+x^2+x) = 1$$
$$c + (x^3+x^2+x)(b + c(x^3+x^2+1)) = 1$$
$$c + (x^3+x^2+x)b + (x^6+x^4+x^3+x^2)c = 1$$
$$(x^3+x^2+x)b + (x^6+x^4+x^3+x^2+1)c = 1$$
$$(x^3+x^2+x)b + (x^6+x^4+x^3+x^2+1)(a + b(x)) = 1$$
$$(x^3+x^2+x)b + (x^6+x^4+x^3+x^2+1)a + (x^7+x^5+x^4+x^3+x)b$$
$$(x^6+x^4+x^3+x^2+1)a + (x^7+x^5+x^4+x^2)b$$
now, (c inverse)
$$c^{-1} = t* \mod a$$
$$c^{-1} = t$$
$$=x^7+x^5+x^4+x^2$$
that is in hex = B4
which is not what this table shows
http://tratliff.webspace.wheatoncollege.edu/2016_Fall/math202/inclass/sep21_inclass.pdf
the inverse should be 80(hex).
While I was trying different values, I found that the values which are two steps or less in
Extended Euclidean algorithm is correct means when it takes more than 2 steps I am getting different values of course I may be just mistaken here but this is what I know.
Ps:- I am trying to solve this mystery for 3 days now so any help is appreciated thank you

Let $g(x) = (x^8+x^4+x^3+x+1)$ and $p(x) = (x^7+x+1)$
The GCD is correct and it is $1$ as the last non zero remainders.
\begin{align}
(x^8+x^4+x^3+x+1) &= (x^7+x+1)(x) + \color{blue}{(x^4+x^3+x^2+1)}\\
(x^7+x+1) &= (x^3+x^2+1)\color{blue}{(x^4+x^3+x^2+1)} + \color{red}{(x)}\\
(x^4+x^3+x^2+1) &= (x^3+x^2+x)\color{red}{(x)} + 1\\
\end{align}
Now collect back to find to reach Bézout's identity $$a(x)g(x) + b(x)p(x) = d(x)$$ where $d(x)$ is the $\gcd(p(x),g(x))$
and we want to keep $g(x) $ and $p(x)$

begin from the last equation ( the last one that has non-zero remainder)
$$(x^4+x^3+x^2+1) =  (x^3+x^2+x) \color{red}{(x)} + 1$$  change to  (in $GF(2)$ we have $-1=1$)
$$1 = (x^4+x^3+x^2+1) + (x^3+x^2+x)  \color{red}{(x)}$$

Now substitute $\color{red}{(x)}$ from the previous
$$(x^7+x+1) = (x^3+x^2+1)\color{blue}{(x^4+x^3+x^2+1)} + \color{red}{(x)}$$
that is
$$\color{red}{(x)} = p(x) + (x^3+x^2+1)\color{blue}{(x^4+x^3+x^2+1)}$$
now substitute
\begin{align}
1 &= \color{blue}{(x^4+x^3+x^2+1)}) + (x^3+x^2+x)\big[(p(x) + (x^3+x^2+1)\color{blue}{(x^4+x^3+x^2+1)}\big]\\
  1 &= \color{blue}{(x^4+x^3+x^2+1)}) + (x^3+x^2+x)p(x) + (x^6 + x^2 + x)\color{blue}{(x^4+x^3+x^2+1)})\\
1 &= (x^3+x^2+x)p(x) + (x^6 + x^2 + x +1)\color{blue}{(x^4+x^3+x^2+1)})\\
\end{align}

Now substitute $\color{blue}{(x^4+x^3+x^2+1)}$ from the first equation
$$g(x) = p(x)(x) + \color{blue}{(x^4+x^3+x^2+1)}$$
$$\color{blue}{(x^4+x^3+x^2+1)} = p(x)(x) + g(x)$$
\begin{align}
1 &= (x^3+x^2+x)p(x) + (x^6 + x^2 + x +1) \big[p(x)(x) + g(x)\big]\\
1 &= (x^3+x^2+x)p(x) + (x^7 + x^3 + x^2 + x) p(x) + (x^6 + x^2 + x+1) g(x))\\
1 &= (x^7 ) p(x) + (x^6 + x^2 + x) g(x))\\
\end{align}
Now that modulo $g(x)$ of both sides
$$1 = (x^7 ) p(x) $$ and this implies inverse of $p(x)^{-1} = x^7$

Note: for the field calculations I've used a Sagemath code as below, and this can be used for AES calculations.
#Base field
R.<y> = PolynomialRing(GF(2), 'y')

#Defining polynomial
G = y^8+y^4+y^3+y+1

#The field extension
S.<x> = QuotientRing(R, R.ideal(G))
S.is_field()

#this is zero
X = x^8+x^4+x^3+x+1
print(X)

#GCD
print(X.gcd(x^7+x+1))
#to find and inverse use the 1/
1/(x^7+x+1)
#field calculations
(x^3+x^2+1)* (x^4+x^3+x^2+1) + (x)


Understanding the definition of Schnorrs identification protocol I have some trouble in understanding the definition of Schnorr's Identification protocol. The is the definition that I received:

Prover and verifier agree on a cyclic group $G$ of prime order $q$ generated by $g$.

The prover sends $r=g^k$ for a random $k$
The verifier sends $e \in_R Z_q$
The prover sends $s=k+xe$
The verifier now verifies if $r=g^sy^{-e}$

Now I don't understand why $r$ and $e$ have different formulas. As far as I understand, $r$ is an element of the cyclic group $G$, and $e$ also. What is the difference between:

$\in_RZ_q$

and

$g^k$ for a random $k$

mean?

The difference is the amount of information you have about the structure of the numbers.

Let $e\in_R\mathbb Z_q$. Then you know that the $e$ you have, is a random number from that set. You know no more and no less.

Let $r=g^k$ for some $k\in_R\mathbb Z_q$. Then you know that the $r$ is a random number from the group and you know its discrete logarithm to a pre-defined element. The fact that you randomly picked $k$ doesn't matter, you still know it and can use it in step 3. Even better you know that it is highly unlikely that somebody else will be able to infer $k$ from $r$ (because that is the discrete logarithm problem).

So you see: You know a lot more about $r$ than about $e$ because it was generated in this slightly different way.


Questions about length key of RSA 2048 bit I use putty gen to generate RSA key, I choose length of key is 2048 bit, it generate public key:

ssh-rsa AAAAB3NzaC1yc2EAAAABJQAAAQEA10prz5/FvHX7cx5aowiF+eO8uQuKTYSU0rA0x5yNPD5yTI0HGmEBTnhia4iOhOzwg0BevOZR1SClBpCRTZViym2Z+ohAGt65mWq+2LLhRf3MNpcM6Ttm8IXFxRiVR9iALk9cPsXu6zz4x7RT9vZG7rE1+KbeeSn1gacpCeudsEYCDOrgenH78hNXCLcc6TdKOWnBlASf8coj/T1czUW78S9tcqu7bFrR7N6xfj9M0d8e8oyBOqYrhv3uFmLxvVQ2yxZrJ0ILhAf8KhrflX6SytO5s/K5zTWRkjhwg83V8Qs30LWd79xJgpaUESaWFeS17x6iit8uEjMtPqBGnqLryw== rsa-key-20160620

I don't know why this key is 2048 bits?

The binary base 64 encoded blob contains a modulus which is 257 bytes in size:

00D74A6BCF9FC5BC75FB731E5AA30885F9E3BCB90B8A4D8494D2B034C79C8D3C3E724C8D071A61014E78626B888E84ECF083405EBCE651D520A50690914D9562CA6D99FA88401ADEB9996ABED8B2E145FDCC36970CE93B66F085C5C5189547D8802E4F5C3EC5EEEB3CF8C7B453F6F646EEB135F8A6DE7929F581A72909EB9DB046020CEAE07A71FBF2135708B71CE9374A3969C194049FF1CA23FD3D5CCD45BBF12F6D72ABBB6C5AD1ECDEB17E3F4CD1DF1EF28C813AA62B86FDEE1662F1BD5436CB166B27420B8407FC2A1ADF957E92CAD3B9B3F2B9CD359192387083CDD5F10B37D0B59DEFDC4982969411269615E4B5EF1EA28ADF2E12332D3EA0469EA2EBCB

The first byte is set to 00 to indicate that it is a positive number. 256 bytes equals 2048 bits, which is the size of the modulus. The modulus in turn defines the key size of RSA.