Is creating an OTP of a key to some data a secure secret sharing scheme? Suppose I have some data that has been encrypted with a known, secure algorithm and a key k. I want to distribute "pieces" of the key to n of my colleagues, and only be able to access the data when all keys are used.

I create a one time pad and XOR the key, then give that OTP to colleague 1, and reapeat this for each colleague. I have a couple questions about this:

Once the key has been encrypted, does it matter which piece was originally the key, or are all pieces now equal?
Suppose my colleagues all meet without me, for a total of n-1 keys, is there anything they can do with the collective data?
Could creating so many one time pads somehow create a vulnerability, or does the strength of an OTP hold with each subsequent piece created?

Since you mention one time pads, I'll deal with one time pad (OTP) secret splitting rather than more complex schemes.  In this case, you don't fragment the key into pieces, you create additional keys exactly the same length and then chuck the original key away.  The only way to recreate the original key is to XOR all of the generated keys back together.  There is a good tutorial here.  You should be able to fathom the method from this extract:-

Taking these bullets one at a time:-

All the new keys are equally important.  You cannot reassemble the original key without all of the new keys.  One missing key will give you nothing.
Further to point 1, no there isn't anything that they can do.  Each original key character still has a certainty of 1/256 if you've used bytes.  Clearly if the key was only one byte long this would afford no security against a brute force attack.  So use a long key, or a key derivation function, but that draws away from the spiritual purity of the OTP.
You would probably use one single one time pad to spilt the original key.  You wouldn't be creating additional keys.  If your OTP generator equipment produces true randomness, the existence of additional OTPs will not create any mathematical vulnerabilities.  You do of course need to keep the many new keys safe as they are all required. That might be an issue in itself.  There are more complex key splitting techniques that don't require a OTP and can split a secret that then only require a subset of the keys to recombine the original.  You might consider this more secure in some circumstances (if some agents were to be eliminated by the enemy).


Will current encryption always remain secure? Is there mathematical proof? Current encryption algorithms, such as AES, RSA, elliptic curve, etc. work based on known mathematical problems. I am specifically interested in the RSA.

Will such security always remain secure?

One way of breaking them would be due to a revolutionary increase computing speeds, making brute-force a viable option. This could be due to invention of quantum computers, neural-network-based hardware, etc. Such technology is at a very early phase, and will take some years to develop.

The other means is to find loopholes in the algorithm itself, using mathematics. Has it been mathematically proved that these algorithms can not be cracked, or is it a possibility? If so, how likely is it that cracking the RSA via a mathematical weakness will be possible in the near future?

This should be an important question, since being able to crack such a system potentially could let you blackmail companies, and even governments, since it is their data which is at risk.

Note: I first asked this question on Security SE, a user there told me to post it here.

"Will such security always remain secure?"

No. $\:$ In particular, quantum computers will break RSA and elliptic curves.

Has it been mathematically proved that these algorithms can not be cracked, or is it a possibility?

It is a possibility, since a very-practical algorithm for the Boolean satisfiability problem
would be enough to break essentially all complexity-based cryptography.

(There might still be a secure complexity-based proof-of-work system,

although it would need a super-constant number of rounds of interaction.)

If so, how likely is it that cracking the RSA via a

mathematical weakness will be possible in the near future?

Does Shor's algorithm constitute "a mathematical weakness" in RSA?


Forcing participants to be honest in Secure Multiparty Communication Alice and Bob engage to compute a secure function f(a,b) where a and b must be present in a set U. Although both Alice and Bob know f(a,b), how can Alice confirm that b is present in U and Bob confirm that a is present in U?

Try reading this paper https://www.math.ucla.edu/~tdokos/notes_files/garbledCircuits.pdf. It will answer your question.


How to sign a CRL file if I have offline keys? I am generating a CA for internal use. When generating a CA, the best practice I have observed is to keep the root CA offline and emit an intermediate CA certificate that will in turn emit the end-user certificates. This way, a compromise of the intermediate CA key can be recovered by revoking that intermediate CA and generating a new one.

I see, however, CRL files need to be renewed regularly (eg. daily), which would require the root CA keys to be used. But the main goal of all this is to keep the CA keys offline. What is the best practice here?

Is there the possibility of using a separate key for CRL signing? If so, how would I do this? Question is not OpenSSL-specific but I'm using OpenSSL in case you want to provide examples.

At some point your Root CA has to have control over it's subordinate CAs.  If there was a scheme where it delegates this control to another server (such as your OCSP-like suggestion), the Root CA would still need to have control over this service in some way or another.  In order to assert this control you would at some point need to power up the Root CA.  A scheme where the Root CA delegates full control to another service would mean that the Root CA effectively loses control; which is not what you want.

The standard way is to have the Root CA generate long-lifed CRLs.  This is relatively safe as the only certificates it issues are to a very few subordinate CAs and these CAs are (should be) securely operated in accordance with the PKI's Certificate Policy with a statement describing this operation in the CA's Certification Practice Statement.

Therefore, every (for example) six months:

Switch on the Root CA;
Generate a new CRL;
Export the CRL (for example using a CD/DVD burner);
Switch off the Root CA.

This process should be formalised and if you have concerns about someone running away with a copy of your Root CA's private key, your PKI Management Authority can/should insist on the use of witnesses and/or CCTV or any other scheme it deems fit.


Creating your own encryption and decryption algorithm I'm very uneducated when it comes to cryptography. I have tried to find an answer to my question, but what I've read doesn't quite cover what I'm asking.

I have thought up my own encryption algorithm (which I'm sure is nothing new) and I would like to know why this sort of algorithm is not used in terms of security, efficiency and any other reasons.

It stems from the Caesar Cipher. But, instead of shifting each letter by 13, you shift each character (using computer character values) by a certain value  each time.

So, let's say I had the sentence:

My dog's name is Rover.

And I have an array of numbers:

1, 4, 3, 2

I would shift M up by 1 character, y by 4, [space] by 3, d by 2 and then continue with the rest of the sentence, looping through the number array.
So, the sentence would be converted into N}#fpk*u!rdof$lu!Vrxfv1.

Let's call the array your "key". Only someone with the key could decipher the message, unless someone figures it out. The more items in your array (key), the safer you are from someone deciphering your message.

Apologies if my explanation is poor.
To summarize my question:

Why is this bad (or, not used)
Is it inefficient/insecure compared to other encryption methods
Is there anything else about this that should be considered

Thanks.

Edit: how to break Vigenère
Yes, this cipher (which as SEJPM points out, is Vigenère) is vulnerable to frequency analysis, but Vigenère resists this a bit, because common letters don't always get ciphered into the same ciphertext. The unavoidable vulnerability stems from the repeating nature of the key.
Let's say your message is $N$ characters long and your key is $k$ characters long. You may think that by repeating the key until you reach $N$ characters that you gain some "units of security" ("it's $\lfloor N/k \rfloor$ times more secure!"). But if I know your message is enciphered in this way, I have learned a great deal about your plaintext.
If I can estimate your key length $k$ $-$ and I can, with the great Kasiski's help $-$ then I can take every $k$th ciphertext character and group them together (for example, if $k=5$, group together the first, sixth, eleventh, etc. characters, then group the second, seventh, twelfth, etc. into another block, and so on). Each block is enciphered with the same character, a character from your key. At this point, a straightforward frequency analysis comes into play; breaking this is no harder than breaking the Caesar cipher you started with.
I do this for each "group" and now I have recovered your key.

It is cool that you came up with the idea of a polyalphabetic cipher on your own. But as the comment and other answer have pointed out, this cipher is insecure and can be broken quite reliably. Seriously: only use this for fun or pedagogical reasons.
In 1863, Kasiski even knew how to guess the length of the key for this cipher! That forces you to make your key longer / harder to remember.
It's very efficient; you can encipher text quickly with it. But that's a double-edged sword: I can attempt to decipher it quickly as well.


Related-key attacks against Salsa20 and ChaCha From the Salsa20 security document, DJB states that he doesn't care about related key attacks:

The standard solutions to all the standard cryptographic problems—encryption, authentication, etc.—are protocols that do not allow related-key attacks on the underlying primitives. I see no evidence that we can save time by violating this condition. The reader might guess that Salsa20 is highly resistant to related-key attacks; but I simply don't care.

Emphasis mine. The only related-key attack I know of is against Salsa20/7 and requires 2217 operations using 224 pairs of keystream blocks from two sets of keystream. I can't find any attacks on ChaCha. The linked paper cites a discussion from the eSTREAM forums which argues the attacks are irrelevant.
What is the state of Salsa20 and ChaCha security against related key attacks? What can be said about their design that would make them resistant to such attacks? How does ChaCha compare to Salsa20?

Perhaps the best evidence for the related-key security of Salsa20 is in the Rumba compression function proposed by the author:
$$
\mathrm{Rumba}(m_1, m_2, m_3, m_4) = f_1(m_1) \oplus f_2(m_2) \oplus f_3(m_3) \oplus f_4(m_4)\,,
$$
where $f_i$ is Salsa20 with a different initial constant for each variant, and each $m_i$ is 384-bit wide. Clearly, for the author to believe this construction would be secure it would require believing the permutation is secure against Salsa20 attackers who also control the key.

This belief was tested in the "New Features of Latin Dances" paper, which found collisions for 3 rounds in time $2^{79}$—much faster than generic methods. But 3 is a long way from 20, and so there does not seem to be much to fear.

Later, in an early version of a paper introducing SMT solvers to the differential cryptanalysis of ARX, Mouha and Preneel argued that there are no strong differential characteristics for 15 rounds of Salsa20, even in the related-key model. However, there are some subtle issues here, and this should be considered evidence but not proof that Salsa20 is immune to differential cryptanalysis.


Finding p and q in RSA with a given n, |p-q|<10000 I've got an RSA encryption I need to crack, but to do it I need to find the p and q values of an N I am given - it's quite large, around 308 symbols.
I know that N is the product of primes p & q, but I don't know what kind of searching algorithm I'd implement to find the exact p & q that fit |p-q|<10000. Since it needs to be an efficient method, I'm looking for a way that excludes finding ALL possible combinations of p*q = n.
How would I go about doing it? How would I even start with inputting the 308 symbol number anywhere? It's too large to fit any kind of variable in c# for example...

As @fgrieu said, it will work when ${|p-q|< N^{1/4}}$ , where ${\sqrt N}$ and ${A}$ both are very nearer. then we can take ${A = \sqrt N}$ to start with.

Let ${A=(p+q)/2}$ , i.e., A is mid point of p and q, which could be nearer to ${\sqrt N}$

There exist an integer ${x}$ so that, ${A-x=p}$ and ${A+x=q}$

${N=pq}$ ${=}$ ${(A-x)(A+x)=A^2-x^2}$

${x= \sqrt{A^2-N}}$

