How to contruct a pseudorandom with a specific property How to construct a pseudorandom function $PRF$ with the following property:

Probability that $PRF(k_1,i)=PRF(k_2,i)$ is negligible, for all keys $k_1,k_2$ such that $k_1\neq k_2$

Does the PRF with the above property have to be Pseudorandom function tribe ensembles mentioned here or it can be any PRF with sufficiently large output range.

Depending on what you consider an acceptable approach, you could get there by having a random-looking function from your PRF domain to a prime-order cyclic group, and then use the permutation $x \mapsto x^k$ on the group.

Under reasonable assumptions and choice of group, this is a PRF. And since the key-dependent part is a permutation, two keys will never map the same $i$ to the same function value.

So this construction satisfies your requirements, but it is not a tribe ensemble.


Can we use a Merkle Tree structure to reduce digest size? A 2nd preimage attack is possible on the standard Merkle tree as pictured below.

I'm aware that we can add identifiers (to differentiate nodes) to the input of each hash as discussed in the link.  If then using a good hash function, it should be resistant to any kind of attacks.
However it would be preferable to have a tree structure where a change in L1 (even if it hashed to Hash0-0) would affect Hash0.
If such a tree structure is viable, it seems we could use it to reduce the digest size used, without necessarily reducing security to the same degree.
That is, if it is difficult to find a pre-image collision in a secure 256 bit digest with a 256 bit input, is it just as difficult to find a pre-image collision in a 128 bit digest when the 256 bit input is constrained by being used further up the tree?
To use a rubbish hash as an example.  For MD5, it may be possible to find a pre-image collision for X.  Is it harder if I ask you to find an input that hashes to X, where the input must also be used to create another pre-image collision at the parent/grandparent of X?
To illustrate my idea, see a simple example of what I imagine below.  Everything except the red blocks would be 128 bit.  'Split & XOR' is splitting the 256 bit DATA block into two 128bit blocks and XORing them together.

The aim being that the attacker (after seeing DATA0 and relevant auth path) cannot simply provide an alternative DATA1, as it will also need to 'Split & XOR' to create the correct parent block. The idea is the attacker is left to find the real 256 bits of DATA1, not just a pre-image for the 128 bits of HASH1.
Questions

Is this a viable idea?
Is such an idea (obviously not as rudimentary as mines) employed anywhere?

The problem is that your construction (the whole second picture) still constitutes a compressing function with 128bit output. Hence, we can find collisions at complexity about $t\cdot2^{64}$, where t is the runtime of your construction.
Indeed, it seems that a little misconception motivates your work: You sound as if it was harder to find a collision than a second-preimage. However, it is the other way around; finding a second-preimage is (generically) a lot harder than collision-finding. The complexity of a generic second-preimage attack is equal to that of a generic preimage attack. The complexity of a generic collision attack is only the square root of the complexity of a second-preimage or preimage attack.


Block Cipher Mode Amicable to Fast Key Change/Rotation Like XOR? I'm working with documents encrypted in long term storage. When a client requests the document, the document should be delivered encrypted under a distinct key (distinct from the long term storage key).

For efficiency, I want to avoid decrypting the document under its long term key and then re-encrypting under a client delivery key.

Are there any FIPS 140-2 block cipher modes of operation that are amicable to a simple XOR for the transformation? That is:

Client Key = Long Term Key ⊕ Random Key
Client Encrypted Document = Long Term Encrypted Document ⊕ Keystream based on Random Key

When the client receives the document, he/she would:

Decrypted Document = Decrypt (Client Key, Client Encrypted Document)

I think a mode like CTR is close to what I want since it Encrypts the Counter and then XORs it with the plain text, but I would like to avoid the "Encrypts New Counter" if possible.

The block cipher and approved modes are important because I'm constrained by FIPS 140-2.

Any insight or help would be greatly appreciated.