Since we know A and N we can find x and subsequently p and q.


What does ''latency'' really mean when a block cipher is partially unrolled? Typically，I think latency should mean the time from the first plaintext input to the first ciphertext output, when the block cipher is not totally unrolled (such as AES unrolled with 2 rounds).

If I use a pipeline to increase the throughput, the latency should relate to the amount of pipelined data. E.g. with AES unrolled with 2 rounds, and 100 group data to create the pipeline, then the latency must be larger than 500 cycles (except the time to calculate).

But in many papers, latency in this situation does not include this number, just the clock cycles of 10 rounds' critical path.

I do not understand why.

Also, what is the requirement of latency which limits the number of blocks which are pipelined?

When talking about a circuit (FPGA, ASIC...) implementing some encryption algorithm, the relevant measures are:

Bandwidth: how many input bytes can be processed per second.
Latency: how much time occurs between the moment an input byte (or block) is injected, and the corresponding output byte (or block) is obtained.
Circuit area, energy consumption...

AES (with 128-bit keys) is defined as using 10 successive rounds; the important point being that each round works over the output of the previous round. Thus, the ten rounds MUST be computed sequentially. However you implement it, the data block will have to go ten times through a circuit computing one round. Ten times through the same circuit, or five times through two copies of the circuit, or through ten distinct copies of the circuit: this does not matter here. The latency for an AES invocation is related to the number of rounds.

If you do a loop, with a single circuit for one round and some gates to reuse that circuit ten times, then you will have minimal total circuit area, but also lowest bandwidth, because you will have to wait for completion of the ten rounds before starting a new AES invocation. For instance, if processing one round takes one clock cycle, then you will have a latency of 10 cycles (it takes 10 cycles to get an encrypted block from the plaintext block), and a bandwidth of one block per 10 cycles. If you "unroll" the implementation with 10 copies of the "round" circuit, then latency will still be 10 cycles: when you inject one block, the corresponding output block will be available 10 cycles later. However, you can then inject one block per cycle: ten times the circuit area, but also ten times the bandwidth.

To sum up, loop unrolling and pipelining in a circuit does not change the latency, but the bandwidth.

All of the above is about doing "AES invocations", i.e. applying the AES algorithm on 16-byte blocks which are independent of each other. When encrypting a message (as a potentially very long sequence of bytes), you are using the AES through a block cipher mode of operation which can add its own constraints. For instance, if using CBC, then, by construction, you need the result of the encryption of one block before beginning the encryption of the next block (because you first XOR each block with the previous encrypted block). Therefore, even if you have a fully unrolled AES circuit with a latency of 10 cycles and a bandwidth of one block per cycle, you will not be able to encrypt more than one block every 10 cycles. Conversely, CTR mode allows for the full bandwidth of one block per cycle, because all the elementary encryptions in CTR can be done in parallel.

Here, I am not talking about the latency of the block cipher itself (AES), but the latency induced by its mode of operation.

If we go one step further and think about overall message processing: consider SSL/TLS. In SSL, data is encrypted as records where each record contains up to 16 kB of data, and has its own MAC. Upon receiving a record, an SSL implementation must first verify the MAC over the complete (decrypted) record before beginning to use the data (until the MAC is verified, the SSL implementation cannot assume that the data has not been altered). This means a much higher latency: between the time the first encrypted record byte is received and the time the corresponding plaintext byte is really available, the decryption and MAC processing of the whole record must occur.

This example shows that the notion of "latency" is flexible and occurs at many levels, so it is important to be clear about what we are talking. In the case of a block cipher like AES, the "latency" is about the minimum processing time for one block independently of other blocks. This translates to the latency for a "message" only insofar as the encryption mode and other protocol characteristics like a MAC do not add their own constraints.


Why Bellare-Micali Oblivious Transfer Construction requires ElGamal with hashed key? The idea of the Bellare-Micali Oblivious Transfer Constructions is the following:

Informally, the receiver is required to generate two public keys $y_b$, $y_{b-1}$ such that it knows only the secret key paired with $y_b$ (where $b$ is its choice bit), indicated with $k$.
In order to prevent the receiver from cheating, the sender requires that the two generated public keys have to satisfy a certain constraint, i.e., $y_b \cdot y_{b-1} = c$ . In such a way, the receiver cannot know both private keys or it can compute DLOG. At this point, the receiver sends the two public keys to the sender.
Then, the sender encrypts $m_0$ with $y_0$ and $m_1$ with $y_1$ and sends both encryptions $c_0$, $c_1$ to the receiver.
Finally, the receiver obtains $m_b$ by decrypting the chipertext $c_b$ (corresponding to its choice bit) using the private key $k$ (note that $c_b$ is the only chipertext it can decrypt).
While the general idea is clear to me, I do not get why ElGamal is not computed as $y_{0}^{r_{0}} \cdot m_{0}$ (and $y_{1}^{r_{1}} \cdot m_{1}$) but $H(y_{0}^{r_{0}}) \oplus m_{0}$ is used instead.

The hash needs to be used in order to be able to simulate. In particular, consider the case that the receiver is corrupted. The simulator can't know the choice of $b$ so doesn't know if the receiver can decrypt the first or the second message. Therefore, in order to simulate, the simulator has no choice but to just choose random values to represent $H(y_0^{r_0})$ and $H(y_1^{r_1})$; denote these random values by $\rho_0$ and $\rho_1$. Then, the simulator can see which of the two queries $y_0^{r_0}$ or $y_1^{r_1}$ the receiver makes to the random oracle. (One can show via the CDH assumption that the receiver cannot make both queries.) Now, once the simulator receives the query $y_b^{r_b}$ to the random oracle, it can send $b$ to the trusted party and get back $m_b$. Then, it sets the response of the random oracle to be $\rho_b \oplus m_b$ (i.e., $H(y_b^{r_b})=\rho_b \oplus m_b$). You should be able to verify that this indeed gives the right distribution.
Next, in order to simulate the corrupted sender, the simulator has to be able to extract the values $m_0,m_1$. Since it doesn't know $r_0,r_1$ (since no ZKPOK are used), this is problematic without the hash. However, .... I'm actually stuck at this point; I'm not sure how you would do this without adding a proof of knowledge of the discrete log of $c$ in the beginning (maybe my brain is fried right now). Then once you have this ZKPOK, you wouldn't need the hash for this part of the proof anyway. Note that you only need to do the ZKPOK once for many OTs using the same $c$.
Note that the lectures refer to the semi-honest setting. In this case, I don't believe that the hash is actually necessary, and it suffices for $m_0,m_1$ to be in the group.


Verify a RSA signature using only RSA encryption I'm trying to verify a RSA signed message, however, the API that I have access to in that environment only has encrypt and decrypt.
I think I understand that verification and encryption with public key are similar. Actually, running the following seems to work:

openssl rsautl -sign -in clear -inkey private_key.pem -out signed
openssl rsautl -encrypt -pubin -inkey public_key.pem -in signed -raw -hexdump

This second command will get the initial clear, padded (then I just need to unpad and verify that it matches the clear). However, the -raw is where I encounter an issue.
As the signed message is the size of the key, I can't encrypt it (the API will refuse, as does openssl if you omit -raw).

I'm not sure on how to proceed. I feel that what I'm trying to do should be possible.

The API you are trying to use automatically pads (probably RSAES-PKCS1-v1_5 padding). Instead you require it to verify and remove the padding during signature verification.

If you cannot skip the padding then you cannot use the API. Try and find a library that actually can verify instead. You shouldn't program RSA itself, but in the end it's just an algorithm. As long as you have access to the key - and preferably a big integer math library - you should be able to perform RSA modular exponentiation and verification / removal of the padding yourself.

You cannot just magic away 11 bytes that are added to the plaintext before modular exponentiation. OAEP would pad even more.

You could try and decrypt the signature with the public key and hope that the API detects the public key and performs the verification and unpadding instead itself, but that's a long shot. Note that you should get an error message if the padding cannot be verified.

Note that Diffie-Hellman also performs modular exponentiation. Sometimes you can use DH functionality to "raw decrypt" an RSA signature.


What are the standard properties of an S-Box Apart form the following, what are the other properties of a good cryptographic Substitution box or the S-Box:

Changing one input bit should change about half of the output bits.
Each output bit should depend on every input bit.

Another very common criteria for an S-box with $n$ input bits and $m$ output bits with $m\le n$ (as most commonly used S-boxes are) is that each of the $2^m$ output values should be reached for exactly (or at least near) $2^{n-m}$ input values.

The question's criterion 1 can be made strict and become the Strict Avalanche Criterion. There are even stricter /higher-order versions. There also is the Bit independence criterion. The desirability of these properties depends on the overall design of the cryptographic construction using the S-box, and is not easy to assess.

More generally, S-boxes are typically optimized with use as part of a particular cryptographic construction in mind, aiming at improving it's overall resistance against cryptanalytic attacks, as pointed in comment.


secure embedded/microcontroller crypto using AES-ctr with hmac-sha2 The embedded device is a low-power 8-bit microcontroller (memory usage is constrained to about 10kb code, 1kb ram). As the device is battery-powered and manual service should be minimal, more powerful processors are not an option.

Throughput is very limited, so performance is not too much of an issue.

The system we came up with is AES-ctr mode encryption with hmac-sha authentication:

// encryption_key, mac_key, device_id are all independent, secure random,
// unique per device pre-programmed values

// aes-ctr encryption (pseudocode)
first_nonce = nonce = device_id || counter++
for block in plaintext
    ciphertext.append(aes_ctr_encrypt_block(encryption_key, block, nonce))
    nonce = device_id || counter++ // counter is saved in non-volatile storage (e.g. flash or eeprom) to avoid re-using after power down

// authenticate nonce + ciphertext (pseudocode)
data = first_nonce || ciphertext
mac_tag = hmac_sha2(data, mac_key)

// send or store mac_tag, nonce and ciphertext
send(mag_tag || data)

The receiving side should then use the deviceID to look up the mac_tag and verify it matches.
By checking if the counter is larger than the one previously received we want to eliminate replay attacks.

If the validation checks out, the data is decrypted.

Is this a secure system? Also, what would be the effect of truncating the output of hmac_sha2 to 128 bits?

Fgrieu has already posted a good answer, which I won't try to repeat.  However, here are a few additional observations:

For an embedded system, you may want to consider using CMAC-AES instead of HMAC, since you can reuse your AES implementation, and don't need a separate hash function.
Further consider using SIV mode (RFC 5297).  It's very similar to CTR+CMAC, but provides additional protection against accidental nonce reuse, and also removes the need for separate cipher and MAC keys.
Do be careful about nonce reuse, especially if you don't use SIV.  (But please use SIV, if possible!)  Saving the nonce to flash after every message is generally not a good idea, so the usual approach is to write, say, nonce + 1024 to flash before each block of 1024 messages.  On reboot, just resume from the last nonce value in flash, which should be greater than the last nonce actually used.  (Also, make sure that nothing breaks even if power is lost during a write; there are standard techniques for handling this, but they're not really specific to crypto.)
Consider including a timestamp and/or a sequence number in your messages to protect against replay attacks.  If you're potentially using the same keys in both directions, or over multiple channels, also tag your messages with sender and receiver IDs.  (These may be in plaintext, but they do need to be included in the MAC.  For SIV, you can include these as "associated data".)


What cipher mode is suitable for independantly decryptable short messages? I'm building a small VoIP client which transmits encrypted audio data via UDP, and some packet loss is expected, so each packet will need to be decrypted separately even if others in the stream don't arrive. I also don't enforce strong ordering of data, since re-ordering is done only if a packet is significantly out of step.

I know some modes like CBC require the previous ciphertext block to be known in order to decrypt the next block, so I don't see that being suitable. ECB is ideal in terms of the "decryptability" requirement, but obviously it's not secure. I figure OFB might be useful, but I can see the implementation being awkward if multiple blocks are skipped.

Are there any modes of operation that suit this kind of scenario, without significant implementation overheads?

Reflex answer: EAX. EAX does encryption and authentication, with minimal space overhead. EAX also has light requirements on the IV: it just needs a non-repeating value, so a simple counter can work. Possibly you already have a suitable counter or time stamp in your packets, that can be used as IV.

About replay attacks: you already expect that some packets will be dropped, or reordered. Be warned that if your protocol tolerates it, then the attacker can force it upon you, mechanically. I suppose that your protocol already includes some sort of frame counter so that you can reject frames which are too old (or too new !) and merge duplicates. That frame counter would work nicely as an IV for EAX.

If you want to do it old-style, use CBC with a random IV (IV must be transmitted along the packet), and then a MAC (HMAC, for instance) computed over the encrypted data (including the IV) and appended to the packet. You will need more code, cryptographically strong generation of an IV for each packet, and space overhead is likely to be higher than for EAX. That's the price of being old-style.


Does this pairing-based signature scheme work? Suppose $g$ is a pairing-friendly elliptic curve with subgroup generators $G_1$ and $G_2$. Suppose also that $M$ is the message I want to sign.

Setup

Compute $A = a \cdot G_1$ and $P = p \cdot G_2$, where $a$ and $p$ are some secret values.
The public key is then defined as a tuple $(A, P)$.

Signature

Hash message $M$ to a number using a hash function: $m=Hash(M)$.
Compute  $C = \frac{p}{a \cdot m} \cdot G_2$.
The signature is then defined as $C$.

Verification

Compute $m = Hash(M)$.
Verify that $e(A, C)^m = e(G_1, P)$.

Are there any holes in this scheme?

Your proposed signature scheme falls to universal forgeries under a known message attack (UF-KMA).

The adversary $\mathcal{A}$ receives the public key $(A,P)$, a single message signature pair $(M,C)$ and the challenge message $M^*$.
It outputs $$C' := \frac{H(M)}{H(M^*)} \cdot C.$$

The adversary described above is succesful with probability $1$.
To see this, consider that $C$ is by definition
$$C = \frac{p}{a\cdot H(M)} \cdot G_2.$$
We now have
\begin{align}
C' &= \frac{H(M)}{H(M^*)} \cdot C\\
&= \frac{H(M)}{H(M^*)}\cdot\frac{p}{a\cdot H(M)} \cdot G_2\\
&=\frac{p\cdot H(M)}{a\cdot H(M) H(M^*)} \cdot G_2\\
&=\frac{p}{a\cdot H(M^*)} \cdot G_2,
\end{align}
which is exactly the signature of $M^*$ and will therefore be accepted by the verification equation.


Expectation Value of the Index of Coincidence Can Anybody tell me why the expectation value of the Index of Coincidence is the following?

For a cipher text string of length $L$, where $n$ is the number of
alphabet characters, $k_r = 1/n$, and $k_p = \sum_{i=1}^n p_i^2$

$$ E(IC) =  \frac{1}{t}*\frac{L - t}{L - 1}*k_p + \frac{t - 1}{t}*\frac{L}{L - 1}*k_r$$

I forgot to state that $t$ is the period of the poly alphabetic cipher used to encipher the message.

Expected Index of Coincidence usually refers to a language's expected index of coincidence (1.73 for English, or 0.067 if you're not normalising).

The formula in question is usually used to determine the length of the key ($t$) given the (measured) $IC$ of received cipher-text. $IC$ is the probability that two randomly-selected letters from the cipher text are identical.

Let $X=\{ x_1,x_2,x_3,...x_L\}$ be the cipher-text.  If we think the the poly-alphabetic cipher has period $t$, then we would expect each of the following:

\begin{eqnarray}
& X_1 =\{x_1, x_{t+1},x_{2t+1},...\}\\
 & X_2 =\{x_2, x_{t+2},x_{2t+2},...\}\\
& \vdots \\
 &X_t =\{x_t, x_{2t},x_{3t},...\}
\end{eqnarray}

to exhibit the same index as the plaintext ($\kappa_p$). So we can reconstruct $IC(X)$ as follows. Pick two letters at random, we want the probability that they match.

The probability that they are in the same $X_i$ is:

$$
\frac{tC(\frac{L}{t},2)}{C(L,2)} = \frac{L*(\frac{L}{t}-1)}{L(L-1)}
$$

The probability they are in different $X_i$s is:
$$
\frac{C(t,2)*\frac{L}{t}*\frac{L}{t}}{C(L,2)} = \frac{t(t-1)*\frac{L}{t}*\frac{L}{t}}{L(L-1)}
$$

If they are in the same $X_i$ then they are both enciphered using the same alphabet: so the probability is $\kappa_p$
If they are in different $X_i$s then they are enciphered using different alphabets, so we can assume they are randomly distributed: so the probability is $\kappa_r$

So the probability of two random letters matching is approximately

\begin{eqnarray}
IC(X) & \approx \frac{L*(\frac{L}{t}-1)}{L(L-1)}\kappa_p + \frac{t(t-1)*\frac{L}{t}*\frac{L}{t}}{L(L-1)}\kappa_r\\
     & = \frac{(L-t)}{t(L-1)}\kappa_p + \frac{(t-1)*L}{t(L-1)}\kappa_r
\end{eqnarray}


Strength and weaknesses of this JavaScript charCodeAt based login script I know of a company on their website who are using this very basic password login page written in JavaScript. This doesn't seem very secure at all, because in the html source code it shows where the script comes from: http://www.dynamicdrive.com/dynamicindex9/password.htm and also you can see how it works as it's JavaScript and you can just view the source in a browser.

It seem pretty simple, it takes a value entered in an input field by a user works out the char unicode interger value of each character in the passcode and then times this value by the previous value and loops this until it has done this for each character in the passcode. It then compares this with an answer value saved in JavaScript which the user has already converted from the right answer in the same manner using the tool on  http://www.dynamicdrive.com/dynamicindex9/password.htm and then if these two match the JavaScript redirects you to the secret page which is a html file with the same name of the clear text password.

My question is knowing how this method works to convert what the user inputs into a charcode value, how can you reverse this process to find out what the original plain text password was? I have changed the usercode and passcode value below to what is featured on this companys website.

I have thought of two methods to change 16978476480 back to plain text. One possibility I guess would to get a word list of common passwords, convert each to a number value using the same method and then seeing if any match 16978476480. The other similar method would be to pick random characters to form a string between 4 and 8 characters in length, the usual password lengths, times all the unicode values to together and then keep looping until we get lucky and hit a match for 16978476480. Can anyone think of any better of faster ways?

The script is as follows:

//Encrypted Password script- By Rob Heslop
//Script featured on Dynamic Drive
//Visit http://www.dynamicdrive.com

function submitentry(){
password = document.password1.password2.value.toLowerCase()
username = document.password1.username2.value.toLowerCase()
passcode = 1
usercode = 1
for(i = 0; i < password.length; i++) {
passcode *= password.charCodeAt(i);
}
for(x = 0; x < username.length; x++) {
usercode *= username.charCodeAt(x);
}
//CHANGE THE NUMBERS BELOW TO REFLECT YOUR USERNAME/PASSWORD
if(usercode==12211815000&&passcode==16978476480)
//CHANGE THE NUMBERS ABOVE TO REFLECT YOUR USERNAME/PASSWORD
{
window.location=password+".html"}
else{
alert("password/username combination wrong")}
}

<form name="password1">
Enter username:
<input type="text" name="username2" size="15">

Enter password:
<input type="password" name="password2" size="15">

<input type="button" value="Submit" onClick="submitentry()">
</form>

You don't need to brute force it. Since the passcode is the product of all its character codes, you can just find all prime factors of the passcode. I used an online tool which yields $2^6\cdot 3\cdot 5\cdot 7^2\cdot 61^2\cdot 97$. It looks like an ASCII passcode of length 5.

This doesn't get you anywhere since this is just a check for a web page to open. Now you need to "brute force" all possible combinations of $2^6\cdot 3\cdot 5\cdot 7^2\cdot 61^2$ ($97$ is more of less fixed to be a) and then try for each combination all permutations. You can further filter a little since only lowercase letters are used. For each permutation you would need to download the password+'.html' file. When you finally get an HTTP 200 code you're done.

Of course if you assume that every letter is lowercase then you can assume that $2\cdot 61$ is z. Now the question is to find a 5 letter word with letter zza in it.... The other prime factors will get you p and i.

Note that you only need to do this for passcode, usercode is not used.


How do Latin squares relate to quantum cryptography? About ten years ago I became interested in Latin squares.  A friend who was at the Clay Institute at the time mentioned that applications for Latin squares were exploding, and that they were being utilized in quantum cryptography.

I've found a paper discussing use of Latin squares in cryptography in general (p.8 in linked doc), but can't find direct info on their uses in quantum cryptography.

This paper also makes reference to a paper entitled: "A message authentication code based on
Latin Squares" from the Australasian Conference on Information Security and Privacy.

However I'm having trouble finding direct references to Latin squares in quantum cryptography.

Basically, I'm trying to get a high-level understanding of this association, if it is indeed accurate.  Any info or insight would be appreciated.

There is a conjecture that a full set of mutually orthogonal Latin squares' existence is linked to the existence of MUBs. I am unsure if there is support for this beyond experimental evidence.

Mutually Unbiased Bases (MUBs) introduced by Schwinger are used in quantum measurements and also quantum cryptography. MUBs are $d+1$ Orthonormal bases of $\mathbb{C}^d$ where the inner product of any pair of vectors between two distinct bases is $1/\sqrt{d}$ in magnitude.

For example, constructing
 a complete set of mutually unbiased bases in the $\mathbb{C}^d$ with $d$ composite and not a prime power has not been achieved yet, not even for $d=6.$

See the PhD thesis of Joanne Hall here


Timing Attacks on ECDSA, ECDHE, AES and SHA2 Are there any known timing attacks (both practical and theoretical) on any implementations of  the following?

ECDSA (I'm aware of this one - are there any applicable to prime fields?),
ECDHE (again, over a prime field),
AES,
SHA2

The attack which you link to, on ECDSA, is related to the following: the signer computes several values $kG$, for random $k$ values chosen uniformly modulo $n$ ($n$ is the size of the subgroup generated by $G$). One such value is generated for each signature. It is important that the selection is uniform: even small biases can be exploited in order to make a key recovery attack. The crucial point is that each ECDSA signature consists in a pair $(r,s)$ where $s = (m+xr)/k \pmod n$ where $m$ is known (it is the hash of the signed message). Each signature involves a new $k$, thus a new $r$ (because $r$ is obtained from $kG$); the $r$ value follow a definite distribution modulo $n$. So if $k$ are biased, then the bias easily turns into an information leak on $x$ (the private key). As an extreme case, if a $k$ value is reused, then the two corresponding signatures suffice to recompute $x$ directly (this is what happened to Sony with their PS3 firmware signature system).

In the OpenSSL implementation of $kG$ on binary curves (using a variant of Montgomery's ladder), it so happens that the code was "optimizing" things by making $\lceil\log k\rceil$ iterations only; so that if $k$ was shorter than $n$ by, say, 3 bits (happens once every eight signatures or so) then the loop was slightly faster (3 less iterations). The attacker can detect that. If the attacker can make the target generate signatures on messages that the attacker knows (that's easy when the target is a SSL server; the attacker just has to connect), then the attacker can keep a subset of the signatures, precisely those where $k$ was "short". This becomes equivalent to a biased $k$ generation, and leads to private key reconstruction.

I describe this to show the important point: it is not specific to elliptic curves over binary fields. In fact, it is not specific to elliptic curves. A classic square-and-multiply implementation of a modular exponentiation for plain DSA could be equally vulnerable. Elliptic curves (in prime fields or binary fields) are not especially weak or strong in that matter. It is best described as a weakness of DSA (and variants, including ElGamal signatures and Schnorr signatures). To protect against it, the implementation must take care to take a constant time in all cases, so as not to leak information on $k$.

It seems unlikely that ECDH would suffer from a similar issue. With ECDH, leaking information about the private key length seems benign enough. The problem with DSA arises from leaking bias information on a value $k$ which is used along with the private key $x$ in "simple" operations (multiplication and division modulo a prime). Diffie-Hellman, be it modulo a prime or on an elliptic curve, does not feature such "simple operations" involving a randomly selected value and a permanent private key.

Moreover, in the case of ECDHE, the final "E" means ephemeral, which more or less implies that the DH private key will not live long. SSL/TLS server may reuse the same DH private key for a few connections (as long as the private key is kept in RAM only, it fulfills the "ephemeral" contract), but normal SSL/TLS servers tend not to do that much. Generating a new DH private key is efficient. This correspondingly severely limits the power of the attacker: timing attacks are statistical in nature, which means that they need to work over several measures which involve the same secret value. With ephemeral DH keys, the private keys can be regenerated often enough to defeat timing attacks in a quite generic way.

For AES, timing attacks are again based on implementation characteristics. Specifically, "normal" AES implementations use lookup tables, and thus exercise caches. The attack will work either on evicting parts of these tables from cache and then measuring the algorithm execution time (thus counting the number of cache misses involved during the execution), or on having the attacker's data evicted from cache when the AES block cipher runs, and then working out (again with timings) which parts of the data were impacted. In both cases, this allows the attacker to gain some information on the intermediate values used in the algorithm, leaking information on the key.

The attack is quite feasible when the attacker can run his own code on the same machine, so as to use the same caches (this is a setup which applies to traditional multi-user mainframes, but also to virtual machines, where one VM may spy on another). For a remote attacker, this has also been demonstrated in lab conditions, but then it depends on a lot of parameters, and the remoteness makes execution time harder to measure with high precision; applicability to any specific real-life situation is hard to assess.

There are table-free AES implementations (see this question) but they use specific CPU features, or are quite slower, or both. Recent x86 CPU have an hardware AES which is very fast, and immune to such timing attacks.

SHA-2 is a family of hash functions. As such, they don't have keys. If they contain no secret, then there is nothing to obtain through timing attacks...

A hash function may be used on secret data, though, in particular in HMAC. SHA-2 is all arithmetic operations, no tables, no data-dependent branches. It seems hard to make a SHA-2 implementation which would be susceptible to timing attacks.


How is key rotation defined? I'm aware that it's advisable to rotate cryptographic keys periodically.  HKDF accepts high-entropy input (IKM - Input Key Material), and expands it to an arbitrary length.  It also accepts a salt, the RFC states that "the use of salt adds significantly to the strength of HKDF".   Naturally, changing the salt results in distinct Output Key Material.

What I would like to clarify, is whether updating the salt (in the context of HKDF) constitutes 'key rotation', or whether the IKM itself needs to be changed periodically.  I suspect the latter, but I'd like to hear what other people have to say.  I assume that this also applies to other KDFs like Scrypt.

If you are concerned with preventing retroactive decryption—e.g., making sure that when the bad people in uniforms take your phone away from you to a forensics lab to find evidence by which to convict you of exercising human rights, they can't use what's on it to decrypt all the past conversations you had over the internet while they were eavesdropping—then you need to rotate the IKM and erase the old one and all keys derived from it.

If you are merely trying to encrypt large volumes of data with cryptosystems that can handle only small volumes per key—e.g., you are trying to use AES-GCM with a single key to encrypt petabytes of messages—then you can just use a different HKDF-Expand info parameter with the same salt/IKM/OKM.

The main purpose of varying the salt is to mitigate multi-target attacks: if everyone used the same salt, or no salt, with IKM having only 128 bits of min-entropy, and if there are $u$ different users of the system, the adversary can get a factor of $u$ cost reduction and factor of $u^3$ speedup by attacking them simultaneously parallelized $u^2$ ways at an expected cost of ${\sim}2^{128}/u$ in the expected time for ${\sim}2^{128}/u^3$ sequential trial evaluations of the cryptosystem.  But if all users have distinct salts, the batch advantage vanishes.  Another way to thwart the batch advantage is to use 256 bits of min-entropy instead, and 256-bit keys everywhere.

(The salt is also documented to prevent accidentally using the same key material for two different purposes, if somehow an adversary can cause the same secret IKM to appear in two different places, though it seems to me that if that happened you would probably have bigger problems.)


How far into the future is AES considered secure? I've looked at NIST documents and done many Google searches, but I can't find an answer to this seemingly simple question.

I am storing data on harddrives, encrypted with AES-XTS 256 bit. Some of this data has a long lifetime, i.e. will still be valuable to an attacker and not good to lose into the future.

My scenario is that a harddrive could be lost today, and while the AES encryption is unbreakable today, how about in 20 years? 30 years? An attacker could keep it or find it in the future and use an not-yet-known attack to break it. Of course this is guesswork, my question is if there is an "official guess" from the NIST or someone else that I can quote and that says "we consider AES-256 secure until at least 2030" or some such.

NIST doesn't make recommendations based on just the cipher alone. NIST SP 800-57 Part 1 includes some discussion of this. Section 5.2 (on page 44) explains rationale for having "cryptoperiods". They list many factors affecting long term security, with an emphasis on key exposure. It's not as simple as guessing the security of AES because AES is just one piece of a larger implementation, with many avenues for key exposure.

If you're looking for a number for how long to keep using a symmetric data encryption key, they say the following on page 50:

  A maximum recipient usage period of 3 years beyond the end of the
  originator usage period is recommended

This is not because they think AES is going to be practically broken in 3 years; it's because it's difficult to keep entire systems secure long term, and rotating the key periodically is a good idea.  For your use case,  I think the suggestion to change the key every 3 years is reasonable.

Now, it's very hard to give a direct answer to your question about AES itself. It's a very heavily studied cipher and currently the best known attacks are completely impractical. That's the best we can say about any cipher. Nobody knows what kind of attacks will be available 30 years from now. Some may argue for a 192 or 256 bit key length due to the threat posed by quantum computers implementing Grover's algorithm, but this is not currently feasible with any known QC and speculating on when it will become so is probably impossible.


What schemes support signature aggregation? Definition: Signature aggregation is taking $n$ signatures of $n$ distinct messages and aggregate them into one short signature that has the same length range as the rest of the signatures. The combined short signature, along with the original messages and public keys, should convince the verifier that each message was signed by the owner of the public key.

What schemes support signature aggregation?
Please provide a scheme name and known implementation if such exists.

I am only aware of BLS signature implemented in PBC

I will have to read up on BLS, however, if I understand correctly by implementing the aggregation of $n$-messages, only the signature is aggregated - not the identities, so for an n-of-n multisig use-case it'll require knowing all public keys. I suspect you could make this tradeoff in both systems, but I will not spend the time to verify this conjecture.

The only other signature scheme that I know that supports aggregated signatures is Schnorr using Bellare and Neven. This supports n-of-n aggregated signatures and aggregated identities over a common message.


How hard/easy will be to break a SHA-1 or SHA-256 hash if the attacker knows part of the original text? I'm creating an algorithm to hash some text variables (20/30 characters long) to send them across an insecure channel. I'm not dealing with high security data, so no credits card numbers or any other very sensitive information.

The original text variable is composed like this:

{secret-client-code,public-random-code}

Then that is hashed and sent across the channel. However, the public random code is sent raw in the channel, so an attacker will know it. Does this make my hashing vulnerable to an attacker considering that the random code is about 30% of the whole variable? (I can change this if needed.)

It's probably a really bad idea to try and roll-your-own here. If you have to ask a question like this, you would probably just be better off using shrink-wrapped solution like SSL rather than trying to make your own protocol. There are a lot of tricky problems around getting these kinds of things right.

However, if you insist on doing this yourself, there are constructions that allow you to do what you want to achieve here.

What you want is a message authentication code (MAC). You can MAC the hash of the variables and then send this across the insecure channel.

In order to do this safely, you need to use a construction like HMAC. You should particularly use such a construction if you are using SHA-1/SHA-256 as they suffer from message extension attacks.

You also need to guard against replays; that is, where an attacker resends a previously seen message on the channel with the hope of repeating an action or causing some other nefarious effect.

These are just a flavour of the kind of bear-traps that can spring when trying to design your own protocol!


Does there exist a universal one-way permutation? Leonid Levin constructed a universal one-way function, i.e. a function which is one-way as long as there exists at least one one-way function.
But my question is, does there exist a universal one-way permutation, i.e. a function which is a one-way permutation as long as there exists at least one one-way permutation?  Would a modification of Levin’s construction achieve this?

To the best of my knowledge, this is unknown. That is, Levin's construction is a one-way function but most certainly not a one-way permutation. I don't see any way in which it can be modified to make it a permutation, since the way it works is by running arbitrary machines and then amplifying. Since there is no efficient way of checking if something is a permutation by looking at the machine (to the best of my knowledge), I don't see how one could modify Levin's construction.
Of course, this is just a limitation of what we know, and it begs a very interesting research question. Does there exist a universal one-way permutation? Similar questions can be asked about other primitives as well. A good paper to read that has some relation to this question (for other primitives) is On Robust Combiners for Oblivious Transfer and other Primitives by Harnik et al.


Zero Knowledge vs. Digital Signature Can someone explain to me, why Zero-Knowledge-Protocols are used instead of letting the person sign a random string and then verify the signature?

Doesn't Fiat-Shamir need even more processing-power than RSA with swapped private and public keys? (RSA can be used as signature-method by "encrypting" with the private key and "decrypting" with the public key, can't it?)