A better way to solve your problem is: on the server, encrypt the document under a document encryption key (a unique key that's specific to that document).  The document remains encrypted in storage encrypted under this document key.  When a client requests the document, send the client a copy of the encrypted document, as well as an encryption of the document key encrypted with the client's key.  Now the client can recover the document key and then decrypt the document.

This will be very efficient and will meet all of your requirements.  And, it is implementable using only standard cryptographic primitives approved in FIPS 140-2.

If you ever need to change the document, you should change its document encryption key to a new, unique key chosen independently of the previous version.  Re-encrypt the new version with its new unique key.  This way, users who have previously downloaded the old version of the document don't automatically get access to the new version (unless you decide they should be allowed to).  This lets you implement revocation to the extent that revocation is possible in this setting.  Thanks to DrLecter for this suggestion.


Wanted: Simple ring signature example I spent all day trying to figure ring signature schemes out but apparently I wasted time.
I read the original ring signature paper (Rivest's How to leak a secret).
I'm having numerous problems. Let's just say that a nice and simple example would make everything clear.

I'm talking about something like this example for RSA.

The problem is that no one provides this. I read 12 papers and… nothing. I would like to have an example with small numbers. Is this even possible? Could you provide such a “toy” example?

If I can be more specific: my problem with the original paper is step 4:

  solve for…

I have no idea how to solve an equation where on the left side I have the encryption (known key) of an unknown value and a value on the right side.

Here is an explanation of step 4.
Look at Figure 2 of the paper.
Lets say $y_s$ is $y_3$ at 6 o'clock.
Start at 12 o'clock and calculate going clockwise until you arrive at 6 o'clock. Denote the result by $r$.
Start again at 12 o'clock and calculate going counter-clockwise until you arrive at 6 o'clock. Denote the result by $l$.
Now $l =r \oplus y_s$, which gives the solution $y_s =r \oplus l$.


How to check whether the given curve is Elliptic or not? I've given a curve E5(2,3) over Zp. How to check this curve is Elliptic or not? I know the curve formed by this will be:
(y2) mod 5 = (x3 + 2*x+3)mod 5.

For most cases, you can take this as a (simplified) definition of Elliptic Curve:
An elliptic curve over $K$ (a field) is a plane algebraic curve over $K$ defined by an equation of the form

$y^{2}=x^{3}+ax+b$    (1)

($a,b \in K$) that is non-singular (it has no cups or self-intersection).

Since the curve you give in the question is of the form $y^{2}=x^{3}+ax+b$, we just need to check the non-singularity!

This can be done by computing the discriminant

$\Delta = -16(4a^3 + 27b^2)$.

Fact: an algebraic curve defined by an equation of the form (1) is non-singular if and only if its discriminant is non-zero (this is a standard result in the theory of elliptic curves)

In our case, $\Delta = -16(4*8 + 27*9) = -16(32+243) = -16(275) = 0$ (mod 5)

So the discriminant is zero in the field $\mathbb{Z}_5$, hence the curve is singular, hence it is not an elliptic curve.

Hope it helps, feel free to ask for further details.


How exactly is the output of the XOR step in PBKDF2 used? I'm attempting to diagram PBKDF2 for a school project and I'm not 100% sure how to represent the XOR step. Specifically, I'm confused as to whether the output of the XOR step is used in subsequent rounds or if it is calculated each round in order to make all rounds identical. Here's a diagram showing what it might look like if the answer is that the output of the XOR step is not used as an input to later rounds. Is this correct?

This diagram is based on the one on the very excellent blog post here: https://stewilliams.com/serious-security-how-to-store-your-users-passwords-safely-2/

So, I've been interested in building a diagram myself, and I find your diagram slightly misleading. I don't know if it's a mistake, or intentionally hiding specific pieces of the algorithm, but I think it could benefit from more granularity.

According to RFC 2898, the algorithm is as follows:

Take the ceiling of the division the desired key length (dkLen) by the digest size. This will give you the number of intermediate keys to concatenate at the end.

So, for a 512-bit key, using HMAC-SHA-256 as the hashing function, we will only need 2 intermediate keys to concatenate, each 256-bits in size:

CIEL(512/256) = 2

For each intermediate key T_i, apply F(P, S, c, i), where F() is a generic function defined below, P is your password, S is a salt, c is the number of rounds, and i is the intermediate key index.

Thus, T_1 = F(P, S, c, 1), and T_2 = F(P, S, c, 2). The final key will be those concatenated:

T = (T_1 || T_2) = (F(P, S, c, 1) || F(P, S, c, 2))

F() is defined as the exclusive-or sum of the first c iterates of the underlying pseudorandom function applied to the password and the concatenation of the salt and the block index i.

Thus, F(P, S, c, 1) = U_1 XOR U_2 XOR ... U_c and F(P, S, c, 2) = U_1 XOR U_2 XOR ... U_c. In other words, each intermediate key is processed with c rounds. Thus, for 2 intermediate keys, we are doing 2c rounds to build the final key. Generically, for n-intermediate keys, we are doing n*c rounds to build the final key.

U_i is defined as the most granular function, giving us the interface to the pseudorandom hashing function. U_i is processed c times using its previous output as the "salt" for the next input

Note that at the first round, we concatenate the intermediate index counter to the salt, thus ensuring that U_1 is always unique for each intermediate key.

U_1 = PRF(P, S || i)
U_2 = PRF(P, U_1)
...
U_c = PRF(P, U_c-1)

So, if we specificed c=100, then:

T_1:
  U_1 = PRF(P, S || 1)
  U_2 = PRF(P, U_1)
  ...
  U_100 = PRF(P, U_99)
T_2:
  U_1 = PRF(P, S || 2)
  U_2 = PRF(P, U_1)
  ...
  U_100 = PRF(P, U_99)

Finally, concatenate the intermediate keys, producing the desired key length:

T = T_1 || T_2

Thus, in your diagram, I think you should specify that "PRF" is doing c-rounds of XOR with to produce the intermediary key.

I think this flowchart might be a bit more thorough:


Elliptic curve group over a prime finite field $F_p$ If $p$ is a big prime, and the elliptic curve $E$ is defined over $F_p$ by the equation $y^2=x^3+ax+b$ where $a,b\in F_p$. The point on $E/F_p$ together with the infinite point $\mathcal{O}$ form a group $G=\{(x,y):x,y\in F_p;(x,y)\in E/F_p\}\cup\{\mathcal{O}\}$. Then  is $G$ a cyclic group? what's the order of $G$?

The cyclic group over the ECDLP problem is posed is a subset of the set of point of the elliptic curve. That is to say, not all the points in the referred curve will be in the cyclic group. What you've called as $G$ confuses with another notation of the generator of a cyclic group $<G>=\{G,[2]G,\cdots,[n]G=\mathcal{O}\}$.

This is the meaning of what you've may heard as the cofactor ($h$). There is a relation between the number of points in the elliptic curve (the cardinal $|E(\mathbb{F}_p)|$) and the order of the mention cyclic group ($org(G)=n$). Following the P1363, the cardinal of a cryptographically good curve should be prime or "almost" prime.

What this almost mean is to factorize in one big number and another very small. $|E(\mathbb{F}_p)|=n\cdot h$, where $n >>> h$. Back to P1363, $h$ shall not be other than $1$, $2$ or $4$. In a $h=1$ your cyclic group fits with the complete set of points in the elliptic curve. On bigger cofactors, smaller the cyclic group; but don't panic, a $192$ bit curve with a cofactor $2$ can be like a $191$ curve with a cofactor $1$ (despite other issues that suggest to avoid cofactor $1$).


NTRUencrypt in NIST competition Why did the NTRUencrypt team not maintain the NTRU1024 release in the NIST second-round competition?

Is this because of the speed performance or security performance or other things?

This has been answered on the PQC forum. The question was asked by El Hassane Laaji:

  Hello NTRU team

  Can you say me, why you didn't keep the NTRUencrypt-1024 release, is it because of > speed performance or security performance.

  Best regards.

The reply came from John Schanck:

  Thanks for your question. To clarify for others, the "NTRUencrypt-1024"
  parameter set was proposed in the first round NTRUEncrypt submission for
  use with the ss-ntru-pke and ss-ntru-kem schemes. I'll split your question
  into two parts:

  Why didn't we recommend ss-ntru?
  Why didn't we recommend an NTRU variant that uses Z[x]/(x^1024 + 1)?

  Regarding ss-ntru:

  At a fixed security level, NTRU and LWE schemes have a trade-off
  triangle between

  the correctness of the decryption procedure,
  the width of the coefficient distributions,
  the compactness of public keys and ciphertexts.

  The second round NTRU team wanted a compact scheme with a correct
  decryption procedure. The coefficient distribution used in ss-ntru
  is not compatible with that goal.

  Regarding Z[x]/(x^1024 + 1):

  It's not clear to us that there's a real need for an NTRU parameter set
  with such a large n. The largest n that we recommend is 821.

  Best,
  John (on behalf of the NTRU team)


Certificateless cryptography While reading "Certificateless Public Key Cryptography" by Author Sattam S. Al-Riyami and Kenneth G. Paterson, they have considered generation of private keys by a Key Generation Center (KGC). If the KGC gets compromised it will break security, so why should a KGC generate private keys.

Will it be possible that user will generate pair of public and private keys and for authenticity of public key only, we will use some trusted center?

If the KGC gets compromised it will break security, so why should a KGC generate private keys.

Certificateless crypto tries to overcome the problem which exists in identity based crypto, i.e., that the KCG generates all the private keys of the users (that is necessary in IBE, see below) and thus knows all the private keys of users (which in turn enables the KCG to decrypt all the ciphertexts intended to it's users). Certificateless crypto is similar to IBE (thus requires a KCG), but does not reveal the entire private key to the KCG.

However, if the KCG in certificateless crypto gets compromised, then you have a problem which also exists with certification authorities (CAs) in public key crypto. In particular, someone who gets the private key of the KCG in certificateless crypto or of the CA in context of public key crypto can incorporate all users he would like to. Essentially, due to fact that he can issue "fake" keys on behalf of users and pretending that they are authentic keys. However, in IBE a compromise is much more devastating than in certificateless crypto or public key crypto, since in the latter two cases the adversary may only issue new "fake" keys but is not able to regenerate all the previous keys as it is the case with IBE (which allows him to decrypt all the previous ciphertexts intended to registered users).

  Will it be possible that user will generate pair of public and private keys and for authenticity of public key only, we will use some trusted center?

That is the case in public key crypto (but as said above, that will not help against a compromised CA which certifies the keys) and in part the case with certificateless crypto.

If we do not assume a compromise of the CA/KCG but that the KCG works as it is supposed to work, then one can subsume the three different concepts as follows. I'll try to give you the big picture and hope it helps you to understand the idea of certificateless public key cryptography.

We have three basic approaches in the field of public key cryptography:

In traditional public key cryptography, a user $A$ generates a private/public key pair $(sk_A,pk_A)$ locally and since this key pair has absolutely no indication to which indentity (user $A$) it belongs, it is necessary to certify the public key, i.e., bind the public key $pk_A$ to the user $A$'s identity. This is commonly done by letting some trusted authority, a certification authority (CA), sign $pk_A$ with additional identifying information of user $A$ after user $A$ proves by some means that he really is user $A$ (the result is what is called a certificate). To encrypt some message for users you have to obtain an authentic public key of the CA and for every user.
Identity-based cryptography aims at letting the users public key be its identity (e.g., the email address) and so to remove the requirement for certificates. In ID based cryptography a user $A$ uses his identity (e.g., his email address) as public key. Now, however, since this identity could be used by anybody to compute the respective private key, it is clear, that there needs to be some other entity involved in generating the respective private key (To see the requirement for such an entity, think of the fact that I could use your email to compute a private key for your identity otherwise). We require a trusted authority (the KCG) owning some secret master key to compute the private key $sk_A$ that corresponds to the public identity string $ID_A$ and this trusted authority has to check whether $ID_A$ (e.g., the email address) indeed corresponds to $A$ and then issues the private key $sk_A$ corresponding to the identity $ID_A$. The advantage is, that you only need the parameters (corresponding to the master secret) of the KCG in an authentic fashion but no longer any authentic key of the users. Now, however, the KCG knows your private key and may use this private key to decrypt your messages, so it needs to be fully trusted. That's an inherent problem of identity based cryptography, although one may implement multiple KCGs (each having a share of the master secret) who compute the private keys for identities in a distributed fashion, so that neither gets to know the entire private key of a user. But it is questionable if this is really practical.
Certificateless public key cryptography is inbetween these two approaches. It aims to get rid of the problem that the KCG gets to know the entire  private keys of all users. Having said that, in this approach the KCG only computes a partial private key of user $A$ based on the identity $ID_A$ (clearly, also here user $A$ has to prove by some means that $ID_A$ is associated to him) and the user then combines this partial private key with some secret information (only known to him). Consequently, the KCG no longer gets to know the entire private keys of the users. Then a user, however, needs to take the parameters of the KCG and needs to combine the user chosen secret with this parameter to obtain an additional user public key. So, to encrypt a message for a user the identity string plus this public key is required. The advantage here, however, is that this public key does no longer need to be certified, since it contains the identity $ID_A$ of user $A$ and if the KCG is trusted (and the parameters of the KCG are authentic) one can assume that the user associated to $ID_A$ really corresponds to $A$ and holds the corresponding private key.


How to calculate RSA Key Size correctly starting from 384 bits to 15360 bits or beyond 15360 bits Hello fellow experts here, I am new to cryptography.

Recently I looked into RSA Key Size (Microsoft RSA library), it actually describes that the minimal key length required is 384 bits and maximum key length accepted was 15360 bits.

I really do have question here is that how can I properly calculate the key size that is between the range of 384 bits to 15360 bits easily without little to no error?

For example, currently from what i know, the possible key length in between 384 bits and 15360 bits contains the common key length of 1024, 2048, 3072 bits.

Is there any formula or calculations that other people used to know these key length? If yes, does this specific formula can be applied to calculate all possible key length between the minimal key length and maximum key length?

Oh, that one is simple: any key size is possible. The key size for RSA is set to the size of the modulus. The modulus in turn is the multiplication of two (or more) large primes. Of course, multiplication means that all prime sizes are added together (give or take a bit).

However, not every implementation will allow any key size. Since computers are byte oriented, in general the key size needs to be a multiple of 8. That makes encoding the key values easier, for starters. Quite often the numbers are calculated using words, so a 32 bit of 64 bit increment is also not uncommon. Finally, if just to avoid over-extensive testing, an implementation may also decide to just allow some specific key sizes.

Generally there is also some lower limit, if just to avoid completely insecure choices like 128 or 256 bit RSA. Creating an upper limit also makes sense, because key pair generation of 16Kib RSA keys or higher is nothing to sneeze at (and, not counting quantum cryptography, that provides a 256 bit security margin anyway).

If I remember correctly Microsoft's native RSA implementation uses 32 bit increments for the key sizes, although there are of course multiple API's and implementations of these API's (managed and unmanaged). But in the end you have to look it up, and even then changes may happen (such as upping the minimum bound or allowing more key sizes).

For common key sizes, try 2048 (on the small side), 3072 (2048 + 1024) and 4096 bits. Almost all implementations will support those key sizes and there is really not much need to choose an intermediate value, except for niche purposes (smart cards). RSA with bit size 1024 is not recommended anymore and may well be prohibited by some implementations.


The difference in size between ECDSA output and hash size So if I use secp256k1 for example, I've got my key size of 256 bit, and say I sign a SHA256 hash of a message, with size 256 bit, I get an output of size 512bit.
Why is there a difference between the hash size and the EC size. In other words, why isn't SHA512 used instead to provide bigger entropy?

I'm not too familiar with the actual ECDSA algorithm so I'm probably missing something.

Thanks!

First to explain you, why you get 512-bit outputs from a 256-bit curve:
The output is basically a point (x-coordinate is enough) and a message-dependant value, with the x-coordinate being expressed as integer. You can verify the signature by checking for a specific relationship between the point and the message-dependant value and the public key point. In order for this relationship to be build the private key is required.

Second, to answer your question why SHA-256 is used and not SHA-512. Consider how the hash function is actually used in ECDSA. You always take the $n$ leftmost bits of it, with $n$ being the curve order bitlength. So if you use SHA-512 you're "wasting" 256 bits, whereas with SHA-256 you "waste" nothing.And from a key-length point it also makes sense to settle on the 128-bit security level (which is defined through your choice of secp256) and it would make no sense to choose a hash-function with 256-bit security level to be used with a curve providing 128-bits.


Meaning of $\operatorname{UOWH}(k; u_1, u_2)$ I do not understand the format used in Shoup's "Using Hash Functions as a Hedge against Chosen Ciphertext Attack (page 8 of the PDF) for universal one way hash functions (UOWH). What are $k$, $u_1$ and $u_2$ in $\operatorname{UOWH}(k; u_1, u_2)$?

If you look up the reference [BR97] in the paper, it clearly states that $k$ is the key which is used to select a hash function from a family of hash functions and the rest of the part of the input i.e. $u_1, u_2, u_3 ...$ is the input to the selected hash such that $u_i$ is the input to $UOWH(k;u_1,u_2,...,u_i-1)$


UKS attacks. Dangers & Prevention? I am trying to understand how to prevent a UKS (unknown key-share) attack, but I am having trouble finding many resources out there to help.

Let's imagine a hypothetical secure messaging application that uses public keys to encrypt messages between any two people trying to communicate. Assume 3 people, $A$, $B$, and $M$, where $M$ is the attacker. My understanding of a UKS attack would be:

$M$ announces his public key as $B$'s public key (instead of his own)
$A$ sends $M$ a message, but $A$ is unaware that he is really encrypting with $B$'s public key
$M$ can't read the message since he doesn't have $B$'s private key, but he forwards it to $B$.
$B$ thinks the message came from $A$ (which it did, technically) except $A$ did not intend for $B$ to see the message (he thought it was going to $M$!)

You could disallow two people from having the same public key in the system, but then you could run into some confusing issues for the user if someone "stole" their public key before they joined.

My question is two-fold:

Are their any other ways to prevent these types of attacks?
What other nefarious things could $M$ do in this scenario? Is it ever practical to alter the ciphertext before sending to $B$ to change the meaning of the message in some way?

As far as I know, unknow key-share (UKS) attacks are mostly related to key exchange protocols.

Presentation
An UKS attack on an authenticated key exchange (AKE) protocol is an attack whereby an entity $A$ ends up believing he shares a key with entity $B$,and although this is in fact the case, $B$ mistakenly believes the key is instead shared with an entity $M \not = A$.Since the adversary $M$ doesn't obtain the shared secret key, he can't modify or decrypt the messages between
$A$ and $B$. However, $M$ can take advantage of the entities' false assumption about the identity with whom they share the key.

Example on authenticated Diffie-Hellman
Let's say $A$ and $B$ want to perform an AKE.
$1. \hspace{2cm} A \longrightarrow M(B):\hspace{0.3cm} Cert_A, g^a, S_A(g^a)$
$2. \hspace{2cm} M \longrightarrow B:\hspace{1cm} Cert_M, g^a, S_M(g^a)$
$3. \hspace{2cm} B \longrightarrow M:\hspace{1cm} Cert_B, g^b, S_B(g^b)$
$4. \hspace{2cm} M(B) \longrightarrow A:\hspace{0.2cm} Cert_B, g^b, S_B(g^b)$
where $M(B)$ denotes $M$ masquerades as $B$ and $S_X$ denotes a signature using the private key given in $Cert_X$.
So at the end of the protocol, $A$ and $B$ share the secret key $g^{ab}$ but $B$ mistakenly believes that this key is shared with $M$ and not with $A$. Note that $M$ does not know the shared secret key $g^{ab}$.

Answers

I am having trouble finding many resources out there to help.

I posted something some months ago about UKS attacks on KEA protocol, maybe it can help you.
Also, an interesting paper about UKS attacks helped me a lot to understand it.

Are their any other ways to prevent these types of attacks?

As mentioned in the paper cited above, there are different ways to prevent UKS attacks:

(A) Certificates of both entites should be exchanged prior to the
key    agreement protocol.
(B) CA should issue certificates whith checking that each entity
possesses a private key corresponding to its public key.
(C) Identities of the sender and intended receiver as well as
flow    numbers should be included in the messages being signed.

In my opinion, (C) is the most important one.

What other nefarious things could M do in this scenario? Is it ever practical to alter the ciphertext before sending to B to change the
meaning of the message in some way?

A famous hypothetical scenario where an UKS attack can have damaging consequences is the following:

Suppose that $B$ is a bank branch and $A$ is an account holder.
Certificates are issued by the bank headquarters, and within each
certificate is the account information of the holder. Suppose that the
protocol for the electronic deposit of funds is to exchange a key with
a bank branch via an authenticated key agreement protocol. At the
conclusion of the protocol run, encrypted funds are deposit to the
account number in the certificate. Suppose that no further
authentication is performed in the encrypted deposit message (which
might be the case to save bandwith). If the UKS attack is successfully
launched, then the deposit will be made to $M$'s account instead of
$A$'s account.

Hope it helps.


Are the Serpent Test Vectors incorrect? I have recently written an implementation of Serpent and was testing it against known vectors to no avail.  Using 256-bit key, I compared my encryption to the test vectors located here:
http://www.cs.technion.ac.il/~biham/Reports/Serpent/Serpent-256-128.verified.test-vectors
For some reason, I match none of these test vectors, and I do not know why.  I downloaded the Python implementation found here:
https://www.cl.cam.ac.uk/~fms27/serpent/serpent.py.html
The Python implementation agreed with me and disagreed with the published test vectors.  I did, however, find two files in folder Floppy 4 (ecb_tbl.txt) and (ecb_iv.txt) from the full submission package (http://www.cl.cam.ac.uk/~rja14/Papers/serpent.tar.gz) which I completely agree with. If I put in the given 256-bit key and the given plaintexts, I do achieve the correct encrypted ciphertexts.
Are the test vectors published on biham's website incorrect, or is there perhaps something I am missing?  If they are wrong, why are they still up and way easier to find than the ones I matched with?
As an example, on Biham's site,
key=8000000000000000000000000000000000000000000000000000000000000000
plain=00000000000000000000000000000000
cipher=A223AA1288463C0E2BE38EBD825616C0
But both my implementation and the Python reference implementation give:
cipher=abed96e766bf28cbc0ebd21a82ef0819
I think it has something to do with this NESSIE format, but so far, I have been unable to determine if that is true and what exactly that means.

Thanks to Richie Frame pointing out this is basically a duplicate of question
Bouncy jdk 1.51 Serpent KAT tests vs Nessie vectors
I discovered the NESSIE writes their key, plaintext, and ciphertext test vectors for Serpent in reversed byte-order (but it's not little endian inside the bytes).  So, on Biham's site,
https://www.cs.technion.ac.il/~biham/Reports/Serpent/Serpent-256-128.verified.test-vectors
, the first test vector,

key=8000000000000000000000000000000000000000000000000000000000000000
plain=00000000000000000000000000000000
cipher=A223AA1288463C0E2BE38EBD825616C0

only works if I use my implementation in reverse byte order; that is, I have to input the key:0000000000000000000000000000000000000000000000000000000000000080,
and I get the above ciphertext in reverse byte order:
cipher:  c0165682bd8ee32b0e3c468812aa23a2
Verifying this with set 3, vector 130:
key= 8282828282828282828282828282828282828282828282828282828282828282
plaintext = 82828282828282828282828282828282
ciphertext= AAA92B00896FE228BDF5AA3BA534CA44
Since the key and plaintext are reversible by byte order, I can put this key and plaintext in and expect the ciphertext in reverse byte order.  My implementation yields:
44ca34a53baaf5bd28e26f89002ba9aa.
This checks out!


Has human-generated entropy ever been a real problem? I know the topic of human brains generating random numbers has been discussed here and in Cognitive Sciences before, but I am interested in a particular part of it:

In an introductory book to cryptography I read recently ("Cuando la criptografia falla", by Arturo Quirantes), it is mentioned that in some historical occasions, mecanographers were used to generate random numbers for cryptographic purposes. However, as we know now, it was not truly random (or at least uniformly distributed) and some numbers would appear more than others. I had read about this before, but I have failed to find examples of historical events when this technique was used. I am also curious about whether any important information has ever been leaked because of the low entropy of human-brain generated numbers.

Could you please point me to some documentation about this?

In World War II, this practice of generating "random" code books by hand is known to have been used by the Special Operations Executive, or SOE:

  Various techniques have been used to do the random generation. Marks
  describes how SOE agents’ silken keys were manufactured in Oxford by
  little old ladies shuffling counters.

(Security Engineering: A Guide to building Dependable Distributed Systems)

The Marks mentioned there is Leo Marks, who was the cryptographer for SOE.  His book Between Silk and Cyanide describes a meeting with Commander Denniston of Bletchley Park:

  [Commander Denniston] questioned me closely about WOK-production, and
  wanted to know why we preferred keys made by hand to the machine-made
  keys supplied by Bletchley.

  I explained that Bletchley hadn't produced them in sufficient
  quantities, and that the ones which they'd sent us didn't seem to me
  as random as the keys the girls produced by shuffling counters.

  He looked at me doubtfully, so I gave him six sheets of keys produced
  by the girls, and six by Bletchley.  He correctly identified
  Bletchley's, agreed there was a pattern to them, ...

(WOK stands for Worked Out Keys, and is a hand-enciphered code using shared random keys to seed it)

While I'm unable to cite a specific instance of hand-generated random data being insufficient, I'm sure it happened.  The coding systems used in World War II, both manual and machine-based, generally relied upon unpredictable keys rather than strong cryptographic algorithms.  Attacks upon keying material were the primary focus (again, both by hand and by machine).  Any weakness in randomness could be exploited.

When you consider the fact that the systematic and massive compromise of Enigma was kept largely secret for around 30 years, the likelihood of a particular hand-shuffled one-time pad being compromised and documented as such is pretty low.  So the fact that examples don't abound isn't really noteworthy.

Neal Stephenson's fiction novel Cryptonomicon does include such a story (although, again, it's fiction) - Detachment 2702's one-time pad traffic is decoded for a few reasons, including re-use of pads but also insufficient randomness:

  "Enoch, why are you . . . here?"

  "Oh. I am here, in a larger sense, because Mrs. Tenney, the vicar’s
  wife, has become sloppy, and forgotten to close her eyes when she
  takes the balls out of the bingo machine."


Tor's integrity verification system? I am trying to understand the design of Tor(onion router). I am reading the original paper on the 2nd generation onion routing system. Where, under integrity checking on streams, they say, "When Alice negotiates a key with a new hop, they each initialize a SHA-1 digest with a derivative of that key. Then they each incrementally add to SHA-1 digest the contents of all relay cells they create, and include with each relay cell the first four bytes of the current digest. Each also keeps a SHA-1 digest of data received, to verify that the received hashes are correct."

How does this work?

What I think is happening: I believe, after initializing a new SHA-1 digest, all the contents of new relay cell are XORed with the digest to produce new "digest". And the first 4 bytes from this digest is put in the digest field of the relay cell and sent. Back at Bob(OR), a similar process is repeated and the first 4 bytes of the recently computed "digest" is compared with the one received.

I understand that this helps in preventing an insider attack at modifying the cell contents as the attacker must be able to deduce the current digest state. However, I don't understand the use of calculating SHA-1 of the cell contents at Bob's end and how it helps verify that the received hashes are correct.

No.  What this means is that they concatenate all of this data and then SHA1-hash the concatenation.  There's no xor-ing of digests or anything like that.

The reason it's described this way is because many hashing APIs allow you to specify the data in a streaming fashion: you can specify the first few bytes of the message to be hashed, then you can specify a few more bytes (which will effectively be appended to the previous parts), then some more, and so on; eventually you tell the API that you are done and please return the hash.  You can think of the API as storing all of the data you passed to it, concatenating it, and hashing it all at the end.  However, for better performance, the API doesn't actually need to store all of that data: because of the way that SHA1 works internally, it can hash the data on the fly and avoid the need to store so much.  Anyway, the wording used to describe what is to be hashed is probably an artifact that mirrors the structure of the API for many SHA1 implementations.

This helps defend against man-in-the-middle attacks.  If both endpoints have the same SHA1 hash, then they must be using exactly the same data.  If a man-in-the-middle tries to modify any of this data while it is in transit, then the two endpoints will have different inputs to SHA1, so they will end up with different SHA1 digests.  Depending upon how the rest of the protocol is constructed, that may provide an opportunity to detect the man-in-the-middle.


Is a one-way function pseudorandom? For one-way function $f$ I understand that $g(x)=0^{n}\mathbin\|f(x)$ is a one- way function with respect to $2n$, where there is $n$ bits of $0$ in the beginning and the output of $f$ in the second half.

However, is this also a pseudorandom generator? My first guess was that, because it is easy to find a number that could be an output from $g$, that it isn't pseudorandom. My understanding of pseudorandom generator isn't quite clear, but it seems based on the definition of computational indistinguishability that the distribution of $g$ indistinguishable from uniform, so does that make it a PRG?

Not all one-way functions are pseudorandom. We'll show that with the help of the fact in the first part of the question (which we accept as granted, as does the question):

  If $f$ is a $n$-bit one-way function, then $g(x)=0^{n}\mathbin\|f(x)$ is a $2n$-bit one-way function.

We'll use an intuitive definition of a pseudorandom function: a function which can't be distinguished (in polynomial time) from a random function (with the same input and output sets). That sidesteps (as the question does) the more precise formalism of pseudorandom function family.

Consider this test for a $m$-bit function $h$: compute $h(x)$ for $x$ the all-zero input, and output $\mathtt{false}$ if all the left $\left\lfloor m/2\right\rfloor$ bits of the result are zero; otherwise output $\mathtt{true}$.

That test runs in polynomial time w.r.t. $n$, assuming $h$ does. When that test is applied to a function $g$ constructed as in our fact, it outputs $\mathtt{false}$ with probability $1$. When that test is applied to a random $2n$-bit function $h$, it outputs $\mathtt{false}$ with probability $2^{-n}$, since each of the $n$ bit(s) tested is uniformly random. For $n>0$, it holds $1>2^{-n}$, therefore that test distinguishes (a) any function $g$ constructed as in our fact from (b) a random function with the same input and output sets as $g$. Therefore, for $n>0$, any function $g$ constructed as in our fact is not a random function.

We now only need to hypothesize the existence of a $n$-bit one way function $f$ to have exhibited a counterexample $g$ to the assertion that all one-way functions are pseudorandom, thus proving the first sentence of this answer.

The question errs when it states

  because it is easy to find a number that could be an output from $g$, that isn't pseudorandom.

Problem with that line of thought: it holds including for a pseudo-random function $f$ that "it is easy to find a number that could be an output from $f$"; in particular, the all-zero bitstring $0^{2n}$ is such "number".

We can try and make that quantitative: the all-zero bitstring $0^{2n}$ is much more likely to occur for $g$ (probability $2^{-n}$ with some extra hypothesis) than it is for a random function $f$ with the same output set (probability $2^{-2n}$).

But it's not enough to remark that it is easy to find a number more likely to be an output from $g$ than it is to be an output for random function $f$. Problem with that alternate line of thought: as $n$ grows, it becomes exponentially unlikely that a certain number will be the output of $g$ or $f$, thus we can't build a polynomial-time distinguisher from the existence of a single such number.

Note, per comment: this answer assimilates a pseudorandom generator to a pseudorandom function (as does the question), by fixing the output width of the PRG to the width $n$ of the pseudorandom function, and using the PRG's key/seed as the input of the pseudorandom function.


Authenticated encryption and file data integrity I've got a task to provide the integrity and an authenticated encryption for files in our application. I need an assurance if my way of thinking is correct.

I can't use AES GCM, I have to stay with CBC mode.

File is logicly divided in 5MiB chunks that are going to be encrypted using same key. IV of first block is randomly generated and the IVs of next blocks are going to be extracted from previous block ciphertext.

Here, below I choosed two possible scenarios how to provide an authenticated encryption and data integrity for file:

First option

At first I encrypt first chunk of file with key and recive ciphertext.

Next I calculate hmac(key, ciphertext) and store it to verify during decryption. For each next encrypted chunk of file I create mac with below formula:

hmac(key, previous_hmac || ciphertext)

And store it to verify during decryption.

Is it proper to do it this way? Is it appropriate to store only last computed hmac in this chained hmac version alongside encrypted file, if it's not important which block was violated, for veryfication purposes?

Second option

The second solution I consider, is to calculate:

hmac(key, block_number || ciphertext)

for each chunk of file and store computed MAC alongside each ciphertext for veryfication during decryption attempt.

ciphertext is encrypted file fragment and block_number is constant bit width integer, which value is fragment offset in file.

Is this an acceptable solution? I know it allows to find violated block among unimpaired ones.

I'm not quite sure, which one of given above solutions is better. I would be thankful if someone could give me an advice which one should I chose or propose a better solution. Any links to lectures also would be appreciated. Thanks.

the IVs of next blocks are going to be extracted from previous block ciphertext.

Here assuming chunks since CBC requires IV only once per message/chunk.

IV of CBC should be unpredictable, i.e random. It is not a good idea to extract from a known source. Use randomly generated per chunk.

  First option

Enables chaining, you should also add the IV with the ciphertext. You can store the last HMAC since you can generate from the beginning. As you said this prevents the detection of chunks that have errors during transmission. This can cause re-transmit all the chunks.

  Second option

There is an attack on this case. If the same key is used for different messages, and an attacker may replace one chunk with a chunk from an old message and you cannot notice this attack if there is no validation for the message.

Better solution

Use chaining and send the intermediate HMAC results, too. This is actually combing of first and second. It enables to detection of the errored chunks and prevents the replacing attack on the second option.


What is the one way function in ECC? In the RSA algorithm it's the the integer factorisation problem, it's easy to multiply the two large primes to generate n, but given just n it's very difficult to find the constitutent primes.

In the Diffie Hellman key exchange it's the discrete logarithm problem with the same principles.

Maybe it's just because it's maths I don't entirely understand but what is the one-way-ness of ECC, you 'dot' points together repeatedly to generate your key (in essence I'm sure it's more complicated than that (if I'm wrong please correct me)). But what is it that Alice and Bob both know that allows them to generate the key, quicker than Eve can?

I hope this question makes sense, thanks in advance.

In typical ECC-based cryposystems, the one-way function is based on the Discrete Logarithm problem as in classical Diffie-Hellman key exchange; only working in a different finite group, built with the help of some Elliptic Curve over a finite field, rather than in the group obtained directly by multiplication modulo a prime.

In classical Diffie-Hellman key exchange with parameters a large prime $p$ and generator some integer $g$, the private key is some integer $x$, and the public key is $y=g^x\bmod p$. This is equivalent to multiplying $g$ by itself $x$ times in the multiplicative group $\mathbb Z_p^*$; though actually, this is done with $\mathcal O(\log(x))$ such modular multiplications, using e.g. exponentiation according to the binary representation of $x$.

In ECC, we just use a different group, and typically note the group law $+$ and the generator $G$ (uppercase is used for members of the group, while lowercase denotes integers). The private key is some integer $x$, and the public key is $Y=x\times G$. This is equivalent to adding the generator $G$ to itself $x$ times per the group law; though actually, this is done using $\mathcal O(\log(x))$ such additions in the group, using techniques as above.

In both cases, obtaining $y$ or $Y$ from $x$ is easy, but obtaining $x$ from $y$ or $Y$ is believed intractable (for proper choice of group and generator, and $x$ random in $[0,n)$ where $n$ is the order of the generator).

Elliptic Curve Diffie-Hellman works essentially identically as its classical counterpart in $\mathbb Z_p^*$, except that the Elliptic Curve group allows shorter public key and more efficient calculation for the same security level. The same transposition from $\mathbb Z_p^*$ to Elliptic Curve group works for ElGamal encryption (which becomes the basis of ECIES) and various signature algorithms including Schnorr and DSA (becoming EC-Schnorr and ECDSA).


Does an anonymous signature hide the sender's identity from the receiver? Does an anonymous signature hide the sender's identity from the receiver, or simply just hide the sender's identity from an eavesdropper or third party?

It is perhaps more complicated.

Signer anonymity for anonymous signatures means anyone who has the signature but not the message (or does not know enough about the message) cannot reveal the identity of the signer.

Thus it really depends on, in your model, what the receiver or eavesdropper knows. For example, if one sends the signature and the message (in plaintext) together, then even the eavesdropper can know the signer's identity. For receivers, often they are supposed to verify a signature, so they know the identity of the signer. However, if your receivers are not verifiers (e.g. they just receive and store the signatures), then they may not need to know the messages, and if the messages are hidden from them, then they don't know the identity of the signer.


How SAM modules secure transactions? As you know SAM Modules are used mainly in the electronic payment industry. Due to the low security of key storing in general storage devices or MCUs, Manufacturers used SAM modules for secure storing and transfering data between processor and the end point card reader. In some (e.g. SAM AV2 series from NXP) both connection between MCU-SAM and MCU-Reader can be secured. But the thing I can't understand is that the MCU and the SAM still must present their keys to each other for authenticating and because of this still must the key be stored in the MCU and how do they introduce themselves to each other securely? How do the SAM module and the reader secure connections?
EDIT: Let me explain more:My question is about procedure of identifying between MCU-SAM & SAM_Reader,Are we need to store a key(derived key or Master one) in the MCU?if yes is it safe to storing it in general MCU's memory?if not how MCU & SAM authenticate each other without key ?is SAM's internal MCU programmable?whats procedure of authenticating between SAM-Reader & Reader-Card?

In the Smart Card industry, it is often used a technique called diversification: individual Smart Cards get a serial number $S$, and a device-unique secret key $K_S$ computed from a Master Key $K$, and $S$, using a (typically: non-entropy-stretching) Key Derivation Function. For example, $K_S=\operatorname{AES-ENC}(K,S)$ where the first parameter of $\operatorname{AES-ENC}$ is the key; or perhaps, $K_S=\operatorname{HMAC-SHA-256}(K,S)$. Injection of $K_S$ in Smart Cards, and injection of $K$ in SAMs, is done in secure conditions (production line of a card manufacturer).

A SAM contains $K$, thus is able to internally recompute $K_S$ of any Smart Card that it must interact with, from its (alleged) serial number $S$, which is usually freely readable from the Smart Card. The SAM and the Smart Card (if it is genuine) will thus share the secret key $K_S$, and then there are plethora of protocols to perform mutual authentication and establish a secure link.


Why is the polynomial of an LFSR called so? As far as I understand, the "polynomial" of the LFSR tells us the positions of the register where taps are situated.

However, the natural way to look at the positions would be to think of them as $x_1, x_2, x_3,\cdots$. But we instead identify them as powers of something and call them $x, x^2, x^3, \cdots$

My question is, what are they powers of? And why do we add a 1 to the polynomial?

The polynomial $X^i$ is a delay operator, so formally $X^i(s_t)=s_{t-i}$.

It's also a linear operator so $X^i(a s_t)=a s_{t-i}$.

Let's apply this to the following simple LFSR in Fibonacci configuration

At each clock cycle, a new state $s_t$ is computed from delayed states $s_{t-1}$ and $s_{t-3}$, as $s_t=s_{t-1}+s_{t-3}$. That recurrence can be rewritten as $s_{t-3}+s_{t-1}-s_t=0$, and represented as the polynomial $X^3+X-1=0$ (the $1$ is a shorthand for $X^0$).  In binary, both $+$ and $-$ are eXlusive-OR $\oplus$ and we write the polynomial modulo 2, as $X^3+X+1.$

Moreover, not only is there a one to one correspondence between recurrences (equivalently LFSRs) and polynomials, but the roots of the polynomial feature in the solutions, i.e., the sequence generated.


Are there any online, single pass, AE with associated data auth? AE comparison summarizes features of nine AE ciphers and none of them combine features online, one pass, AD auth (see table below). Are out there such ciphers or such combination was proved to be unsecure?

The comparison table is old. OCB has been updated twice since it was first published, supporting associated data since the Asiacrypt 2004 paper. The latest version is OCB3 (but Rogaway suggests it should be called OCB) from a FSE 2011 paper. See http://web.cs.ucdavis.edu/~rogaway/ocb/ocb-faq.htm#versions

In summary, OCB (versions OCB2 and later) supports AEAD and has supported it since 2004.


Extracting Zip using Only the AES Key I have set myself a little challenge, to see if I can decrypt my own text file from with a ZIP file...

The AES Key from my encrypted ZIP is all I have    managed to extract,
how do I decrypt the zip using this AES Key...

It asks for a password, so how am I supposed to bypass that and only decrypt using the AES Key.

The details are explained in the WinZip documentation. It describes two encryption formats, termed AE-1 and AE-2. The format itself supports 128, 192, and 256-bit keys for AES in CTR mode, using PBKDF2-HMAC-SHA1 with 1000 iterations for key derivation. The salt is random and is half the size of the key. Help with decrypting data using a library is given elsewhere on the site.

You can verify that the decryption is correct by checking the password verification value:

  This two-byte value is produced as part of the process that derives the encryption and decryption keys from the password. When encrypting, a verification value is derived from the encryption password and stored with the encrypted file. Before decrypting, a verification value can be derived from the decryption password and compared to the value stored with the file, serving as a quick check that will detect most, but not all, incorrect passwords. There is a 1 in 65,536 chance that an incorrect password will yield a matching verification value; therefore, a matching verification value cannot be absolutely relied on to indicate a correct password.

The key is derived from the password using PBKDF2, explained as follows:

  Key derivation, as used by AE-1 and AE-2 and as implemented in Dr. Gladman's library, is done according to the PBKDF2 algorithm, which is described in the RFC2898 guidelines. An iteration count of 1000 is used. An appropriate number of bits from the resulting hash value are used to compose three output values: an encryption key, an authentication key, and a password verification value. The first n bits become the encryption key, the next m bits become the authentication key, and the last 16 bits (two bytes) become the password verification value.

General useful information on the PKZip format is also available here.


Prime order elliptic curve groups: Generators and the reason choice As far as I understand, the elliptic curve group based on BLS12-381 is prime order and cyclic. Thus, any group element could be used to generate all the elements of the group.

Why is a point explicitly hard-coded as the generator of the group
here and here?
If any group element serves as a generator of the group, what is the specialty of the chosen points in the above libraries? And how would one compute that special point?

Yes, by Lagrange's Theorem in the group theory, the order of any element must divide the order of the group. Therefore, except for the identity element, which has order 1, all other points can be a generator.
If you define a protocol, you need a common agreement and the generator is a part of this. If you don't include it in the specifications you need to agree for every user. Instead of this, one point is assigned as the basepoint.
Normally the base points are selected in the manner of nothing-up-my-sleeve-numbers to show that there are no backdoors designed. The choice reason is given as

The generators of G1 and G2 are computed by finding the lexicographically smallest valid x-coordinate, and its lexicographically smallest y-coordinate and scaling it by the cofactor such that the result is not the point at infinity.

BLS12-381 is used for digital signatures and zero-knowledge proofs in Zcash, Ethereum 2.0, Skale, Algorand, Dfinity, Chia, and more.


modulo operations in crypto algorithms Am not a mathematician.

Every crypto specification I see uses the modulo operation. For example RSA -

If $e$ is the public key and $m$ is the plaintext with a modulus $n$ - the cipher text is $c = m^{e} \bmod n$

Why is this $\bmod\ n$ there? By definition isn't the modulo operation introduces an uncertainty? I mean  $3 \bmod 7 = 10 \bmod 7 = 3$.

Is it the idea to limit the result to a group? Why is there no uncertainty about the result?

Is it the idea to limit the result to a group?

Yes. The advantage to doing so is that we have multiplicative inverses (well, for anything relatively prime to $n$) and can therefore decrypt. It also keeps ciphertexts relatively small.

Why is there no uncertainty about the result?

There would be, except we require require plaintexts to be smaller than the modulous (i.e., part of the group). In your example, we wouldn't allow 10 to be a plaintext, because 10 is greater than 7, the modulous.

So how do you encrypt long messages? Normally, the only thing you encrypt using RSA is a symmetric key, and then encrypt your actual message using the symmetric key. Since symmetric keys are significantly shorter than RSA moduli, this isn't an issue.

We would also like to sign long messages with RSA. Therefore we typically hash the message to a digest that's shorter than the modulous, and then sign the digest. This also improves performance and stops attackers from exploiting the fact that RSA encryption is a homomorphism to forge signatures.


What is the relationship between attribute based encryption (ABE) and access control? So if possible could someone tell me or at least recommend a book.

ABE provides a secure and automatic way to enforce access control, but access control may not involve encryption.

In the ABE setting, the resources (that one wants to access) are encrypted by a "controller" and then the ciphertexts are made public and each user is granted a key corresponding to its specific access right. Then, the controller doesn't need to interact with the users to manage their access, because such access control enforcement can be guaranteed by the security of the underlying encryption scheme.

However, in a general access control setting, a "controller" (e.g., an OS or an application) may need to interact with the user (e.g., via an OS access control mechanism or a login system) and grant it the correct access right each time the user wants to access some resources. The resources here may not be encrypted, but are only available to the "controller".


Attacks against El Gamal private key El Gamal encryption involves picking $(p,g,b)$ which is our public key. We compute $b=a^x$ $mod$ $p$. Here, $x$ is the private key which we don't know.

What are some efficient and strong algorithms today used to finding this $x$?

I am currently dealing with numbers such as $b=42-60$ digits long and $p=30-50$. So $b$ is anywhere between 42 and 60 digits.

Does anyone know of any program and some attacks to finding this $x$ using our given information?

Being new to cryptography is one thing, but you are supposed to do some research on your own before asking questions here (see How to Ask), and D.W. gave you the right directions already.

But since you wanted names and links:

The first stop should be discrete logarithm on Wikipedia, and it lists several algorithms on this topic.
As a beginner, start with Babystep-Giantstep and Pohlig-Hellman.
Your next stop should be Index Calculus.
Additionally, there are algorithms based on the NFS, e.g. described in Gordon's paper Discrete Logarithms in GF(p) Using the Number Field Sieve. Current records modulo primes employ this technique.


How do you derive the lambda and beta values for endomorphism on the secp256k1 curve? Note: This question was reposted from Bitcoin Stack Exchange, where it received alike answers.

You can see a little background about this on this bitcointalk post by the late Hal Finney.

$\beta$ and $\lambda$ are the values on the secp256k1 curve such that:
$$\begin{align}
\lambda^3 &= 1 \mod N \\
\beta^3 &= 1 \mod P \\
\end{align}$$

As seen here, in hex, $N$ and $P$ are:
$$\begin{align}
N &= \mathtt{FFFFFFFF\ FFFFFFFF\ FFFFFFFF\ FFFFFFFE\ BAAEDCE6\ AF48A03B\ BFD25E8C\ D0364141} \\
P &= \mathtt{FFFFFFFF\ FFFFFFFF\ FFFFFFFF\ FFFFFFFF\ FFFFFFFF\ FFFFFFFF\ FFFFFFFE\ FFFFFC2F} \\
\end{align}$$

The actual values of lambda and beta are easily verifiable and are:
$$\begin{align}
\lambda &= \mathtt{5363ad4c\ c05c30e0\ a5261c02\ 8812645a\ 122e22ea\ 20816678\ df02967c\ 1b23bd72} \\
\beta &= \mathtt{7ae96a2b\ 657c0710\ 6e64479e\ ac3434e9\ 9cf04975\ 12f58995\ c1396c28\ 719501ee} \\
\end{align}$$

The question for me is, how do you derive this? Can someone show me step-by-step how you can figure out these values?

Given that $N$ and $P$ are prime, one obvious way to do this is to select a random value $g$ from $[1, N-1]$, and compute $g^{(N-1)/3} \bmod N$; assuming that $N \equiv 1 \pmod{3}$, this resulting value will either be 1, the displayed value of $\lambda$, or $N-\lambda-1$ (with equal probabilities of each).  If $N \not\equiv 1 \pmod{3}$, then the only modular cube root of 1 will be 1.

And, to compute $\beta$, you do the same with $P$.


Will the contents of a password protected Zip 2.0 file be safe for a week I will need to distribute a file to people for a challenge and I need them to open the file at the same time. The file will be provided a couple of days before the challenge. For maximum compatibility (so no need for 3rd party software, just OS supplied tools) I was thinking of using a password protected Zip 2.0 file.

After some reading I think this will be OK, but I'm not sure. I can't seem to find information on my specific use case (the file only needs to be secret for a short amount of time).

There will be only one file and I will use a 5 word diceware password to make it easy for entering the password while keeping quite a bit of enthropy.

Will this keep my file secure for about a week, assuming people don't have access to big computing clusters?

I just stumbled on http://www.tomshardware.com/reviews/password-recovery-gpu,2945-5.html. Although it's a bit old, it does give me some perspective. It mentions ~30 million password tries per second on a Zip 2.0 file. So if someone had a that can perform 10 times as much tries per second, they would need (6^5)^5 / 300 000 000 = ~94767626766 seconds = ~3000 years. I don't think anyone will be spending time and money on a 200000 node cluster to bring this down to ~5 days.

@SEJPM, thanks for your comment that gave further thought to my own question. I was wondering, how did you come up with 2^44.8? If I calculate (6^5)^5 / 7 / 24 / 3600 I get 2^45.4. Is there a something I'm overlooking?


Easily reversible hash functions as a method of data transmission I've been looking through the literature because I want to see if anyone has implemented this idea I have. I know data compression algorithms work by removing redundancy in data. I was wondering though if this scheme I have would work.

Ordinarily the idea of a hashing function $H$ is designed so that $H(x)$ (where $x$ is the message) is easy to compute in the forward direction, but difficult to compute in the reverse direction (computing $H^{-1}(x)$ is intractable). But I also notice another thing about $H$. In practice the length of $H(x)$ is can be as large as 512 bits (I'm referring to the SHA-512 hash). This means that $H$ can map $2^{512} \approx 1.34 \times 10^{154}$ hashes to theoretically an infinite number of pieces of data. It's just that in practice the message space of all possible messages are not necessarily messages that have any meaning to humans. The number of total human readable messages may be on the order of say $2^{520}$ (meaning the total number of unique messages in the entire history of mankind).

So now let us suppose we have a hashing function $h$ which is easy to compute in both directions. We could compress our large data file $D$ into a short hash $h(D)$ that maps to $D$ and several other unintelligible "messages." So now to transmit $D$ all we have to do is to transmit $h(D)$ (which is short) and then the receiver would reverse $h(D)$ until they find a possible intelligent message and they could reconstruct $D$. If such a thing could work it would be possible to compress large amounts of data into short messages.

Does anyone know if such a thing has been done before?

The hashing function you describe would be a magical compression method. Well, I'm sorry to burst this on you, but magic isn't real. Magical compression that can take arbitrary data and condense it to a very small size does not exist. In fact, it's easy to prove mathematically that there is no compression method that reduces the size of all data, by the cardinality argument you give.

Compression that reduces the size of common data certainly does exist. But it works by recognizing certain kinds of patterns. Cryptography doesn't help with recognizing patterns — if anything, cryptography is all about hiding patterns.

Compression that can take data among a finite set and condense it to a fixed size is called naming or indexing. Cryptography doesn't help with that either.


Desirable S-box properties What desirable properties should an S-box have?

My current standard selection process is to just pick them at random and verify that they fit the following criteria:

The probability that any random two bits $S[a]_b$ and $S[c]_d$ are equal (for any random $a$, $b$, $c$ and $d$) is 50%.
The probability that any random two bits $S[a]_n$ and $a_n$ are equal (for any random $a$ and $n$) is 50%.
No entries exist such that $S[a] = a$
No entries exist such that $S[a] = \bar{a}$

Are there any other important properties that need to be applied?

Edit My reasons for asking are that I wish to combine this S-Box design with a CBC mode cipher as discussed on this question.

The following information about the DES S-Box might be useful (taken from here):

DES Design Criteria

there were 12 criterion used, resulting in about 1000 possible S-Boxes, of which the implementers chose 8

these criteria are CLASSIFIED SECRET

however, some of them have become known

The following are design criterion:
R1: Each row of an S-box is a permutation of 0 to 15
R2: No S-Box is a linear of affine function of the input
R3: Changing one input bit to an S-box results in changing at least two output bits
R4: S(x) and S(x+001100) must differ in at least 2 bits
The following are said to be caused by design criteria
R5: S(x) [[pi]] S(x+11ef 00) for any choice of e and f
R6: The S-boxes were chosen to minimize the difference between the number of 1's and 0's in any S-box output when any single input is held constant
R7: The S-boxes chosen require significantly more minterms than a random choice would require

For Rijndael, things were different as the S-Box in Rijndael had to meet certain requirements mathematically and cryptanalytically


Is it OK to use a data-encryption key for key wrapping, too? Our industry (area of cheap networked devices) has a standard that defines the usage of keys for both authentication and encryption using EAX mode of AES. This standard does not define key management, and someone wants to change this key material in devices using the RFC 3394 key wrap algorithm. For that they want to use these very same encryption/authentication keys as key-wrapping keys to receive new keys (no separate/master key-wrap-key).

I assume it is a bad idea, but I could not find a clear prohibition for this, and here is the best I could find on this site. Can anyone help with a better reference/book? Or is that safe after all?

That's a really bad idea. The general rule is that a symmetric key can either be used for key wrapping or for data encryption, but never for both.

I assume that the keys already in the devices are currently used for processing data. If such keys are now also used for key wrapping, an attacker may abuse the existing protocols and processing facilities and use the device as an oracle to unwrap the new key packages you are about to send. Whether that is really a problem depends on how the key are really used, but in general it is very dodgy and it should be avoided in the first place. If that's not possible, you need to carry out some serious analysis to verify that cannot happen.

Note that the same problem exist even if you derive the actual wrapping key from the existing key material.

The rule is fairly obvious and well known. If you need a reference, you can rely on Clulol's paper "On the security of PKCS#11", Section 2.2.


Does "double RC4" exhibit the same weaknesses as standard RC4? I know that RC4 is weak.  However, I don't know if two RC4 streams XORed with each other can be attacked in the same way that one can, especially if $n$ bytes are dropped.

Assume keys and IVs are independent and random.

(This is purely theoretical, I don't plan on using it in practice).

It can be attacked in the same way, but not as efficiently.

The RC4 "NOMORE" attack (pdf), for example, uses both Fluhrer-McGrew biases, which are biases towards certain pairs of values in certain positions, and Mantin's "ABSAB biases", which are repetitions of bigrams. Both of those biases will survive a XOR of two keystreams, but will be less frequent.

A rough estimate would be that you need quadratically as much ciphertext, so that you can attack first one layer and then the next. That would imply  >$2^{55}$ captures instead of the ~$2^{28}$ in the attack demonstration, which would likely be too much to use in practice. However, depending on whether or not the two keystreams are aligned, that could be an overestimate or an underestimate.

It seems possible that a XOR of two independent RC4 keystreams would be too strong to practically break in such a manner, even if it was significantly below the strength implied by key size. However, distinguishing attacks require less data and are more likely to be feasible. (The attack in question decrypts cookies or other suitable data.)


"open-key model" attacks, why would one be concerned? In a paper on a Feistel network, I found the line

  we have made no effort to guard against attacks in the open-key model

and then I found this paper at iarc.org on the subject.  I found only a single reference to this as an actual problem with RC4 and related keys in WEP implementations.  If the open key model is an issue with related keys, why would the authors of a paper relating to a Feistel network make the statement regarding the "open-key model".  Particularly, due to all of the work with Feistel networks and their proven security for a high round counts, I just don't understand why they would need to include this disclaimer.  Is there something that I am missing?

It is not uncommon for a paper to state that the proposed design was not designed to protect against related key attacks. One reason for this is the over-powered nature of the attack against confidentiality: If the adversary already possesses the key, and can encrypt and decrypt at will, then one has to wonder how/why the adversary even stands to benefit from running an attack.

The open key model appears to go a step further, and assume that the adversary may have even chosen the key in question.

As far as confidentiality goes, there appears to be little point to defending against a known/chosen key attack. Doing so would likely require a more elaborate design, or at least more rounds, which will degrade performance in the "regular" use case to protect against an edge case situation that seems unlikely to occur in practice.

As to why a paper would explicitly mention such a thing: It is better to see "we made no attempt to protect against this class of attack" as opposed to not even mentioning the existence of the class of attacks. If the authors decline to mention related key attacks, it could be interpreted that they were not aware of them, as opposed to did not care to defend against them.

On the opposite side, there is one compelling reason to try and defend against known/chosen key attacks: If the cipher is to be used as a component of a hashing function, known/chosen key attacks become a relevant threat model. For example, this is mentioned briefly on page 9 of the proposal for simon/speck.


Is padding of the digest needed in SHA256 with RSA-2048 scheme? For a signing scheme involving generating a $256$ bit digest using SHA256 followed by RSA with $2048$ bit modulus, the signature would always be 256 bit without padding even though signatures of up to $2048$ bits are allowed in the RSA scheme that follows.
As such, is there a need to pad the $256$ bit digest to improve security?

For a signing scheme involving generating a 256-bit digest using SHA-256 followed by RSA with 2048-bit modulus, the signature would always be 256-bit without padding..

That assertion is wrong. For every RSA signature scheme, the signature is always at least as wide as the modulus (or next to that; there are tricks to reduce it by a few bits). Much shorter signatures are not verifiable.

  Is there a need to pad the 256-bit digest to improve security?

If the question asks whether a more elaborate padding scheme than signing message $M$ as $(\operatorname{SHA-256}(M))^d\bmod N$ is needed: Yes. Otherwise, an existential forgery might be possible per a variant of the Desmedt and Odlyzko attack; it is feasible at least for a 200-bit hash.

Common RSA signature schemes:

RSASSA-PSS of PKCS#1v2.2. It is a randomized RSA signature scheme with appendix (that is, with the signature appended to the unmodified message). It has a strong security reduction to the RSA problem (finding $M$ from $M^e\bmod N$ for random $M$). It remains secure  (assuming slightly stronger hypothesis) if it's randomness source is stuck.
ISO/IEC 9796-2 scheme 2. It is a randomized RSA signature scheme with message recovery (that is, with some or all of the message conveyed in the signature itself, saving bandwidth). It has a strong security reduction to the RSA problem. It remains secure (assuming slightly stronger hypothesis) if it's randomness source is stuck.
ISO/IEC 9796-2 scheme 3. It is a deterministic RSA signature scheme with message recovery, equivalent to scheme 2 above with no randomness, and maximum ability to embed data in the signature (size of the modulus, minus hash width and 2 bytes). It inherits scheme 2's security reduction.
RSASSA-PKCS1-v1_5 of PKCS#1v2.2. It is a deterministic signature scheme with appendix. There is no known attack against this scheme, but no security reduction.
ISO/IEC 9796-2 scheme 1, a deterministic RSA signature scheme with message recovery. There is an existential forgery against this scheme when the adversary can obtain signature of chosen messages, thus the (fully compatible) scheme 3 should be used in all new systems.


What is the padding scheme for the original Tiger hash? The specification doesn't seem to indicate how to pad messages to the requisite 512-bit boundary.

What is the padding scheme for the original Tiger hash?

For drop-in compatibility, we adopt the outer structure of the MD4 family: the message is padded by a single '1' bit followed by a string of '0's and finally the message length as a 64-bit word. The result is divided into n 512-bit blocks.

http://www.cs.technion.ac.il/~biham/Reports/Tiger/tiger/node2.html

I assume this 64 bit word is little endian, like the rest of Tiger and like the MD4 padding.

For reference the RFC1320 which describes MD4 says:

  a sequence of
     bytes can be interpreted as a sequence of 32-bit words, where each
     consecutive group of four bytes is interpreted as a word with the
     low-order (least significant) byte given first.

  [...]

  Step 1. Append Padding Bits

  The message is "padded" (extended) so that its length (in bits) is
     congruent to 448, modulo 512. That is, the message is extended so
     that it is just 64 bits shy of being a multiple of 512 bits long.
     Padding is always performed, even if the length of the message is
     already congruent to 448, modulo 512.

  Padding is performed as follows: a single "1" bit is appended to the
     message, and then "0" bits are appended so that the length in bits of
     the padded message becomes congruent to 448, modulo 512. In all, at
     least one bit and at most 512 bits are appended.

  Step 2. Append Length

  A 64-bit representation of b (the length of the message before the
     padding bits were added) is appended to the result of the previous
     step. In the unlikely event that b is greater than 2^64, then only
     the low-order 64 bits of b are used. (These bits are appended as two
     32-bit words and appended low-order word first in accordance with the
     previous conventions.)

  At this point the resulting message (after padding with bits and with
     b) has a length that is an exact multiple of 512 bits. Equivalently,
     this message has a length that is an exact multiple of 16 (32-bit)
     words. Let M[0 ... N-1] denote the words of the resulting message,
     where N is a multiple of 16.


(Uniformly) Random Value when an element is picked with $\frac{1}{p-1}- \frac{1}{(p-1)^2}\ $ probability Let's $\mathbb{F}_p$ be a finite field where $p$ is a large prime number(e.g. 256-bit)

I know if the probability that an element picked from the field is $\frac{1}{p-1}$ we say the element is picked uniformly at random.

Question: In security context can we say the element is uniformly at random even if its probability is $\frac{1}{p-1}- \frac{1}{(p-1)^2}\ $?

$\mathbb{F}_p$ actually has p elements. Hence, an element would be picked uniformly at random if every element was chosen with probability $1/p$. Already if one element is chosen with probability $\frac{1}{p-1}$ this is not a uniform distribution anymore. Depending on the size of $p$ you can argue that the distribution is statistically indistinguishable from a uniformly random one.


Formal Verification of DHKE protocol using ProVerif I am new to ProVerif and trying to verify a simple DHKE protocol. The attacker is assumed as passive. The specifications are:

The attacker cannot obtains the mutual key.
Both participants obtain the same key.

This is what I have created.

type G.                             (* The generator *)
type exponent.

free c, sc: channel.
free c02, c12: channel [private].
const g: G [data].
free msg, sameKey: bitstring [private].

fun exp(G, exponent): G.
fun enc(bitstring, G): bitstring.
reduc forall m: bitstring, k: G; dec(enc(m,k),k) = m.

equation forall x: exponent, y: exponent; exp(exp(g,x),y) = exp(exp(g,y),x).

set attacker = passive.
query attacker(msg).
query attacker(sameKey).

let par1 =
    new a1: exponent;
    out(c, exp(g,a1));      (* g^a1 *)
    in(c, v2: G);
    let key1 = exp(v2,a1) in
        out(c, enc(msg,key1));
        out(c02, key1).

let par2 =
    new a2: exponent;
    out(c, exp(g,a2));      (* g^a2 *)
    in(c, v1: G);
    let key2 = exp(v1,a2) in
        out(c12, key2).

let px3 =
    in(c02, k1: bitstring);
    in(c12, k2: bitstring);
    if k1 = k2 then
        0
    else
        out(sc, sameKey).

process
    par1 | par2 | px3

My questions:

Is it enough to verify the first specification?
Logically, the attacker cannot obtain the value of sameKey if the mutual key is identical. But, proverif returns the following output along with some traces. Are there any mistakes in this approach?

The proverif output:

RESULT not attacker(sameKey[]) cannot be proved.

[Update] I managed to solve this problem by using different channel for P1 and P2, denoted by $\verb|c01|$ and $\verb|c10|$ respectively.

I think it's because par1 and par2 start "out".
As you know, a client will start to send message to the server first. And after do thart, the server will receive the message.
It seems that it's probably possible to fine if your code in one of them code is fixed like below.

let par1 = out(..);
                  in(..);

let par2 = in(..);
                  out(..);


Get points of an Elliptic Curve defined over a Finite Field on Twisted Edwards Extended Coordinates I'm working on a crypto library, and I need to perform some tests for the implementation of:

Point Addition.
Point Subtraction.
Point Doubling.
Scalar Mul Point.

The operations are performed on Twisted Edwards Extended Coordinates so (X, Y, Z, T).

The problem is that apart of the Identity point which is: (0,1,1,0), It's being hard for me to get other points to test the operations.

So being the Eq of the curve: -x²+y²=1-$\frac{86649}{86650}$x²y² over the Finite Field modulo P = 2^252 + 27742317777372353535851937790883648493.

  (So a = -1 and d = 86649/86650 (mod P).

My idea was to pick random X values and get it's corresponding Y values. Then find T is trivial. But the problem is that I end up with things like:

For whatever X,

Y = +- (sqrt(-x^2 -1)) / (sqrt(d*x^2 -1))

My question is if this approach of getting random points over the curve is correct.
And in that case:
Since I cannot get decimal values over a Finite Field, how should I treat the sqrts?

  With division we know that a/b = a * inverse_mod(b, P).

But what about the SQRT operator? How can I deal with it?

You will have a weistrass equation of the form:

$Y^2 = aX^3..$

Where x is the only unknown variable on the right hand side. Insert a random X value in to the right hand side. Then evaluate the right hand side. This would need to be done modulo whatever prime you are using.

You will end up with an equation of the form:

$Y^2 = K$ where K is your evaluated right hand side.

This number K is either a Quadratic Residue or it is not. You can check this using the Legendre symbol.

If it is, then you can perform the sqrt of K modulo your prime to get the value for $+Y, -Y$

How you do the sqrt depends on what algorithm you decide to use, you can use Tonelli-Shanks which is a more generic square root algorithm


Lattice-based cryptography prone to side channel attack? Is lattice-based cryptography still prone to side channel attacks? What are some mitigation strategies, if any?

my understanding is that Supersingular isogeny Diffie-Hellman (SIDH) is fully protected against timing and cache attacks as all operations on secret data run in constant time. That was my own experience.


How can you produce visual cryptography? I would like to be able to "code" images such as the one seen here on Wikipedia.

Is this generally produced with software, or does this require complex programming? Ideally, I would love to be able to batch encrypt images based on settings I pre-defined.

Actually, it's fairly simple:

Generate an image with random pixelation; that is, each pixel is either black or white with probability 1/2.  We'll call this image 1.
Exclusive-or image 1 with the target to generate image 2; so that a pixel image 2 will be white if the pixels in image 1 and the target are the same (both with or both black), and black if they differ.

Now, you combine the two images by overlaying them; what this effectively does is an AND function, in the sense that a pixel in the combined image will be white only if both image 1 and image 2 are white.

Now, if we have an area of pixels in the target image which are black, then when we combine those images, that area will be black as well.  That's because, of any pixel in that area, either the pixel in image 1 will be black, or the pixel in image 2 will be black.

In contrast, if we have an area of pixels in the target image which are white, then when we combine those images, that area will be gray (likely consist of half white and half black pixels).  Any pixels that happen to be black in image 1 will, of course, be black; any pixels that happen to be white in image 1 will also be white in image 2; as image 1 was random, this results in a gray area.


Is encrypting a public key with a symmetric key safe? Assume the sender wants to share their ephemeral/long-term public key with intended receiver only and both share symmetric key.

Is it secure to encrypt the (full/partial) public key (of RSA, ECC) with the shared symmetric key?

Is there any chance of finding symmetric key from encrypted public key?

If not why?

Is there any chance of finding symmetric key from encrypted public key?

The answer is no, assuming the symmetric key has sufficient entropy and a secure encryption algorithm and mode is used correctly.

Modern ciphers like AES with proper secret keys are not vulnerable to known plaintext attacks.

Why?

This has been answered in an earlier question: Why is AES resistant to known-plaintext attacks?

However:

  Is it ok to encrypt (full/partial) public key (of RSA, ECC) with shared symmetric key?

Definitely it is OK, but this is operation that is not often needed, though. In hybrid cryptosystems, it is common that the long-term secrets are private keys and public keys and those are used to establish per session symmetric keys. Doing it the other way around (having symmetric key and transporting public key) is somewhat less common.

Also, most usually public keys need some sort of authenticity or integrity protection, it rarely makes sense to try to encrypt them (confidentiality protection).

  symmetric key (password)

This sounds suspect. It is rare for a password to contain sufficient entropy for this purpose. If a password is weak or it is used improperly to create a symmetric key, then it is possible that an attacker can indeed find the secret key (e.g. via a form of dictionary attack).

Do the peers share symmetric key or password?

  want to share his ephemeral/long-term public key with intended receiver only

This is usually not possible. If the public key is ever used, somebody eavesdropping the communication will learn the public key. It is not possible to have only intended recipient knowing the public key.


Which cipher to use with openssl for shortest output? I'd like to encrypt my 12-24 words seed for my bitcoin wallet with openssl command line tool to be able to have it with me on paper without the risk that somebody could use it

Which cipher should I use for the shortest output in base64? The seed consists of just a-z characters and is case insensitive

Main requirements are short length and decodable on any computer with openssl installed - nothing exotic

It could be better to use PGP, which has been designed to encrypt files.

Only OpenSSL v1.1 latest versions contain a command line switch to choose the number of iterations (the work factor) to configure the password hash when using password based encryption (PBE). This is something that is required, otherwise the password must be of about the same strength as your original password. That would of course not help you any further.

As you require just normal confidentiality you could just use AES-CTR mode for PBE. Then there is just 16 bytes of overhead for the salt and header (you could remove the first 8 bytes of magic and replace it back afterwards as optimization). So then the ciphertext would be only 8 bytes more than the password. Base 64 - you can forgo the base 64 padding characters - will just expand this by one third.

However, the password consists solely of lowercase characters. So each character only needs to take 5 bits (2^5 = 32 which is greater than the 26 values required). So that way you can save 3 bits per character.

So the minimum size of the maximum value would then be 24 * 5 / 8 = 15, 15 + 8 = 23 bytes, expanded to (24 / 3) * 4 = 32 base 64 characters.

But don't forget to write down or remember the iteration count and - of course - the algorithm itself.

It might be easier to use e.g. an IronKey to store your passwords on a USB stick (or two), which would cost you about 50 Euro per piece. Remember that flash may not last forever though, it can leak state over time.


Are there secure stream ciphers that cannot be parallelized? Are there any stream ciphers (or a deterministic random number generators, that should work as well I guess?) that cannot be parallelized?
For example, if I seed it with a specific value, and then "run" it for a year, generating more and more bits, and finally get a bitstream off it, then that bitstream will be impossible (unless somebody "breaks" the cipher) to get a hold on without doing all that work synchronously and requiring at least a similar amount of time. (So that nobody will be able to get 100x cores to do all that work in 100x shorter time. They could always get a faster processor, or build a specialized chip or something, but it would still run the calculation single-threaded, synchronously still requiring a lot of time to get to the needed bitstream from the initial seed value.)
Do algorithms with similar properties exist? Or can everything be parallelized?

As Thomas notes, most stream ciphers cannot be parallelized (in the sense that generating a single keystream would be significantly faster with multiple processors than with one) or randomly accessed (in the sense that the mimimum time needed to compute the $k$-th bit of the keystream would be sub-linear in $k$).

Examples of stream ciphers that cannot be parallelized include:

As far as I know, ther's no known way to parallelize the RC4 stream cipher in any useful way.
Block ciphers used in OFB mode are not parallelizable, except insofar as the underlying block cipher itself can be parallelized.  I suspect it might even be possible to prove this, given suitable indistinguishability assumptions on the block cipher, although I'm not personally aware of such a proof.

Nonetheless, some stream ciphers do exist which can be parallelized or even randomly accessed.  Particularly notable among these is the CTR mode of operation, which turns a block cipher into a randomly accessible (and thus also fully parallelizable) stream cipher.

Some modern stream ciphers are also designed to exhibit at least a limited degree of parallelizability in hardware.  For example, the Trivium stream cipher is designed so that it can be used to generate anywhere from one up to 64 bits in parallel.  However, any reasonable software implementation of Trivium would already exploit this parallellism to a high degree by operating on 32- or 64-bit blocks of data, so, for all practical purposes, Trivium in software is not (further) parallelizable.

More generally, eseentially all synchronous stream ciphers (including all those mentioned above) may be written in the following form:

$$\begin{aligned}
x_0 &= i \\
x_n &= f(x_{n-1}) &\forall n \in \{1,2,3,\dotsc\} \\
o_n &= g(x_n) &\forall n \in \{1,2,3,\dotsc\}
\end{aligned}$$

where

$i$ is the initial state of the cipher (derived based on, and possibly including, the key as well as any IVs, tweaks, etc.),
$x_n$ denotes the internal state of the cipher at step $n$,
$o_n$ is the keystream output at step $n$,
$f$ is the function that updates the internal state at each step, and
$g$ is the function used to map the internal state into the output.

For most stream ciphers, which are not efficiently parallelizable, the cryptographic strength comes from the internal update function $f$, while the output function $g$ is fairly trivial (typically just extracting some part of the internal state).
On the other hand, to allow random access into the keystream (as with CTR mode), the update function $f$ must be trivial (for CTR mode, just incrementing a counter by one), so that $x_n$ can be quickly computed from $x_0$ for any $n$, while the cryptographic strength must come solely from the function $g$ (which, for CTR mode, is the underlying block cipher).

One reason why the random access type of stream cipher design is not more widely used is that relying on $g$ instead of $f$ for strength puts much harder demands on it: the fact that $f$ is iteratively applied to its own output allows its strength to build up gradually over many steps, whereas any security coming from $g$ must come from just one single application of it.  Most of the update functions $f$ used in traditional stream ciphers like RC4 would be hopelessly insecure if used as $g$ with a trivial $f$.

(Also, if you do manage to design a function that can be used securely as $g$ with a trivial $f$, what you have is basically a secure block cipher or something very close to one.  So, in that sense, the CTR mode construction is the generic random access stream cipher, with any other random access stream cipher being essentially the same thing with just cosmetic differences.)

However, I should note that there's another kind of parallelism which may be more relevant: if an attacker wants to crack the cipher by brute force, he will typically do so by generating multiple keystreams from different keys and seeing which of them yields a meaningful decryption.  In that case, even if the generation of a single keystream is not parallelizable, the attacker can just take multiple processors (or, say, cores in a GPGPU) and set each of them to generate a different keystream.

This kind of parallelism is quite hard to avoid, since, fundamentally, the generation of many independent keystreams is an embarrassingly parallel task regardless of how each individual keystream is generated.  One way to try to slow down such attacks is to make the keystream generation (or other computation) require a lot of memory, on the basis that, with current technology, it's a lot cheaper to build a lot of simple parallel processors than to provide each of them with a large amount of memory to work with.

One example of such a design is the scrypt key derivation function, which is designed to use an adjustable amount of random access memory in an essential way, such that, hopefully, any attempts to compute the function using significantly less memory would only be possible at the expense of a prohibitive increase in computation time.

In fact, reading the scrypt paper, what the ROMix construction used in scrypt does is to first use a non-random-access stream cipher (actually, an iterated hash function) to construct a large (pseudo)random lookup table, and then to use that lookup table to perturb the state of the stream cipher while generating the actual keystream (the end of which, in ROMix, is then taken as the output).  It certainly seems feasible to apply a similar construction to actual stream ciphers, although there are various subtle details, as noted in the scrypt paper, to consider.


Are there any encryption schemes that enable to permute homomorphically? According to the Barrington's theorem, any circuit in NC1 can be converted to a branching program, whose main operation is the composition of permutations (along with the choosing of permutations according to inputs, which we omit here) . So I wonder whether there is a scheme that can directly encrypt the two-line notation of permutation, which also enables to do the composition of permutations on the ciphertext, except the general methods by using FHE/Multilinear mapping on permutation matrices?

One can do bounded-length "composition of permutations on the ciphertext"

by Evaluating Branching Programs on Encrypted Data.

Public key length and ciphertext length both scale linearly with the number of permutations.

Leveled FHE can evaluate arbitrary-length compositions of permutations, since iterated composition of permutations can be carried out in low depth. $\:$ (So, one does not need full FHE.)

I don't know of any less general methods than that for arbitrary-length compositions.


Why is this not a viable key exchange algorithm? I was just wondering why this kind of algorithm can't be used instead of, say, Diffie-Hellman to exchange keys:

Alice decides on a key she wishes to share with Bob.
Alice generates a stream of bytes with the same length as the key (securely, say, with a CSPRNG).
Alice sends to Bob:
C1 = (key ^ alice_random_bytes)

Bob generates a stream of random bytes in a manner similar to Alice.
Bob returns to Alice:
C2 = (C1 ^ bob_random_bytes)

Alice XORs C2 with her random byte sequence again, leaving only key ^ bob_random_bytes like so and sends it to Bob:
C3 = (C2 ^ alice_random_bytes)
   = (C1 ^ bob_random_bytes ^ alice_random_bytes)
   = (key ^ alice_random_bytes ^ bob_random_bytes ^ alice_random_bytes)
   = (key ^ bob_random_bytes)

Bob XORs C3 with his random bytes and obtains the key:
K = (C3 ^ bob_random_bytes)
  = (key ^ bob_random_bytes ^ bob_random_bytes)
  = key

This seems a lot simpler than Diffie Hellman, so I was wondering: what is the issue with such an algorithm?

I've simplified the Alice random bytes to ARB and Bob random bytes to BRB. Then the protocol follows as;
Alice knows $key$ and $ARB$ and sends $$C_1 = key \oplus ARB$$
Bob knows $C_1$ and $BRB$ and sends
$$C_2 = C_1 \oplus BRB = key \oplus ARB \oplus BRB$$
Alice calculates $C_2 \oplus key \oplus ARB =  key \oplus key \oplus ARB \oplus BRB = BRB$
Alice knows $key, ARB,$ and $BRB$  and sends
$$C_3 = (C_2 \oplus ARB) = key \oplus ARB \oplus BRB \oplus ARB = key \oplus BRB$$
Now, first of all, this requires a three-pass protocol.
Now, an observer sees
\begin{align}
C_1 & = key \oplus ARB \oplus {}\\
C_2 & = key \oplus ARB \oplus BRB\\
C_3 & = key \oplus \phantom{ARB}\oplus BRB \\
\end{align}
A passive observer (eavesdropper) simply x-ors all to derive the key $$key = C_1 \oplus C_2 \oplus C_3.$$ Therefore it is insecure against the weak assumption on the attacker; passive!.
So, you rely on the xor, however, did not check what an observer can get and calculate from them.
The Diffie–Hellman key exchange (DHKE), on the other hand, leaks $g^a$ and $g^b$ where Alice selects a random integer $a$ and sends $g^a$ and Bob select a random integer $b$ and sends $g^b$. Finding $a$ or $b$ from them is the discrete logarithm problem. On the other hand, The Computational Diffie–Hellman (CDH) assumption, is asked to find $g^{ab}$ given $g^a$ and $g^b$, and the DHKE is relayed on this. If the discrete logarithm is easy then CDH is easy. We don't know the reverse, in the general case.


How to compute the discrete logarithm of Diffie-Hellman with a composite modulus? Imagine $n = pq$ with $p-1 = 2 p_1 p_2$ and $q-1 = 2 q_1 q_2$.

I can compute the discrete logarithm of $y = g^x \pmod{n}$ by computing the discrete logarithm of $y$ modulo $p$ and $q$. But then how to recompute it?

What I'm doing right now is recomputing it in $2p_1p_2q_1q_2 = \frac{(p-1)(q-1)}{2}$ with CRT (they all happen to be co-prime). But we're still not modulo $(p-1)(q-1)$ (it lacks the last 2). I usually have a solution though, and I can get the other solution by adding $(p-1)(q-1)/2$ to it.

I figured out I should find the $x$, but I find two other solutions. I can't seem to understand why, shouldn't I find the exact $x$ this way?

Also here I'm lucky, most primes (except one of the $2$) were co-prime. What about when $lcm(p-1, q-1)$ is way smaller than $(p-1)(q-1)$ ?

I think the problem is that you are trying to recompute the result in $(p-1)(q-1)$ instead of $n$ and that is why you don't find the exact $x$.

Your question is:

  I can compute the discrete logarithm of $y=g^x \mod n$ by computing
  the discrete logarithm of $y$ modulo $p$ and $q$. But then how to
  recompute it?

As I understand, you want to find the discrete logarithm of $y$ modulo $n$, not modulo $(p-1)(q-1)$.

Let be $x_p$ the discrete logarithm modulo $p$ and $x_q$ the discrete logarithm modulo $q$. So to recompute the result we have to solve the system
$\left\{
\begin{array}{l}
  x \equiv x_p \mod p \\
  x \equiv x_q \mod q
\end{array}
\right.$

If $gcd(p,q) = 1$ then you can apply the chinese remainder theorem by using the Gauss algorithm (check also the Garner algorithm which is more efficient) without having to consider $p_1$, $p_2$, $q_1$, $q_2$ and you will find a unique solution.

  What about when $lcm(p−1,q−1)$ is way smaller than $(p−1)(q−1)$?

If $gcd(p,q) \not = 1$ but $gcd(p,q) \text{ | } x_p - x_q$ the system can still be solved but there exist several solutions.

Otherwise, you will not be able to recompute the solutions modulo $p$ and $q$ into the modulo $n$.