In Zero knowledge protocols , the verifier trying to verify the validity of the prover's arguments or parameters. So according to the theory , the verifier doesn't know anything about the prover in the beginning and gain knowledge when the testing process goes along. This is a statistical approach and probability of the "truth" increases when you do more tests.

Contrary , if you using a PSK system, you have the knowledge about the prover and verification process is one time and binary(either true or false).

Yes the Zero-knowledge protocols requires more processing power and consume more time.


Layman's description of the padding oracle attack I understand that the MAC-then-encrypt approach is susceptible to several attacks including the so called padding oracle attack. I understand that in this attack the attacker modifies the padding and listens for the errors caused which he can then use to infer the plain text. Can someone please explain the attack in layman's terms?

I would like to have the following addressed in the answers:

How does the attacker listen for these errors? Does it mean the attacker is assumed to have some malware installed on the host machine doing the decryption?
Is the attack based on a cipher text captured by the attacker, or a chosen cipher text selected by the attacker?

Quoting the answer here:

Padding Oracle attacks are mainly a problem in cases, where e.g. an encrypted message is modified and send to a target. These attacks try to measure the difference when decrypting and validating the message.
The steps are:

decrypting the message
checking the padding > error if wrong
checking or processing the data > error if wrong or format corruption detected

The padding oracle attacks try to measure timing differences between step (2) and (3) or utilizes different error messages.

So the information leakage that enables the attack comes in the form of either timing differences or is present in the error messages that the server returns as a response to the malicious query.


why did oaep change from pkcs1 v2.0 and v2.1? In PKCS1 v2.1 the OAEP output is prepending with a null byte. Quoting RFC3447,

  i. Concatenate a single octet with hexadecimal value 0x00,
     maskedSeed, and maskedDB to form an encoded message EM of
     length k octets as

        EM = 0x00 || maskedSeed || maskedDB.

In PKCS1 v2.0 (as defined in RFC2437):

   11. Let EM = maskedSeed || maskedDB.

So in PKCS1 v2.1 you prepend a null byte and in PKCS1 v2.0 you don't. What technical difference does that change (and possibly others) create between the two versions of the standard?

The answer is relatively simple, but I'll expand on the details of the changes from PKCS#1 2.0 to 2.1 in two additional sections below this answer.

On the padding with the zero valued byte

The I2OSP function - used during decryption - converts an integer to a statically sized, unsigned, big endian octet string or byte array. This function will always generate a number of $k$ octets as it is used, automatically left-padding with zeros. The OS2IP function is the reverse function.

However, as it is defined for PKCS#1 v2.0 / OAEP encoding, it will always operate over an octet string of $k - 1$ bytes. This isn't nicely symmetrical, and it doesn't clearly communicate to the reader that the top eight bits of the resulting number should always be set to zero. The result of the OS2IP function for $X_{k-1} || X_{k-2}... || X_0$ and $00 || X_{k-1} || X_{k-2}... || X_0$ are identical, because the big endian number is unsigned; even if the most significant bit is set, it doesn't get interpreted as the sign bit for a two complement number.

When implementing it in a language such as Java, the new description does make it clear that you can simply make sure that the encoding starts with 00 and then convert to a number using a converter that expects a signed value. In general it is also better to always operate on numbers with a known encoded size.

On the padding size

This section explains why the padding with the zero byte is required at all.

In PKCS#1 v2.0 the encoding operation for the encryption operation in 7.1.1 is mentioned in its own section 9.1.1.1 (not 9.1.1.2, I'll notify the author of the bug). In 2.1 it seems that this created too much complexity and the encoding operation has been integrated into the description of RSA OAEP encryption in section 7.1.1.

It is a requirement for the padding is to create an octet string (or byte array) that can fit into an integer of size $kLen-7$ or $kLen-8$ bits where $kLen$ is the key size in bits (not mentioned in RFC 2437).  RSA signature generation already uses a padding of $kLen-7$ bits so RSA encryption uses a padding that is $kLen-8$ bits. The reason why the padding must be smaller than the key size in octets is because RSA is defined for any key size, including a key size of, for instance, $kLen=1025$ bits. In that case the size of the octet strings will be $k=129$ bytes rather than $k=128$ bytes.

However, the integer calculations are still using a 1025 bit modulus. If one of the first 7 bits of the first bit would be set then the input of the calculation would be higher than the modulus, so the modular operation with the private exponent would not result in the same octet string.

Note that because of these kind of complexities many RSA implementations only handle key sizes or an 8 bit or 32 bit increment. It is strongly recommended to use a key size of 1024 bits or (preferably) higher with a key size of the form $2^x$ (e.g. $2048$) or $2^x + x^{x-1}$ (e.g. $2048 + 1024 = 3072$).

On the encoding function

This section explains another difference between 2.0 and 2.1: the use of a separate encoding function.

There was also a comment by Artjom B about the size of $dbMask$. The size of $dbMask$ is not different for the different descriptions of the encoding scheme. So this section should be seen as a supplement to the answer.

RSA signature generation already uses a padding of $kLen-7$ bits so RSA encryption uses a padding that is $kLen-8$ bits. This means that the result of the encoding must be an octet string of one octet less as the key size / modulus size in octets. This is why the encoding function is called using $k-1$:

EM = EME-OAEP-ENCODE (M, P, k-1)

and if you look carefully then you'll see that $emLen = k-1$ in the algorithms of EME-OAEP-ENCODE, for instance the message length should be $emLen-1-2hLen$.

Now in PKCS#1 v2.1 the EME-OAEP-ENCODE is missing; it has been integrated in the description of OAEP encryption itself. This has the disadvantage that other encryption schemes (for instance those based on ElGamal encryption) cannot directly reference the encoding operation within the standard. That is however not a main objective for a standard that describes RSA. On the other hand the standard is more clear because it doesn't need to mention $emLen$ at all; it can directly reference $k$, possibly avoiding off-by-one errors in implementations. Furthermore, it simplifies reading the description of OAEP, as readers do not have to switch back and forth between 7.1.1 and 9.1.1.1.


AES confused about how ShiftRows() step works Advanced Encryption Standard has a ShiftRows() operation that cyclically shifts last three rows of 16 byte block as shown here. This process is explained here in further detail.
But same documentation provides test vectors which have confused me a bit:
round[ 1].s_box    63cab7040953d051cd60e0e7ba70e18c
round[ 1].s_row    6353e08c0960e104cd70b751bacad0e7

So after shift row step, the 16-byte block has turned into a hex number labeled as round[1].s_row.
Converting into byte representation we have:
round[ 1].s_box  [99, 202, 183, 4, 9, 83, 208, 81, 205, 96, 224, 231, 186, 112, 225, 140]
round[ 1].s_row  [99, 83, 224, 140, 9, 96, 225, 4, 205, 112, 183, 81, 186, 202, 208, 231]

I had assumed that if we turn this 16x1 array into 4x4 matrix, first four elements would act as first row, elements 4..8 as second row and etc. in which case first four bytes [99, 202, 183, 4] should have remained unchanged.
However as we can see only elements at indices 0, 4, 8 and 12 are unchanged. Are definitions of rows and columns different in context of AES?
Here is how my implementation of AES transforms the hex labeled as round[1].s_box: 63cab70453d05109e0e7cd608cba70e1
[99, 202, 183, 4, 83, 208, 81, 9, 224, 231, 205, 96, 140, 186, 112, 225]
Edit: it is obvious that columns are transposed both before applying ShiftRow() and then after the operation is complete. This turned out to be the case for MixColumns() operation as well. Is there any particular reason for this?

The entire AES algorithm uses column-major order. So the first four elements are actually the first column, and not the first row.


Lightweight cipher using only 8-bit operations What is the most efficient (in cycles per byte) cryptographically secure symmetric cipher to implement using only 8-bit operations? Algorithms like TEA are great for embedded devices, but it is optimized for 32-bit operations. I am not looking for the most efficient implementation of an algorithm, but rather an algorithm which was designed with this in mind. The MCU in question is a 3.5 MHz Z80 with 16K RAM.

Looking this up, I found resources showing how to implement AES on 4-bit microcontrollers, and how to implement secure hashes on 8-bit microcontrollers, but neither of those answer my actual question.

I second Richie Frame's observation that AES is an excellent choice. I'd use AES-128 in CTR mode, which has the advantage that decryption is the same as encryption (thus is as fast, contrary to some other modes).

Update: SPECK, considered in this other answer, is good if compactness or speed per encryption for narrow block size are the choice criteria. SPECK-32 can be competitive with AES from the standpoint of cycles/byte on a Z80 (as asked in the question) because the state fits in registers. But I doubt SPECK-128 can be competitive with AES from the standpoint of cycles/byte on a Z80, because the  multi-bit rotation and large number of rounds are going to be show stoppers; and the state has to be in memory.

AES is good on 8-bit CPU (especially if a wide block is desired) because

It has a natural implementation with as the only data transformations: XOR between octets, and lookup of two 256-octet tables. Contrary to many modern ciphers, no word rotation is needed, which is extremely desirable in the context, in which that would be slow even when using assembly.
With an implementation (still natural) separating derivation of round subkeys from encryption itself, speed for large data will be hard to beat, thanks to the carefully crafted structure of AES.
Typical C compilers can generate fair code, and optimization is relatively easy.
With the precaution of locating the two 256-octet tables on page boundaries, a natural implementation on a CPU without data cache (such as the Z80) will typically exhibits no data timing dependency (but I have seen small caches, e.g. 16-octet, in the read path of Flash memory).

As illustration, here is reference code:

// ezAES: Public domain AES-128 encryption.
// C99-conformant. Well suited to 8-bit CPUs.
// CAUTION: vulnerable to fault attacks and side-channels, including
// Differential Power Analysis, and possibly data cache timing attack.

// Data types
typedef unsigned char octet_t;      // 8-bit octet
typedef octet_t ezAESblk_t[16];     // AES data block
typedef octet_t ezAESkey_t[16];     // key for AES-128
typedef octet_t ezAESsks_t[11*16];  // subkeys for AES-128

// Sbox for encryption, FIPS-197 figure 7
static const octet_t ezAESs[256] = {
    0x63,0x7c,0x77,0x7b,0xf2,0x6b,0x6f,0xc5,0x30,0x01,0x67,0x2b,0xfe,0xd7,0xab,0x76,0xca,0x82,0xc9,0x7d,0xfa,0x59,0x47,0xf0,0xad,0xd4,0xa2,0xaf,0x9c,0xa4,0x72,0xc0,
    0xb7,0xfd,0x93,0x26,0x36,0x3f,0xf7,0xcc,0x34,0xa5,0xe5,0xf1,0x71,0xd8,0x31,0x15,0x04,0xc7,0x23,0xc3,0x18,0x96,0x05,0x9a,0x07,0x12,0x80,0xe2,0xeb,0x27,0xb2,0x75,
    0x09,0x83,0x2c,0x1a,0x1b,0x6e,0x5a,0xa0,0x52,0x3b,0xd6,0xb3,0x29,0xe3,0x2f,0x84,0x53,0xd1,0x00,0xed,0x20,0xfc,0xb1,0x5b,0x6a,0xcb,0xbe,0x39,0x4a,0x4c,0x58,0xcf,
    0xd0,0xef,0xaa,0xfb,0x43,0x4d,0x33,0x85,0x45,0xf9,0x02,0x7f,0x50,0x3c,0x9f,0xa8,0x51,0xa3,0x40,0x8f,0x92,0x9d,0x38,0xf5,0xbc,0xb6,0xda,0x21,0x10,0xff,0xf3,0xd2,
    0xcd,0x0c,0x13,0xec,0x5f,0x97,0x44,0x17,0xc4,0xa7,0x7e,0x3d,0x64,0x5d,0x19,0x73,0x60,0x81,0x4f,0xdc,0x22,0x2a,0x90,0x88,0x46,0xee,0xb8,0x14,0xde,0x5e,0x0b,0xdb,
    0xe0,0x32,0x3a,0x0a,0x49,0x06,0x24,0x5c,0xc2,0xd3,0xac,0x62,0x91,0x95,0xe4,0x79,0xe7,0xc8,0x37,0x6d,0x8d,0xd5,0x4e,0xa9,0x6c,0x56,0xf4,0xea,0x65,0x7a,0xae,0x08,
    0xba,0x78,0x25,0x2e,0x1c,0xa6,0xb4,0xc6,0xe8,0xdd,0x74,0x1f,0x4b,0xbd,0x8b,0x8a,0x70,0x3e,0xb5,0x66,0x48,0x03,0xf6,0x0e,0x61,0x35,0x57,0xb9,0x86,0xc1,0x1d,0x9e,
    0xe1,0xf8,0x98,0x11,0x69,0xd9,0x8e,0x94,0x9b,0x1e,0x87,0xe9,0xce,0x55,0x28,0xdf,0x8c,0xa1,0x89,0x0d,0xbf,0xe6,0x42,0x68,0x41,0x99,0x2d,0x0f,0xb0,0x54,0xbb,0x16
    };

// Tabulation of (x<<1)^((x>>7)*0x1B)
static const octet_t ezAESt[256] = {
    0x00,0x02,0x04,0x06,0x08,0x0a,0x0c,0x0e,0x10,0x12,0x14,0x16,0x18,0x1a,0x1c,0x1e,0x20,0x22,0x24,0x26,0x28,0x2a,0x2c,0x2e,0x30,0x32,0x34,0x36,0x38,0x3a,0x3c,0x3e,
    0x40,0x42,0x44,0x46,0x48,0x4a,0x4c,0x4e,0x50,0x52,0x54,0x56,0x58,0x5a,0x5c,0x5e,0x60,0x62,0x64,0x66,0x68,0x6a,0x6c,0x6e,0x70,0x72,0x74,0x76,0x78,0x7a,0x7c,0x7e,
    0x80,0x82,0x84,0x86,0x88,0x8a,0x8c,0x8e,0x90,0x92,0x94,0x96,0x98,0x9a,0x9c,0x9e,0xa0,0xa2,0xa4,0xa6,0xa8,0xaa,0xac,0xae,0xb0,0xb2,0xb4,0xb6,0xb8,0xba,0xbc,0xbe,
    0xc0,0xc2,0xc4,0xc6,0xc8,0xca,0xcc,0xce,0xd0,0xd2,0xd4,0xd6,0xd8,0xda,0xdc,0xde,0xe0,0xe2,0xe4,0xe6,0xe8,0xea,0xec,0xee,0xf0,0xf2,0xf4,0xf6,0xf8,0xfa,0xfc,0xfe,
    0x1b,0x19,0x1f,0x1d,0x13,0x11,0x17,0x15,0x0b,0x09,0x0f,0x0d,0x03,0x01,0x07,0x05,0x3b,0x39,0x3f,0x3d,0x33,0x31,0x37,0x35,0x2b,0x29,0x2f,0x2d,0x23,0x21,0x27,0x25,
    0x5b,0x59,0x5f,0x5d,0x53,0x51,0x57,0x55,0x4b,0x49,0x4f,0x4d,0x43,0x41,0x47,0x45,0x7b,0x79,0x7f,0x7d,0x73,0x71,0x77,0x75,0x6b,0x69,0x6f,0x6d,0x63,0x61,0x67,0x65,
    0x9b,0x99,0x9f,0x9d,0x93,0x91,0x97,0x95,0x8b,0x89,0x8f,0x8d,0x83,0x81,0x87,0x85,0xbb,0xb9,0xbf,0xbd,0xb3,0xb1,0xb7,0xb5,0xab,0xa9,0xaf,0xad,0xa3,0xa1,0xa7,0xa5,
    0xdb,0xd9,0xdf,0xdd,0xd3,0xd1,0xd7,0xd5,0xcb,0xc9,0xcf,0xcd,0xc3,0xc1,0xc7,0xc5,0xfb,0xf9,0xff,0xfd,0xf3,0xf1,0xf7,0xf5,0xeb,0xe9,0xef,0xed,0xe3,0xe1,0xe7,0xe5
    };

// Round constants
static const octet_t ezAESr[10] = {
    0x01,0x02,0x04,0x08,0x10,0x20,0x40,0x80,0x1b,0x36
    };

// encrypt one block
void ezAESenc
    (
          ezAESblk_t    oC, // ciphertext output
    const ezAESblk_t    iP, // plaintext input
    const ezAESsks_t    iS  // round subkeys
    ) {
    ezAESblk_t vB;          // current state of the block
    ezAESblk_t vT;          // temporary
    octet_t vn;

    // first AddRoundKey
    vn = 16;
    do {
        --vn;
        vB[vn] = iP[vn] ^ iS[vn];
    } while( vn!=0 );

    // round loop, started 10 times; exits with break in the middle of the last round
    for( ; ; ) {

        // ShiftRows and SubBytes, performed 10 times
        vT[ 0] = ezAESs[vB[ 0]]; vT[ 1] = ezAESs[vB[ 5]]; vT[ 2] = ezAESs[vB[10]]; vT[ 3] = ezAESs[vB[15]];
        vT[ 4] = ezAESs[vB[ 4]]; vT[ 5] = ezAESs[vB[ 9]]; vT[ 6] = ezAESs[vB[14]]; vT[ 7] = ezAESs[vB[ 3]];
        vT[ 8] = ezAESs[vB[ 8]]; vT[ 9] = ezAESs[vB[13]]; vT[10] = ezAESs[vB[ 2]]; vT[11] = ezAESs[vB[ 7]];
        vT[12] = ezAESs[vB[12]]; vT[13] = ezAESs[vB[ 1]]; vT[14] = ezAESs[vB[ 6]]; vT[15] = ezAESs[vB[11]];

        if ( (vn += 16)==10*16 )
            break;

        // MixColumns and AddRoundKey, performed 9 times
#define EZAESMA(x) \
    vB[x+2] = vT[x+0]^vT[x+1];                  /* 1 1 0 0 */               \
    vB[x+3] = vT[x+2]^vT[x+3];                  /* 0 0 1 1 */               \
    vB[x+0] = ezAESt[vB[x+2]]^vT[x+1]^vB[x+3]   /* 2 3 1 1 */ ^iS[x+0+vn];  \
    vB[x+2] ^= ezAESt[vB[x+3]]^vT[x+3]          /* 1 1 2 3 */ ^iS[x+2+vn];  \
    vB[x+3] = vT[x+1]^vT[x+2];                  /* 0 1 1 0 */               \
    vT[x+3] ^= vT[x+0];                         /* 1 0 0 1 */               \
    vB[x+1] = ezAESt[vB[x+3]]^vT[x+2]^vT[x+3]   /* 1 2 3 1 */ ^iS[x+1+vn];  \
    vB[x+3] ^= ezAESt[vT[x+3]]^vT[x+0]          /* 3 1 1 2 */ ^iS[x+3+vn];
        EZAESMA( 0)
        EZAESMA( 4)
        EZAESMA( 8)
        EZAESMA(12)
#undef EZAESMA
        // here the content of vT is immaterial
        }

    // last AddRoundKey
    vn = 16;
    do  {
        --vn;
        oC[vn] = vT[vn] ^ iS[10*16+vn];
    } while( vn!=0 );
}

// prepare round subkeys
void ezAESkey (
          ezAESsks_t    oS, // round subkeys output
    const ezAESkey_t    iK  // key input
    ) {
    octet_t vj, vk;

    // first subkey is the key
    vj = 16;
    do {
        --vj;
        oS[vj] = iK[vj];
    }
    while ( vj!=0 );

     // for each 4-octet word of each 10 other subkeys
    vk = 0;
    do  {
        if( (vj&15)==0 ) {
            oS[16+vj] = ezAESs[oS[13+vj]]^oS[  vj]^ezAESr[vk++];
            oS[17+vj] = ezAESs[oS[14+vj]]^oS[1+vj];
            oS[18+vj] = ezAESs[oS[15+vj]]^oS[2+vj];
            oS[19+vj] = ezAESs[oS[12+vj]]^oS[3+vj];
            }
        else {
            oS[16+vj] = oS[12+vj]^oS[  vj];
            oS[17+vj] = oS[13+vj]^oS[1+vj];
            oS[18+vj] = oS[14+vj]^oS[2+vj];
            oS[19+vj] = oS[15+vj]^oS[3+vj];
            }
    } while( ( vj += 4)!=10*16 );
}

// Minimal test and demo. Returns 0 for OK, 1 for error.
int ezAESchk(void) {
    // test values from FIPS-197 appendix C.1
    const ezAESkey_t key = {
        0x00,0x01,0x02,0x03,0x04,0x05,0x06,0x07,0x08,0x09,0x0a,0x0b,0x0c,0x0d,0x0e,0x0f
    };
    const ezAESblk_t plaintext = {
        0x00,0x11,0x22,0x33,0x44,0x55,0x66,0x77,0x88,0x99,0xaa,0xbb,0xcc,0xdd,0xee,0xff
    };
    const ezAESblk_t ciphertext = {
        0x69,0xc4,0xe0,0xd8,0x6a,0x7b,0x04,0x30,0xd8,0xcd,0xb7,0x80,0x70,0xb4,0xc5,0x5a
    };
    ezAESsks_t subkeys;
    ezAESblk_t result;
    octet_t j, r;

    // derive the round subkeys
    ezAESkey( subkeys, key );

    // encrypt
    ezAESenc( result, plaintext, subkeys );

    // compare result and known-good ciphertext
    for( j = r = 0; j<16; ++j)
        r |= result[j] ^ ciphertext[j];

    return r!=0;    // 0 for OK, 1 for error
};


Physical entropy source: How many bits entropy per byte is sufficent? 8 bit / byte  would be perfect obviously.

head -c 1M /dev/urandom | ent

gives ~ 7.9998 bits per byte.

Now, if I have a physical entropy source, how much entropy is sufficent. E.g. my sound card produces 7.8 to 7.9 bits per byte for 1M raw data generated via randomsound.

My main question: Is this amount of entropy sufficient to inject it into the kernels entropy pool?

Clearly, the data from the sound card is internally scrambled again before it is used to produce random numbers. In the end, the resulting entropy is similar to 7.999 bits per byte.

First, take note of my answer to the question Estimating bits of entropy. A key phrase therein:

  You'll never be able to look at a bitstream without knowing the distribution and say "there are X bits of entropy here."

The ent program doesn't know the distribution of the data it's looking at; instead it performs some statistical tests that any sufficiently-long random bitstream will pass with overwhelming probability. Here, I mean "pass" in the sense of having an "estimated entropy" near 8 bits per byte, which is exactly what truly random data has.

So,
$$\text{bitstream is random} \implies \text{bitstream passes ent}$$
is about all we can say. Thus the (hidden) premise of your post - namely that because ent claims your soundcard's data looks random, it actually is random - is faulty. ent cannot be used to determine whether data is actually random. As an example, if a program has a fixed output, that output's entropy is 0 bits; but ent will declare otherwise since it does not have this external knowledge.

This is probably unnecessarily pedantic, but cryptography is a subtle science, and I think we need to acknowledge the particulars.

With all of that out of the way, can you feed your soundcard data into the kernel's random pool? So long as you trust that the soundcard hasn't been tampered with and actually is reporting random data, sure! For multiple reasons:

The soundcard isn't the only source of random data, so even if it is somewhat predictable, oh well - as long as it's not a malicious privileged device
If you feed random data into the Linux kernel as non-root, it doesn't use that source to increase the "entropy counter" at all: so it may be that your soundcard will act as a random source anyways, but not necessarily be counted as "random" by the kernel (n.b.: the entropy counter is of dubious value, but I am mentioning this for completeness)
The Linux kernel mixes and stirs "random" sources before presentation; it already doesn't much trust the sources to be uniformly random, etc

So with these reasons in mind, throwing any data you'd like into the kernel's random pool should be safe, even if the data isn't great. The exception is data that is carefully crafted with potential knowledge of the other random sources, as explained in the above link, but such a malicious source is a non-issue for most folks.


Getting unlimited amount of signatures - Risk? Lets suppose we have a communication protocol given where messages $(1)$ and $(2)$ are send over an unsecure network.

There are some prerequisites like distributed certificates etc., but they should not matter for this question).

Message (1) is send as plaintext from $A$ to $B$ and does contain the identity of $A$. Party $B$ responds with a signature over the received identity and some other data (e.g. a public DH key) and sends it over to $A$.

A protocol that starts like this design allows an attacker to get a lot of signatures (as much as needed) and the input is even something under his control (the identity of $A$).

In my opinion this may open door to a lot of attacks the attacker can use. I don't know any but I can imagine that have been some and this kind of design should always be avoided.

I am open for any kind of comment on this. Especially if there were some relevant attacks in the past.

In my opinion this may open door to a lot of attacks the attacker can use.

Actually, public key signatures are designed to be used securely like this.  When we design a signature method, we assume that the attacker can ask for a large number of messages of his choosing to be signed, and still try to ensure that the attacker cannot generate a valid signature for a message that he did not ask to be signed (or recover the private key) - if someone can show a method, we consider that signature method as broken, and discard it.

However, there is one possible avenue for the attacker; if he submits the identity $Eve$, and gets the signature for $(Eve, DHPublicKey)$, he now has a valid message/signature pair, which would verify just fine.  If he can use that signature somehow in an attack, well, that's one thing that the signature method doesn't protect you against.  Of course, it's possible that there is no such attack (for example, if the attacker doesn't know the $DHPrivateKey$ that corresponds the to $DHPublicKey$ in your message), however that is something you need to consider.


Looking for a Non-textual hashing function Pardon my terminology, but is there a hashing function of some sort which accepts a string as input and generates a non-textual output of some sort, or perhaps a unique output that can be used to draw a visual representation of the output.

I refer it to as "hash" because the same output should always lead to the same visual representation of the output i.e. behave like a hashing function, even though my use-case is highly tolerable towards collision as its only meant to uniquely identify in a small group of inputs when compared to another small group of inputs, and it need not be absolutely unique across the vast range of inputs that are possible. Though even the slightest change in input, should change the visual output considerably.
Objective: I am exploring the possibilities of using a visual cue derived from random strings that can aid in differentiation and quick identification in a small group. Eg: How CryptoKitties project generates a visual image of a cat by their genome representation which is just a textual input.
Use-case: I am building an air-gapped multi-accounts multi-currency cryptocurrency wallet which is a 2-device system (Vault + Wallet). Vault boots up as an ephemeral instance of OS, so it doesn't store any information across boot instances. So accounts that are once created in vault and imported into wallet using an xpub key and labels are added there. Vault doesn't and can't store any labels associated with the accounts. So when the same accounts are derived on the vault program upon initialization on next boot, I am trying to represent every account (essentially the xpub key by a visual character so that they are matched with the accounts on the wallet by simply looking at them without any communication required.

This is a pure encoding problem, as @kelalaka said. Take any reasonable hash algorithm like SHA-512. You have all qualities that you mentioned - not reversable, low probability of collisions, etc. What needs top be done, is to encode this hash into a picture.
To algorithm: look for instance at automatic generation of avatars at Stack Exchange to get one of possible simple ideas.
If you use SHA-512: The hash consists of 64 bytes. Consider it as a matrix of 8x8 elements, for each element define 256 values. These 256 values can be a combination of simple elements, e.g. 4 elements each having 4 states.


ECDH or RSA more secure for symmetric key wrapping? Suppose a message is encrypted with a symmetric block cipher with a random key. RSA is often used to wrap the symmetric key using the recipient's public key.

In this case, the size of the message is increased, as the block size of the RSA encryption (depending on the modulus size) is much bigger than the actual size of the symmetric key. This also leads to using some special padding schemes (like OAEP).

For example: Assuming we want 128-bit security - 128-bit symmetric key, encrypted with 2048-bit RSA yields 256 byte output, which is 16 times the size of the symmetric key.

On the other hand, when the increase in size is an issue, one can make use of ECDH (with some safe curve). Take the recipient's public key $rP$, generate a random value $s$, compute $rsP$ and use KDF to obtain the symmetric key from its $x$-coordinate. The encrypted message is sent along with the sender's public key $sP$.

In this case (for 128-bit security), one uses some safe curve over 256-bit prime field, the size of $sP$ $x$-coordinate is 32 bytes, which is twice the size of the symmetric key.

Here comes my question - besides being more computationally demanding (two scalar point multiplications vs. one exponentiation), are there any additional security considerations one should take when substituting RSA with ECDH in this case?

Yes, there are a few reasons to prefer ECDH over RSA:

ECDH will perform much better;
ECDH can provide forward security when used with ephemeral key pairs without a large performance overhead for creating those key pairs;
ECDH should be impervious to most oracle attacks, i.e. timing based padding oracle attacks on OAEP.

For the forward secrecy you require two ephemeral key pairs (to perform ephemeral-ephemeral Diffie-Hellman). Ephemeral key pairs cannot be used for authentication, so you require additional steps if you wanted to use a static ECDH key pair for this.

There are a few drawbacks as well:

RSA is generally much better understood;
there is some discussion about EC security and domain parameters: you may need to validate the public key point or use one of the Safe Curves.

Although you may have to perform more modular calculations - including modular exponentiation - for ECDH, the modular calculations are over much smaller numbers, leading to a much better performing algorithm, especially regarding calculations that use the private key.

Textbook or raw RSA is perfectly able to handle big secret keys; any normal sized secret key can be directly encrypted with a normal sized RSA public key. It's just required to interpret the padded secret key as a number. RSA padding schemes such as OAEP are required to obtain security.


Advanced Access Content System (AACS) and Subset Difference techniques for Broadcast Encryption I'm trying to get a grasp on AACS and Subset Difference (archived version with images) for a project I'm working on and am having a hard time coming up with a technically valid layman explanation, let alone implementation.

Is it fair to say that the content is encrypted once per public key (device key), resulting in several copies of the movie on the same DVD?...  given that a DVD player can only read one (singular) copy of each of those encrypted streams?

What s a better explanation?

There is no "public" key in AACS (at least, no in the part which uses SDR).

Each movie is symmetrically encrypted with a movie-specific key, and stored as is on the disc. All copies of a given movie use the same key; indeed, all copies of a disc are bit-to-bit identical (it would not be economically sound to do otherwise). Two distinct movies, however, use distinct keys.

From that point, the problem of giving access to the movies to all "allowed" players (and only to them) is reduced to the problem of giving them access to the movie encryption key. A movie encryption key is small (a few dozen bits), an encrypted movie is huge (several gigabytes); presumably, keys will be easier to handle. On the disc, physically, there is only one instance of the movie itself.

Each player has its own key. So one model is the following: the disk contains the movie, encrypted with the movie key $M$, and a complete set of $E_P(M)$ (movie key $M$ encrypted with player key $P$). Each player would decrypt "his" $E_P(M)$ to retrieve $M$ and decrypt the movie. If, at some point, a given player key $P$ is detected to have been leaked (e.g. there is some downloadable software which uses that key to decrypt movies), then the movie editors just have to stop including $E_P(M)$ for that key $P$ in the discs they press (we would say that the offending key is revoked).

Now, the problem with that model is that there are billions of player keys (for all the current and future players, because we want disks sold now to be playable on systems which will be built next year) so the total size of all these $E_P(M)$ would exceed the disk capacity (it would need several dozen of gigabytes, more than the movie itself). So the tree-like structures come into play. The player keys all come from a giant tree structure. The needed size on each disc is in $O(\log n) + O(r)$ where $n$ is the number of player keys in circulation (including future keys) and $r$ is the number of revoked keys. This is small enough for existing discs (in particular Blu-ray discs, which use AACS) as long as there are not too many revoked keys (the hope is that revocation will remain a rare occurrence).


RSA signing security I'm curious about the security of RSA signing with the same public private key pair when the same message is sent multiple times. It's my understanding that once you generate the hash of the message you wish to send, that you then sign this message with your RSA private key, then transfer both this signed hash and the original message. The receiver then uses the original message to generate their own hash and compare against the result of decrypting the signed hash with the server's public key. Now that you know my understanding of the process on to the question.

Scenario: A client connects to a server and retrieves a command as well as a signed hash of this command. The server's public key is hard coded into the client. Only this server should be able to issue commands, commands will be reused

1) Is it possible for an attacker to simply log the hash of a command and then replay this hash on a server of their own thus defeating signing?

2) Assuming question one is correct how can this be prevented, I can't see a random index, being added on the end of the command, working because the server must send the original message thus exposing the "secret index" that was intended to change the hash each time.

I understand how RSA is secure when data is only sent once, but when it's sent multiple times how is it/can it be made secure? I'm looking for a possible solution. Thanks for reading.

Timestamps, as mentioned by user93353, are one possible answer.  The drawback is that they require synchronized clocks, which can't always be assumed.

Another possible approach to prove liveness (that is, that this isn't a replay) is for the receiver to select a random value (a "nonce"), send that to the server, and have the server sign the command concatenated with the nonce.  This also foils a replay; replays cannot work unless the receiver repeats the nonce.


Why use PBKDF2 over SHA-512 to derive AES encryption key? Suppose I am using user passwords to derive AES-128-CBC encryption key. This key will be used to encrypt some sensitive data for the user so that even the website owner / operator can not decrypt it.

Then why should I use PBKDF2 over taking the first 128-bit of the SHA-512 output over the salt and password?

If I use PBKDF2, then what is recommended iterations nowadays for PBKDF2 at this date?

The problem with passwords or, more succinctly pass phrases, is that they are often relatively easy to guess. Password strength - or rather the lack of it - is a common problem. The strength of a password is not such a big deal if there is some kind of control over how the password can be used (e.g. a PIN is relatively easy, but you are only allowed 3 tries). However, if they are used to generate the key then the ciphertext is commonly believed to be accessible by an adversary, leaving the password guessing vulnerable to an uncontrolled offline attack.

Cryptographic hashes have been designed to be not just one way, but also to be rather fast. That simply means that for an adversary it is easy to test many inputs to derive the correct key. Generally it only takes very little time to test a key as well, since it is not required to decrypt a large amount of data with it; if the ciphertext is large then the adversary can still just decrypt a small part of it. So an adversary has to do a limited amount of work to find a key.

The iteration count - or more generally - the work factor is there to slow the adversary down. Any work that you do once for each password, the adversary has to do for each guess. That still only provides an additional amount of work compared to the situation with a cryptographic hash, but beggars cannot be choosers. So this is what passwords hashes or Password Based Key Derivation Functions have been designed to do: "strengthen" or "stretch" the password in such a way that they are relatively harder to guess.

As said, PBKDF's only provide limited protection against adversaries. Moreover, since ciphertext can be stored, the protection diminishes when faster computers become available. Attacks can also be very easily parallelized. So I would very much try and avoid password based encryption all together.

There are some ways of mitigating the problem of course. For one, you can use a password manager and a very complex password that has a similar strength of a secret key (say 96 bits or higher). That way you may not need a PBKDF to strengthen the password (although entering the password may become more cumbersome).

An other way of mitigating this is to encrypt a private key instead. Now you access to the private key to decrypt the ciphertext. You don't need access to it during encryption.


Is SHA-1 secure when used to implement a PRNG I read SHA-1 is still a secured hashing function with no collision found as of now. However, it's just a matter of time for someone to come up with such a collision or attack. Therefore, in new projects, it is recommended to use SHA-256. SHA-512 is even better.

In Java, we still use the "SHA1PRNG" algorithm in the SecureRandom class for the purpose of generating IV (let's say for CBC).

Is SHA-1 secure enough as hash function within a PRNG to generate an unpredictable IV for CBC? Or is SHA-256 recommended, even for a PRNG?

I read SHA1 is still a secured hashing function with no collision found as of now.

You read an old text, this is not the case anymore since SHA-1 was SHAttered.

In Java, we still use SHA1PRNG algorithm in SecureRandom class for the purpose of generating IV (let's say for CBC).
Is it enough secured as a PRNG generating unpredictable IV for CBC? Or even for a PRNG, SHA256 is recommended?

SHA-1 is still fine for key derivation, HMAC, MGF1 based padding and indeed random generation and many other use cases that do not suffer from collision attacks.
That said, attacks can only get better, never worse, so using a  more modern hash is always recommended. When it comes to random number generation the seeding is much more likely to be problematic though, and you should definitely make sure that your systems RNG is running correctly.
And, when it comes to Java's SecureRandom, you may want to consider my answer on StackOverflow and not use (or at least indicate) "SHA1PRNG" at all.


Purpose of DES parity bits DES has a 64-bit key size, but only 56 of those are used during encryption. The other 8 are "parity bits".

What was the intended purpose of the party bits, and why are they no longer used in modern ciphers?

They are there to check if the key was indeed correctly retrieved. It could for instance be that the key is a result of key decryption or key agreement. In that case, or simply during transmission, wrong keys are used. According to NIST FIPS 46-3:

  The 8 error detecting bits..."

Or even better, Wikipedia states ANSI INCITS 92-1981), section 3.5:

  One bit in each 8-bit byte of the KEY may be utilized for error detection in key generation, distribution, and storage. Bits 8, 16,..., 64 are for use in ensuring that each byte is of odd parity.

So you see, they're there to protect against errors reinstating/recreating the key.

Nowadays transmission errors are usually taken care of at the transport layer. As e.g. TCP/IP (and most other network protocols) already deliver a reliable transport mechanism the need for the parity bits has been strongly reduced. Things like parity checking are not seen as part of a cipher definition. Nowadays it is seen as an unnecessary nuisance, complexity where it isn't required.

In the unlikely event that you'd ever need to perform parity or CRC checking it is of course easy to add the necessary bits; as long as you strip them away again before using the key.


8th SharifCTF — What is the advisable way to recover the key of single round DES here? I am participating in the 8th SharifCTF competition and have a related question:

I have 1000 plaintext and its ciphertext, which has been encrypted with  DES algorithm (only 1 round).

Now, how can I get this 64-bit hexadecimal key?

Can we use a known plaintext attack, or would another attack be more advisable? If, which one?

Can we use a known plaintext attack

Considering that you have 1,000 plaintext-ciphertext pairs, you should be able to.

Known plaintext attack(s)

Try applying linear cryptanalysis, DES is relatively weak against it.

Alternatively, you could try differential cryptanalysis; DES is usually considered to be relatively strong against it, but with only a single round you might still make some headway.

  or would another attack be more advisable? If, which one?

Chosen plaintext attack

Do you have access to an encryption oracle? If not, then you can't perform a chosen-plaintext attack.

Chosen ciphertext attack

Do you have access to a decryption oracle? If not, then you can't perform a chosen-ciphertext attack.

Slide attack

Since the cipher is a reduced round variant that uses only a single round, you cannot use a slide attack.

Brute force

You could probably rent a supercomputing cluster and simply crack the key with brute force. This is probably the slowest, most expensive, and least enlightening technique, but it will work against regular (not triple) DES.


Digital signatures using a partially public key I'm thinking to sign a message using a key that is made up of a publicly shared key and a privately shared key. The operation for mixing the two keys could be concatenation, if it suffices.

To formalise it a bit, the signature is essentially $$MD5(msg, concat(pub, priv))$$

Since the entire key isn't (completely) known to the public, are such signatures considered secure? Should the merged key be hashed and/or derived from a KDF before applying it to MD5 (or HMAC for that matter)?

Perhaps, something like $MD5(msg, concat(KDF(pub, n), priv))$ where $n$, the number of rounds, is randomly derived from the public key? The rationale is that even if the attacker knows the public key, they won't be able to derive n, which protects the private key from some kind of text attack.

A few things.  First of all, MD5 is broken, and no longer suitable for cryptographic purposes.  Instead, prefer newer algorithms, like those from the SHA-2 family (SHA-256, SHA-512, etc).

Second, the term "signature" in cryptography is defined more narrowly than you would expect.  It specifically refers to situations where there is a public key (the "verification" key), and a private key (the "signing" key).  Everyone can verify a signature themselves, if they have the public key.

It sounds like what you're actually after is a Message Authentication Code (MAC).  MACs use a single "secret key" for both signing and verifying, instead of having separate keys for each purpose.

Since that's the behaviour you want (assuming I understood your comments correctly), it's best to use an algorithm designed for that purpose, such as HMAC-SHA256.


converting finite field elements to octet strings I need to convert elements of the finite field $GF(p^k)$, where $p$ is an odd prime, to octet strings.

To be more precise, I want to include elliptic curve points over $GF(p^2)$ in a Subject Public Key Info of an X.509 certificate.
In the document IEEE P1363 there is a FE2OSP function which is probably not usable for that case.

Do you know of any well accepted standard which describes that encoding?

Ok,
if there is no standard, then "I do it my way":

Let $i$ be a root of a fixed minimum polynomial of $GF(p^2)$ and $x$ be an element in $GF(p^2)$. Then $x:= x_1+x_2*i$ can be represented as a vector $(x_1,x_2) \in GF(p)^2$.
Now convert $x_1$ and $x_2$ with the FE2OSP function form IEEE P1363 and concatenate them
$FE2OSP(x_1)|| FE2OSP(x_2)$.

An elliptic curve point $(x,y) \in E(GF(p^2))$ can then be represented either compressed or not compressed.

not compressed:

$04|| FE2OSP(x_1)|| FE2OSP(x_2)|| FE2OSP(y_1)|| FE2OSP(y_2)$

compressed:

$02|| FE2OSP (x_1)|| FE2OSP (x_2)$ if $LSB(FE2OSP(y_1))=0$
$03|| FE2OSP(x_1)|| FE2OSP (x_2)$ if $LSB(FE2OSP (y_1))=1$