Can AES decrypt with a wrong key? The title is asking the question in layman terms, but what I really mean to ask is this:

Let $x \in \lbrace 0,1 \rbrace^{128}$ (an arbitrary input block) and let $K \in \lbrace 0, 1 \rbrace^{128}$ (an arbitrary key for 128-bit AES). Let's mark AES decryption with $AES_K^{-1}$. My questions are:

Is $AES^{-1}_K$ defined for (arbitrary) input $x$? (i.e. Is AES onto $\lbrace 0, 1 \rbrace ^{128}$ for any key?)
If so, is $AES_K( AES^{-1}_K (x) ) = x$ ?

Are those questions trivial or do they require proof?

AES-128 uses the full set $\{0, 1\}^{128}$ as keyspace, and for each key the blockcipher is defined for each input block in $\{0, 1\}^{128}$. The same goes for AES-256, but it uses a 256-bit keyspace (but still a 128-bit block).

So the answer to 1 is yes.

For 2, we have this equation:

$$AES_K(AES_K^{-1}(x)) = x$$

We can decrypt both sides:

$$AES_K^{-1}(AES_K(AES_K^{-1}(x))) = AES_K^{-1}(x)$$

Because we know that $AES_K^{-1}(AES_K(a)) = a\:$ by the definition of the inverse we can cancel out an encryption/decryption cycle on the left hand side:

$$AES_K^{-1}(x) = AES_K^{-1}(x)$$

So it's true.


Correlation among Psuedo Random Sequences generated from seeds which are correlated I want to see and mathematically verify how PN sequence generated by LFSR or maximum length codes would correlate (auto-correlation and cross correlation) for seeds of varying correlation.

Say I want to generate 512 bits of PN sequence on two sides (A and B). To hide the possible output from eavesdropper I choose some seeds (which can be generated by both A and B simultaneously). The issue is the seeds(sequence of 512 bits) generated at various instants of time are correlated with previous time instants.

I want to:

  See how correlation in input seed affects correlation in output

Is there any paper or reference literature survey for same?

EDIT

My research efforts...

As of now I am studying properties of PN sequence generators. In my research I have a source which generates correlated sequences of various degrees. I want to analyse what happens to PN sequence generated using those seeds.

Caveat: LFSRs outputs are vulnerable to known plaintext attacks using the Berlekamp Massey algorithm.

Given a maximal length sequence $s(t)$ of period $2^n-1$ generated by a primitive LFSR, all its windows of length $\ell \geq n$ are unique so partial period correlation of such lengths can uniquely determine the phase, thus the seed.

All primitive LFSR sequences of this length are obtainable by regular decimations of this sequence, i.e., $s(dt)$ where $gcd(2^n-1,d)=1.$

So this is an exploitable correlation.

Another relevant property is the shift and add property

$$s(t+k)\oplus s(t)=s(t+z(k))$$

that comes from the fact that the maximal length sequence and its cyclic shifts together with the all zero vector form a linear code. This is another source of correlation.Here $$a^{z(k)} =1+ a^k$$ defines the so called Zech logarithm $z(\cdot)$, if we use the trace representation $$s(t)=Tr(a^t)$$ with $a \in GF(2^n).$

The book by Golomb and Gong and a survey by Sarwate and Pursley in the Proceedings of the IEEE are good places to start.


Is there an encryption scheme that is url-safe AND compact? I want to be able to encrypt some data like JohnSmith@domain.com|1234|A in a form that I can send to a user as a clickable link like:
https://example.com/click/this/NiUGgvamNOVmI1SzlTN0ZIRlQ0WklCazI3LzRxY09RVFRjOTByZ1o1OFJyT0lUeWd3PQ2....

Then the user clicks the link and when I receive the token, I can decrypt it and operate on the data.
I'm using the RijndaelManaged cipher, with a password and salt, and then Base64 encoding and then UrlToken encoding it, to avoid characters that would cause trouble in a url.
This all works fine, but it creates really long tokens, about 4 times the length of the original data, which makes sense, as it's smearing the information across all 256 possible bytes and then reducing to only 64 possible bytes for output.
What I am wondering is if there's a way to encrypt the data, possibly not as securely, but enough for limited application, that would not be 4 times longer than the input string. Could there be an algorithm that encrypts text AS text and without requiring vastly more size?

TL;DR You should use format-preserving encryption which is designed to solve your problem.
There are various solutions some of which are easier than others to implement. I'll estimate their sizes based on your example token and url.
Some less than perfect solutions
As suggested in the comments, a bitwise stream cipher (such as ChaCha) or block cipher in streaming mode (such as AES-CTR) followed by base 64 encoding and url tokenising will only make your string about 42% longer plus any IV overhead. You may or may not want to worry about the ability of the user to modify the data. A user who can identify their token data could then forge tokens of the same or shorter length.
Estimated token length with 128-bit IV: 61 characters.
Estimated url length: 92 characters.
By adding a MAC you can defend against token manipulation but add another 21-22 characters to both lengths. Modern authenticated encryption methods may integrate authentication codes automatically.
You can shave off some characters with shorter IVs and MACs, but I wouldn't recommend going below 64-bits. These would save you 10-11 characters.
Estimated token length with 64-bit IV: 50 characters (61 with 64-bit MAC).
Estimated url length: 81 characters (92 with 64-bit MAC).
If we assume that your tokens use a character set of size 65 {A-Za-z0-9@|.} You could index the set and use a mod 65 stream cipher which would preserve the character set. Again IVs and MACs would be advisable, but could be expressed in the character set. There aren't any off the shelf mod 65 stream ciphers, but one could be constructed based on established stream cipher designs.
Estimated token length: 40 characters (52 with short MAC)
Estimated url length: 71 characters (73 with short MAC)
My laptop browser has a 65 character address bar and so I like urls with fewer than 64 characters to inhibit malicious url suffixes such as @http://evil.com/malware.exe. None of these solutions manage to achieve this for your example.
The designed and standardised solution
You can create url-friendly tokens and then use format-preserving encryption for 0 overhead. NIST have a standard for FPE and googling for "FF3-1 open source" should find an implementation in your language of choice.
Estimated token length: 27 characters
Estimated url length: 58 characters
58 character urls are still longer than the address bar on my phone browser, but this is still pretty good.


Why does my attempt at RSA break? I have that $N = 798$, $p=2$, and $q=399$. I choose $e$ such that $\gcd(e,(p-1)(q-1))=1$ where $e=7$. I, then, choose $m = 123$. Thus, $c=123^{7}\bmod798=669$, which is my ciphertext. After, I try $d=7^{-1}\bmod398=57$. I, then, get the wrong result that $m'=669^{57}\bmod798=729$ which is not my original message $m$.

Why is this? I can't seem to understand why RSA would break. Does RSA break if either $p$ or $q$ is 2 and the other is a composite?

Since your q is composite with factors 3,7,19 we get $\phi(q)=(3-1)*(7-1)*(19-1)=216$ and not 398 The rest of the calculation follow as in the question.

And since $p=2$ we get also $\phi(n) = 216$

As a result we also get $d=e^{-1}=7^{-1}=31 \bmod 216$

And we can verify that $669^{31} \bmod 798 =123$ as expected.


How to implement HMAC SHA-256 I am trying to figure out how the HMAC SHA-256 hashing algorithm works. I know that we have to use the following:

H (K ^ opad)|| H ((K ^ ipad)|| text)).

The problem that I am facing is I think of basic understanding of the above. As far as I know, SHA-256 takes in “character input”. The key that I am using is of 256 bits in size and that leads (K^ipad) to be a 512 bit number. How do I use that to get the desired hash?

SHA-256 is defined for inputting and outputting binary data using bits. Most libraries only perform calculations based on byte input instead of bit input though. So in general, SHA-256 operates on bytes, not on characters.

You need to explicitly encode your characters to to bytes using character encoding such as UTF-8 to use SHA-256. Some platforms have an implicit conversion to bytes, or even equate characters with bytes (the char type in C/C++), but it is better to use explicit conversion none-the-less.

Never confuse characters and bytes, it's the source of about half of the problems with cryptography on stackoverflow (as well as countless bugs on system in the field, not just concerning cryptography).

When comparing the implementation of your library, don't test against random sites on the internet; they usually get encoding/decoding wrong as well. Instead compare with test vectors that do make clear which bytes are actually processed.

After you succeed with the official test vectors, you could perform string comparison with known good libraries (Java, OpenSSL etc.) using code for which the string encoding is explicitly specified.


Why doesn't CTR mode require blocking? I've been reading a bit about block cipher modes and I have a relatively straightforward question regarding CTR.  In essence, I was hoping you guys would be kind enough to validate my understanding of things.

As I understand it, CTR does the following:

Take the first output of the nonce (let us assume an incrementing int for our purposes)
Encrypt the nonce with the key.  CTR requires that the key and the nonce be of identical size.
Perform some lossless operation between encrypted nonce and a portion of plaintext (e.g.:  XOR)
Increment nonce
Repeate ad libitum

Here's what I don't understand.  CTR is supposed to transform a block cipher into a stream cipher, but don't you still have to operate block-by-block for step 3?

What am I missing?

While you do operate block-by-block when generating the pseudorandom stream, the actual encryption step (i.e., the XOR) is bitwise, and therefore does not require the message to be padded.

For example, the message "Hello" will be processed as follows (pseudocode):

byte stream[16] = AES(Key, Nonce);
byte plaintext[5]  = "Hello";
byte ciphertext[5];
for i from 0 to 5:
    ciphertext[i] = plaintext[i] XOR stream[i];

The remaining bytes of the pseudorandom stream, beyond the length of the message, are simply discarded.


Is multiple encryption using NaCL and TLS better? In general, the idea of multiple encryption sounds interesting - for creating stronger cyphers (especially against implementation bugs), one could always get the configuration details wrong and mess it up.

So I wonder: if one starts with NaCL, which is supposed to have a default configuration that's very hard to mess up, and transmits it with TLS with a very good configuration, say from the recommendations at this Security.SE Q&A, does it improve security over TLS? What could go wrong?

Two things to consider: encryption and authentication.

In general you can only say that a cascade of ciphers is as secure as its weakest link. If the encryption in NaCL had a side-channel attack, it might leak information about the plaintext, whether or not the ciphertext is sent through TLS.
Authentication, on the other hand, is additive. If you can authenticate the message in both TLS and NaCL, breaking one will not allow an attacker to make forgeries.

However, getting any benefit requires that you have set up long term keys in both. Simply sending a NaCL key over a TLS channel allows a man-in-the-middle attack in case TLS is broken. Also, you have to use independent keys or a key recovery attack on any part of the stack may reveal them all.

In practice, a cascade may not help. If the implementations were perfect, it would likely be stronger, but with more things to implement there is also more potential for bugs and they may affect both. For example, Heartbleed would likely have leaked plaintext and keys even if you used an inner encryption layer (because it allowed random memory dumps).

When considering TLS and NaCL, specifically, you should note that some algorithms are used in both:

AES (used in Poly1305 and some TLS suites)
SHA-2 (Curve25519 and at least some TLS suites)

That doesn't matter if you are only concerned about implementation or protocol weaknesses, but means you couldn't claim resistance to one of those being fundamentally broken.


Embedded devices Authentication, Integrity and Confidentiality Embedded devices send messages to the server. The server occasionally sends messages to individual devices(Reboot, upgrade firmware etc)

After some research this is my ad-hoc solution:

1) Each devices gets a unique id(like MAC address) and a public/private key pair when first programmed at the factory. The server will have a copy of the unique id and the public key for each device.

2) The server has a public certificate.

3) When the device wants to send a message: If it wants confidentiality it can encrypt the message using symmetric encryption and the key,salt etc will be encrypted with the servers public key. Then it can use it's private key to digitally sign the message which gives the message Authentication and Integrity.

4) The same process could be reversed when the server wants to send a message to the client.

5) Timestamps will be part of the message to resist replay attacks. The time needs to be fairly synchronized (within a minute of each other) for data collection purposes.

Are there any flaws with doing it this way? The devices are fairly resource constrained so have to pick fast public key algorithms.

I do not see an immediate flow, but the public-key cryptography seems to be an overkill in your system with a single server. As long as the server keeps some keys of each device $D$, it may as well keep a single symmetric key $K_D$, and use a single authenticated encryption scheme $\Pi$ with key $K_D$, for instance, AES-GCM. This would simplify your system significantly, and you would not need certificates. You would not even need random number generator, except for the key generation.


What is chain voting? I read The Three Ballot Voting System by Rivest. This paper-based voting system can be attacked with chain voting. But can't find any description of what "Chain voting" is mentioned in section 4.9.

Would anyone explain what it is?

After a small search; it is a vote buying scheme.

  Chain voting, a vote buying scheme in which a crook gives the voter a pre-voted ballot, the voter votes that ballot, and then after leaving the polling place, sells his blank ballot to the crook, who votes it and then gives it to the next willing participant.

This is from Douglas W. Jones web page and reference 12 of the Rivest's article points his definition.

This attack is applied in many countries (I'll not give any source). One countermeasure can be paper-based PUF. Also, some ideas from University Voting Systems Competition might be interesting to look at.


Malleability for varying length message Given ciphertext for a message encrypted using $AES-CTR$ along with actual, desired message and IV, I need to perform malleability attack on the ciphertext to change the original message from $M$ to $M'$. But the message length of $M$ and $M'$ isn't the same. Since CTR doesn't use padding and the ciphertext is same length as the message then should I remove the extra bytes from ciphertext in the forged cipher to get $M'$ as its shorter than $M$?
To explain this better please see the following example of what I have done so far!
$M$ = "Pay alex \$100"
$M'$ = "Pay \$900"
$C$ = Ciphertext with first block as IV

Calculate $x = M ⊕ M'$ (I padded $M'$ before XOR to match length of $M$)
$C' = C[17... n]$ (Exclude initial 16 bytes as it corresponds to IV)
$C'' = C' ⊕ x$
Forged Cipher $C^* = C[1.. 16]||C''$ (First 16 bytes is the IV)

When I decrypt the forged ciphertext $C^*$ I get the expected message but with extra characters in the end as "Pay $900.....".
So in the forged cipher-text if I remove the last 10 hex characters I get the exact message $M'$ that I was expecting. Is it right approach to get rid of the extra bits in the forged cipher-text to match the message length or what I've done is incorrect?

Yes, you got it right. You XOR'ed the correct bits, copied the IV and then shortened the message. Nothing wrong with that approach.
The only thing that I'm a bit critical about is the one based indexing instead of the zero based indexing. Most mathematicians use zero based indexing (because it is compatible with modular calculations, for instance) and similarly do most developers and therefore cryptographers...


How can I derive an ed25519 key pair from a secp256k1 key pair? Alice has a secp256k1 key pair that she used some time ago when she communicated with Bob.
Bob can no longer user secp256k1 but he only uses ed25519 instead.
Alice and Bob cannot exchange any messages.

Is there a secure algorithm that Bob can use to derive an ed25519 pubkey from original Alice's secp256k1 pub key and also Alice can derive the matching ed25519 private key from her original secp256k1 private key

Secp256k1 and Ed25519 are completely different algorithms using different elliptic curves. There is no algorithm that could convert one to the other because the keys cannot match. It's just impossible.


Why is the Lovász condition used in the LLL algorithm? The LLL algorithm is used to approximate the Shortest Vector Problem, i.e., it outputs a reduced basis. Such a basis will satisfy two conditions:
  $$ \forall i \gt j. \quad \lvert\mu_{ij}\rvert \le \frac{1}{2} \qquad\text{[size-reduced]} $$
  $$ \forall i.\quad \lVert b_i^*\rVert^2 \le \lVert b_{i+1}^*\rVert^2 + \mu_{i+1,i}^2\lVert b_i^*\rVert^2 \qquad\text{[Lovász condition]}$$

It seems the first condition assures the resulting basis is nearly orthogonal.
But what does the Lovász condition mean and why is it used?

The issue with the length-reduction criterion alone (and the reason the Lovász condition is included in the LLL algorithm) is that the following basis satisfies it:

(The grey arrow is the projection of $b_2$ to the orthogonal complement of $b_1$.)

Clearly, this basis is not very short, nor is it close to being orthogonal (i.e., note that length reduction alone does not imply almost-orthogonality!). The Lovász condition is suited to detect such a situation: If the order of the vectors is swapped, another length reduction can easily be performed, yielding the following LLL-reduced basis:

It seems that Lenstra, Lenstra, and Lovász have noticed that a situation in which length reduction alone is stuck with a very bad basis — as depicted in the first image — always has vectors which are in the "wrong" order comparing their lengths and which are far from being orthogonal, and that it helps in this case to exchange them and continue length-reducing.¹
That is really the core idea of the LLL algorithm.

I think of the Lovász condition mainly as a technical construction that just "turned out" to work well, but by rearranging the terms, one may get a feeling for why it enforces close-to-orthogonality:

$$
(\delta-\mu_{i+1,i}^2)\lVert b_i^\ast\rVert^2 \;\leq\; \lVert b_{i+1}^\ast\rVert^2
$$
(In your formula, $\delta=1$ is "hardcoded".)

The Gram-Schmidt coefficient $\mu_{i+1,i}$ measures the angle between $b_i^\ast$ and $b_{i+1}$; the angle is small iff $\mu$ is close to $1$, and it is large (i.e. almost orthogonal) iff $\mu$ is close to $0$.
Note this talks about the angle between the orthogonalized vector $b_i^\ast$ and the lattice vector $b_{i+1}$, but $b_i^\ast$ is in turn forced to be "quite close" to $b_i$, hence this also bounds the angle between the lattice basis vectors depending on the orthogonalized vectors' lengths relative to each other.

In short: The Lovász condition is fulfilled if the vectors are close enough to being orthogonal, or if they are roughly ordered by length. Both of these properties lead to length reduction being quite effective.

¹ The procedure of changing the order of some vectors and length-reducing approximates another basis reduction concept, weight reduction, but there is no efficient algorithm to compute that one.


How does the rand() function in C work? I want to know how rand() works (even when I don't provide any seed how it produces PRNs?) thanks!

Well, successive calls rand() just produce numbers that "look random".

Now, rand() doesn't take a seed; that means that everytime the program runs, calls to rand() will generate the exact same sequence of numbers.  This is a deliberate design decision; that means that the program behavior is reproducible (which can be important if you're debugging).  If you don't want this behavior, well, that's why srand() is provided.

As for what "looks random" means, well, it essentially means "if you eyeball the output, no obvious pattern jumps out at you".

When working with cryptography (you did ask in the crypto stack exchange), we don't have much use for rand(); even if you feed in a seed via srand(), that seed is generally too small to be useful, and even if the rand() output isn't obviously patterned, crypto has much higher criteria for randomness.

On the other hand, other uses need not have such high standards.  I believe rand() may be useful within some randomized algorithms; just not cryptographical ones.


Learning with rounding (LWR) This may be a naive question:

LWR assumption states that for ${A} \stackrel{$}{\leftarrow} \mathbb{Z}^{m \times n}_q, s \stackrel{$}{\leftarrow} \mathbb{Z}^n_q$, given $(A, \lfloor A\cdot s \rfloor_p$), it is indistinguishable from $(A, u)$ with $u \stackrel{$}{\leftarrow} \mathbb{Z}^m_p$.
There seems to be no specific condition on $m$ and $n$ except $m,n \geq 1$.

My question is does this hold true for $m = n = 1$? It does not seem right to me, kindly explain.

There seems to be no specific condition on $m$ and $n$ except $m,n \geq 1$.

The LWR assumption isn't that the problem is hard for any arbitrary $m, n$, it's there it's true for the specific $m, n$ pairs we use in practice.  Obviously, for $m=n=1$, it's an easy problem; that's not particularly relevant, as we don't use $m=n=1$.

This is similar to the RSA assumption; that assumption isn't that it's a hard problem for arbitrary sized keys (it's not for, say, 10 bit keys); it's that it's a hard problem for the key sizes we use in practice (for example, 3072 bit correctly generated keys).


Simulation Based Proof: How the Corrupted Party's Input is Given To Simulator Imagine we have a 3-party protocol, including client $A$,client $B$ and a server. In this protocol client $B$ encrypts its input under its public key and sends it to the server. The server performs some computation using client $A$'s and client $B$'s input and returns the result back to client $B$.

Now we want to consider client $B$ is corrupted and construct a simulator for that. I do know that if we use a zero knowledge proof of knowledge the simulator can obtain client $B$'s input. But in the above protocol we do not use a zero knowledge proof.

My question is: In the above protocol, how can a simulator in the ideal world obtain client $B$'s input and send it to the trusted third party (TTP)?

Some more details: consider client $A$ has $S_A=\{a,b\}$ and client $B$ has $S_B=\{c,d\}$. Client $A$ gives its set in clear to the server. Client B does as follows: computes $Enc_{B}(c), Enc_{B}(d)$ and sends them to the server. Then the server computes: $Enc_{B}(r_1\cdot a+r_2 \cdot c), Enc_{B}(r_3\cdot b+ r_4\cdot d)$, where $r_i \leftarrow \mathbb{Z}_p$. And sends the encrypted values back to client $B$. It's clear that the view of client $B$ is indistinguishable in real and ideal world, thus we do not need any zero knowledge proof of knowledge to prevent client $B$ from doing any particular things. Please ignore the fact that the result is nonsense.

The simulator obtains "client $B$'s input" in the same way the simulator obtains $\:\{\hspace{-0.03 in}0,\hspace{-0.04 in}0\hspace{-0.03 in}\}\;$.

Even in the real world, the server computes its response without using any secrets, that response is the only message $B$ receives, and (from your description) no other party gives any output. $\:$ Thus, it doesn't matter what input the simulator sends to the trusted third party.


How to show that any 2-round key-exchange protocol satisfying a given definition can be converted into a public-key encryption scheme? How to show that any 2-round key-exchange protocol satisfying a given definition can be converted into a public-key encryption scheme that is CPA-secure?

The given definition is as followed:

Actually this is an exercise of the book "Introduction to modern cryptography", I can figure out how to prove it.

Can someone help me? Thanks a lot!

My reputation won't let me post this as a comment, but I believe you could simply use the key exchange as a one time pad.

Alice and Bob could use the key-exchange as normal. Alice initiates the key-exchange and sends the first round. Bob sends the second round. They now both have enough information to generate a shared key of length $k$ bits, which is CPA secure. Bob then sends a message of length $l \leq k$ XORed with the shared key (obviously only sending $l$ bits). Alice can decrypt this message, simply by XORing with the shared key.

Note that the entire key exchange needs to be repeated for each block of $k$ message bits. This repetition must be secure.


Choice of multiplication polynomial in Rijndael s-box affine mapping The Rijndael specification details the design choices for the s-box in section 7.2. They describe the choice of affine mapping as follows:

We have chosen an affine mapping that has a very simple description per se, but a
complicated algebraic expression if combined with the ‘inverse’ mapping. It can be seen as
modular polynomial multiplication followed by an addition:
$b(x) = (x^7 + x^6 + x^2 + x) + a(x)(x^7 + x^6 + x^5 + x^4 + 1)$ $mod$ $x^8 + 1$

The modulus has been chosen as the simplest modulus possible. The multiplication polynomial has been chosen from the set of polynomials coprime to the modulus as the one with the simplest description. The constant has been chosen in such a way that that the S-box has no fixed points (S-box( a ) =  a ) and no ’opposite fixed points' (S-box( a ) =  ā ).

The multiplication polynomial being $x^7 + x^6 + x^5 + x^4 + 1$, which is irreducible and therefore coprime to the modulus $x^8 + 1$. The inverse mapping multiplication is $x^7 + x^5 + x^2$.
However, $x^7 + x + 1$ is also irreducible, and has an even more simple representation. It is the most simple irreducible polynomial of degree 7. It also has a longer affine period (8 vs 4) which is supposedly better. There are many valid choices for the added constant that result in no fixed or opposite fixed points. The inverse mapping multiplication is $x^6 + x^5 + x^3 + x^2 + 1$, which is coprime to the modulus.
Is there some obvious reason the more simple polynomial was not used? The implication in the Rijndael specification is it does not have the simplest description, which does not seem to be the case. My assumption is lack of complexity of the algebraic expression in the resulting s-box or its inverse, but I do not have the means to determine if that is the case.
update
Thinking that the reason may have been the statistical performance of the s-box with the given affine polynomial, I compared it against $x^7 + x + 1$, the results are below:
                             AES        x^7 + x + 1
SAC Relative Error           12.5%      9.4%            lower is better
SAC Satisfaction %           67.2%      67.2%           higher is better
Distance to SAC              432        432             lower is better
Negative DSAC                176        152             lower is better

2nd order SAC Rel Err        12.5%      12.5%           lower is better
2nd order SAC Sat %          56.7%      61.2%           higher is better
Dist to 2nd order SAC        1664       1424            lower is better
Negative 2nd order DSAC      844        684             lower is better

AVAL Relative Error          3.52%      3.12%           lower is better
Guaranteed Avalanche         339.2      339.2           my own metric

Bit Independence Rel Err     13.412%    12.856%         lower is better
Bit Independence Sat %       56.2%      63.8%           my own metric

It is quite clear that $x^7 + x + 1$ has better results in many s-box performance metrics when compared to the chosen polynomial.
During testing I also found that the Rijndael s-box has a self inverse mapping at 0x73 and 0x8F, where an input to the s-box and the inverse s-box produce the same result. This implies that the additive constant may not have been chosen carefully enough. The optimal constant appears to be 0x15.

As I have duplicated your question by mistake and non of us have had an answer, I request help to the authors to know why those parameters where selected like that.

The affine transformation is a vector space operation $(\mathbb{F}_{2})^8$, and the simplicity comes from the fact that, from the bunch of possible transformations the one used can be also described as a product in a polynomial ring modulo $x^8+1$.

Above the criteria that the matrix (or the multiplicand constant in polynomial view) must be invertible and the vector (or the addition constant) has avoid fixed point neither opposite fixed points, they have simply picked some from the set.

The timing feature is useful when the S-Boxes are calculated on the fly, but with them pre-calculated the difference doesn't matter (I think).


Which hash function is usually used in RSA? I know there are several available, however I can't seem to find whether there is one standard one or not.

I think I understand the process of digital signatures, just wondering which has function is used.

Thanks

In general there is no default hash algorithm in the PKCS#1 standards, neither for RSA with PKCS#1 v1.5 padding or RSA with PSS. Both these schemes are defined in RFC 3447 RSA PKCS#1 v2.1. Note that PKCS#1 v2.2 adds a few SHA-2 hash functions (SHA-224 and SHA-512/224 and SHA-512/256) to the mix - neither of which makes much sense.

PSS uses a Mask Generation Function MGF1 which defaults to SHA-1:

  The default mask generation function is MGF1 with SHA-1

however, that's not the hash used to hash the message itself, it's just used to pre-process the hash before modular exponentiation. The strength of the hash used for MGF1 is not that important.

Many API's that have been around for some time rely on SHA-1 as a default. MD5 and SHA-1 have been around for a long time, and most libraries seemed to have taken the more secure SHA-1 as more future proof.
You might find very old libraries that default on MD5, but I haven't come across them yet.

The low level security of SHA-1 shows one of the reasons why defaults should not be used. Once a library sets a default, it's impossible to get rid of, even if the default algorithm - SHA-1 in this case - is found to be insecure.  Explicit parameterization is much better. It may require some initial effort when coding, but that is easily recovered during the maintenance phase of software.

Usually the specific SHA-2 algorithm needs to be configured in API's if SHA-2 is to be used. That's also because there is more than one SHA-2 algorithm: there are 2, with 6 variants in total. SHA-3 has 4 variants, so I don't expect this to change in the future. Furthermore, it has two SHAKE variants, SHAKE128 and SHAKE256 that can be used for RSA-FDH.


What would happen in DSA/ECDSA if there were a collision in $r$ but not $k$? In DSA, the value of $r$ is generated as:

$r = (g^k \bmod p) \bmod q$

ECDSA is similar, using the $x$ coordinate of the generator $g$ scalar-multiplied by $k$, again taken modulo $q$.

It's well-known, particularly by Sony, that $k$ must be different for each message signed, or the private key leaks.

Due to the construction, it is possible, but unlikely, to generate two different $k$ values that result in the same $r$ value.  If you happen to generate two signatures of different messages that have the same $r$ value but different $k$ values, does it break security?

If you happen to generate two signatures of different messages that have the same $r$ value but different $k$ values, does it break security?

No, it doesn't break security.

Suppose you happened up use two different $k$ values ($k$ and $k'$) that just happened to result in the same $r$.  Then, when you publish the corresponding $s$ values, you would publish:

$$s = k^{-1} (H(m) + xr)$$

$$s' = k'^{-1} (H(m') + xr)$$

with $s, s', r, H(m), H(m')$ known.

That leaves $k, k', x$ are three unknown variables; for any possible $x$ value (which is the private key), there are $k, k'$ values that make these equations fit, hence we cannot deduce the value of $x$ from these two equations.

In contrast, if we also knew that $k = k'$ (that is, if the actual $k$ value was reused), then that drops the number of unknown variables to two; in that case, it's just a pair of linear equations in two variables - quite easy to solve.


How is it possible for someone to "Protect against Future Unknown Attacks" In section 4.4 (page 6) of Camellia: A 128-Bit Block Cipher Suitable for Multiple Platforms - Design and Analysis, it says

  $FL$ and $FL^{−1}$ functions are inserted between every 6 rounds
  of a Feistel network to provide non-regularity across rounds. One of
  the goals for such a design is to thwart future unknown attacks.

How we can thwart against attack which we dont know, or which is yet to be discovered or established?

How we can thwart against attack which we dont know, or which is yet to be discovered or established?

I'll just answer in the generic sense: by adding complexity. The complexity / irregular structure of the function(s) may not be directly needed for the (incomplete) security proof of the overall cipher but it may still need to be overcome by attacks on it.

For instance, a function could be used to hide a regular algorithmic structure, so that the cipher cannot easily be written down as a set of mathematical equations. New advances may make it easier to solve the equations for a (partially) unknown key. So those kind of attacks may be avoided by adding complexity.

Of course, with the attacks being unknown, it's impossible to be sure such attacks would be thwarted. So it's a goal which is only reached if one or more attacks are nulled or at least made computationally hard.


Complexity of Gaussian Elimination over a Finite Field I read somewhere that the complexity of solving a Linear $n\times n$ system over a Finite Field $\Bbb F_q$ using Gaussian Elimination is $\mathcal{O}(n^3)$ operations in $\Bbb F_q$.
What's the role of $\Bbb F_q$ here in the complexity?
Also, what's the cost of this algorithm in terms of $q$ and $n$?

The classic Gaussian Elimination algorithm is $O(n^3)$ runtime regardless of specific field and the Matrix, so in this case a finite field $F_q$ of order $q$ doesn't play a role in the complexity. This runtime is due to the fact that you are zeroing out entries in columns column-by-column to get into row reduced echelon form.
For matrices in $GL(n, q)$, the set of $n\times n$ invertible matrices in the finite field of $q$ elements, Andrén et al. in 2007, demostrated a striped Gaussian elimination in

On the complexity of matrix reduction over finite fields

which can shave off a $\log_q n$ factor by attempting to pick row operations that simultaneously zero out entries in multiple columns by using the finite field structure.
They proved that up to a constant factor this algorithm is best possible as almost all matrices in $GL(n, q)$ need asymptotically at least $\frac{n^2}{2 \log_q n}$ operations.
Demetres, in 2014 showed that the striped elimination algorithm is asymptotically optimal by proving that almost all matrices in $GL(n, q)$ need asymptotically at least $\frac{n^2}{\log_q n}$ operations.

The Asymptotic Complexity Of Matrix reduction Over Finite Fields


Why are stream ciphers based on linear-feedback shift registers so popular? I was conducting research on stream ciphers and LFSRs was a subtopic of my research and I was wondering why are LFSRs so popular?

There were popular once upon a time;

They were very easy to implement in the hardware. Think about you only need latch and $\oplus$. For combining functions some $\wedge$ operation.
Their periodic properties are well studied, the minimal polynomial and characteristic polynomial etc. You can see a glimpse in the classical book of Solomon Golomb.
They are insecure, as Fgrieu said in comments. Single LFSR can be breakable by Berlekamp-Massay algorithm. You need only $2L$ keystream if the LFSR's length is $L$. Interestingly, this algorithm was invented for decoding the BCH codes.
Many people tried to use LFSRs to produce secure stream ciphers. To see the attacks on them look at the links.

Combining LFSRs with non-linear combiner broken by the novel attack of Siegenthaler
Irregular clocking as Alternating step generator
Shrinking Generator
Filtering the LFSR

Some recent (date back to 1999) algorithms based on LFSR

A5/1 and A5/2 used in GSM phones, E0 used in Bluetooth. If you look carefully on their usage you will see that there were a second design factor for this ciphers. That is; using smaller hardware. And, this reduces the power consumption.

Note 0: Definitions:

Shift Register : cascaded flip-flops that the out od each is connected to the next one's input. At each clock cycle, the data shifts one. As in 'C' code  x << 1
Linear-feedback shift register, LFSR is a shift register where the input is the linear combination of previous states.
Nonlinear-feedback shift register, NLFSR is a shift register where the input is the non-linear combination of previous states.

Note 1: The following from eSream project are using LFSR or NLFSR or both:

Trivium uses 3 NLFSRs.
Sosemanuk uses LFSR with a maximal period $2^{230}-1$
Grain uses both LFSR and NLFSR
MICKEY uses both LFSR and NLFSR

Note 2: They have other applications as @bmmo6 said in the comments.

Note 3: I barely remember a product advertisement in Cryptologia. They were claiming that they combined 5 LFSRs to generate a secure cipher.


Is the hash function $h(x\|y) = AES_x( y)$ collision resistant? If $x$ and $y$ are both 128-bit strings would the function $h(x||y) = AES_x(y)$, where $x\|y$ means concatenation, be considered collision resistant ?

Is there an easy way to find $(x_1, y_1)$ and $(x_2, y_2)$ such that $h(x_1\|y_1) = h(x_2\|y_2)$ ?

I couldn't think of a way but since the hash function is un-keyed something tells me that there is a way to manipulate the key/string pairs?

It isn't even second-preimage resistant. Hint:

   $y = \mathrm{AES}^{-1}_{x}(\mathrm{AES}_{x}(y))$

For any 128-bit string $x_1$, $x_2$ and $y_1$,

   $h(x_1||y_1) = \mathrm{AES}_{x_1}(y_1) = \mathrm{AES}_{x_2}\left(\mathrm{AES}^{-1}_{x_2}(\mathrm{AES}_{x_1}(y_1))\right) = h\left(x_2 || \mathrm{AES}^{-1}_{x_2}(\mathrm{AES}_{x_1}(y_1))\right)$

Follow-up question: is it preimage-resistant?

   $h(x||y) = \mathrm{AES}_{x}(y)$ so $y = \mathrm{AES}^{-1}_{x}(h(x||y))$. For any hash value $H$ and any 128-bit string $x$, it's trivial to calculate a preimage that begins with $x$.


Recommended key size for DKIM What is the recommended key length for DKIM? I'm currently thinking about a 1024-bit key vs. a 2048-bit one.

From the crypto point of view for RSA, 2048 or 4096 bits is clearly recommended--no discussion on that point. Having glanced over various posts, it seems there may be some trouble at the mail or DNS level with keys of 2048-bit length.

Moreover, using 1024-bit keys seems to be the current trend.

Which key length is best for DKIM?

Nobody has publicly announced that they've broken 1024-bit RSA (other than via implementation defects that can happen with any key size), but it's not out of the question. I can't find a recent estimate, but when RSA-768 was broken in 2009, the researchers estimated that RSA-1024 would be “about a thousand times harder” and that there was “little doubt about the feasibility by the year 2020 of a matrix required for a 1024-bit NFS factorization”. So 1024-bit RSA should certainly not be used to encrypt confidential data or to authenticate arbitrary entities.

However, DKIM is somewhat less demanding than most cryptography applications. Your adversary is not NSA, it's spammers and scammers. On the scale of how much money they make, the cost of breaking 1024-bit RSA would be totally prohibitive. Furthermore, the impact of a broken key is detectable and correctable: if someone manages to break a legitimate key and makes use of that, there will be emails bearing those traces. This may cause temporary harm, but the key can be revoked. In practice, it's a lot more likely that an adversary would impersonate a legitimate participant by exploiting some misconfiguration of the server than by breaking the cryptography.

So 1024-bit RSA is fine for DKIM at the moment. However, attacks only ever get better. It's possible than an improvement to factoring techniques will make it slightly easier to break RSA, and will bring 1024-bit RSA from “NSA can break it if they really want” to “$10k on AWS”. So you should have an upgrade path ready, which you should always have when it comes to cryptography anyway. You should make sure that your system accepts 2048-bit keys, but it's ok to use a 1024-bit key for now.


Frequency Analysis on DES, AES, 3DES using Cryptool2 I am trying to analyze symmetric block ciphers like DES, 3DES and AES, using Cryptool 2.
I want to do a frequency analysis on each of these ciphers, in order to comment whether this is an effective way for cryptanalysis or not.
However, the ciphertext these ciphers produce comes in hex form:

My question is - when performing frequency analysis on such ciphers, do I input the hex ciphertext or do I need to transform it into text? How can I comment on that (based on letter frequency or bit occurrence)?

My question is - when performing frequency analysis on such ciphers, do I input the hex ciphertext or do I need to transform it into text? How can I comment on that (based on letter frequency or bit occurrence)?

First of all, what you are looking at is a hexadecimal representation of the ciphertext. The ciphertext itself does not consist of hexadecimals, it is binary. Converting it to text makes very little sense; if any analysis has to be done it has to be performed over the binary data without any conversion to text.
We know that DES and AES are permutations over block sizes of 8 or 16 bytes. What you are showing is a DES or AES using mode of operation. Analysis should only be performed on the combination of the two. And you can actually find e.g. duplicate blocks when DES or AES is used in ECB mode. In any correctly used secure cipher mode they should of course be secure, and indistinguishable from random (IND-CCA/IND-CPA).
It doesn't make much sense to use the general frequency analysis over the cipher as the output does not even consist of characters. Generally analysis should not be performed willy-nilly; it is performed while keeping the characteristics of the cipher under investigation in mind. And this kind of leads to the answer...


Is TLS secure against VM reset attacks? Is the TLS protocol secure against VM reset attacks?

Background: Imagine running cryptographic software inside a virtual machine (VM).  A VM reset attack is one where the the state of the software is checkpointed (snapshot) at one point in time, allowed to run forward, and then reset (rolled back) to the previous snapshot and run forward some more.  In some cases, this allows powerful attacks.  There exist protocols that are secure in the standard model, but not secure against VM reset attacks.

So, is TLS (as a protocol) secure against this kind of attack?  Are there are any attacks?  Are any of the TLS ciphersuites vulnerable to VM reset attacks?

Prior work:  Ristenpart et al. showed that some TLS implementations are vulnerable to VM reset attacks, in the following paper:

Thomas Ristenpart and Scott Yilek.  When Good Randomness Goes Bad: Virtual Machine Reset Vulnerabilities and Hedging Deployed Cryptography.  NDSS 2010.

However, their attacks are all against particular implementations of TLS, and exploit failure to reseed the RNG.  In other words, they seem to represent a failure of the implementation rather than of the protocol itself.  It appears that a sufficiently careful implementation can shield against those attacks by adding additional entropy to the PRNG at appropriate points.

My question is: are there any protocol-level VM reset vulnerabilities in TLS?

Threat model: Here is a more detailed threat model.  The software runs inside a VM.  The attacker can freely interact with the software over the network, as usual.  Also, the attacker gains two additional powers: at any point, the attacker can save a snapshot of the current state of the VM; and at any point, the attacker can roll the VM back to some prior snapshot and then cause it to continue execution from there.

It is easy invent protocols that would be secure in the standard model but insecure in this model.  For instance, imagine a protocol that generates an ephemeral keypair $K_A,K_A^{-1}$ for a one-time signature scheme, signs the ephemeral public key $K_A$ with a long-term RSA signing key, receives some message from the attacker, and then signs some message using the ephemeral signing key.  In the standard model, this would be as secure as using a RSA signature.  But in the VM reset model, this is insecure: an attacker could snapshot the system right after it generates the ephemeral keypair, let it run forward to emit one message signed by the ephemeral private key; then roll it back to the snapshot and run it forward from there, observing a second message signed by the same ephemeral private key.  Once the attacker observes two messages signed by the same one-time private key, the attacker can forge other messages.  So that's a proof that protocol-level VM reset vulnerabilities can exist.  But is the TLS protocol vulnerable?

No, TLS is not secure against VM reset attacks. There are at least two attacks that are made possible by VM reset attacks, off the top of my head:

AES-GCM nonces are typically generated deterministically from the message counter value. If you set the snap shot prior to the local peer sending a plain text message that will change after resetting to the snap shot, you will have a severe nonce reuse vulnerability. As specified in RFC 5288, the 64 bit explicit nonce that is sent per packet MAY equal the message counter. The current TLS 1.3 draft removes the explicit nonce and replaces it with the implicit message counter xor:ed with the static IV values that were derived from the master secret. The same nonce generation is specified in the chacha20-poly1305 draft, which consequently has the same vulnerability. The traditional CBC cipher suites would be less vulnerable, in particular if used in encrypt-then-mac mode. Edit: In practice, the VM engine might be implemented to automatically close all TCP connections when suspended, and not necessarily reconnect when resumed after a reset. This might help to make the attack less practical against normal TLS connections directly over TCP. TLS over other types of channels and DTLS over UDP might be a different story.
Session master secrets are supposed to be discarded after any fatal alert corresponding to the session, such as failures to verify the finished messages. An attacker that is able to reset the local peer would obviously be able to circumvent this. This means e.g. that an attacker might attempt to perform session resumptions using the session id belonging to another peer, even after an initial failure. Such attacks against the session state do not depend on in which state the VM engine leaves the network stack when resetting to a snapshot.


Is there a Pseudo Random Permutation Generator that can output all values of the length of N Is there a pseudo random permutation generator that produces all permutation of any bit length of the plaintext (this may not be clear, please let me know and I will explain).  It must be fast, and does not hold numbers in memory.
This is a permutation of (1)
(1)
This is a permutation of (1,2)
(2,1)
This is a permutation of (1,2,3)
(1,3,2) (2,3,1) (2,1,3) (3,1,2) (3,2,1) n!
Note* the above is not in a pseudo random order and not a complete set that I am looking for.
This is a pseudo random permutation with replacements that I am looking to duplicate with a generator of any size.
PRP of (1,2,3) with replacements
(1,1,1)(3,3,3)(2,3,3)(1,1,3)(3,3,2)(2,3,1)(2,2,2)(1,3,3)(3,2,3)(2,1,2)(1,2,2)(3,1,3)(1,1,2)(3,3,1)(2,3,2)(2,2,1)(1,3,2)(3,2,1)(2,1,1)(1,2,3)(3,1,1)(2,2,3)(1,3,1)(3,2,2)(2,1,3)(1,2,1)(3,1,2) N^N
If one does exist could you please post its name, if possible.
If it does not exist could you expound as to the reason why, if it is against a known proof, or it has simply not been made, yet.
The question here is very similar but it needs to be with replacements.
https://math.stackexchange.com/questions/3521660/invertible-pseudo-random-permutation-function
What would it mean if it could be made. Meaning given the length of any plaintext if that order and length is your first permutation of group g than all permutation after that would be your subgroup permutations. Given that the key length that produces the permutation is not an issue (I would be glad to explain this as well).
Another way of writing this would be. What program would generate all permutations of a given string with replacement? The given string is the complete message source or file to encrypt of any size. It will probably be recursive. Once all permutations are calculated it should loop back to the original permutation which is the file.

Use any true random permutation generator that relies on random input. Then replace the random input with the output of a PRNG primitive.


Any way to prove possession of a RSA 2048 private key using 256 bit? Alice has a RSA 2048 private key and Bob has corresponding public key.
They have a secure connection, but Alice can transmit only 256bit to Bob (Bob can transmit any amount of data to Alice).
Is there a way how Alice can proof to Bob that she is in possession of the private key?

Is there a way how Alice can proof to Bob that she is in possession of the private key?

Here is one possible way:
Bob selects a random 2048 bit value $m < n$ and computes $m^e \bmod n$ and sends that and $\text{SHA3_256}(m )$ to Alice.
Alice, with the private key, recovers $m$, and verifies that $\text{SHA3_256}(m)$ matches the value she received from Bob.  If so, she computes and sends $\text{SHA3_256}(m || m)$; that's 256 bits.
Bob compares that with the hash of the duplicated value he originally selected; if they match, then either Alice was improbably lucky, or she really does have the private key.
Bob cannot use this protocol as an Oracle to compute the hashes of RSA decryptions, because he would need to already know the hash of the plaintext.


Signal Double Ratchet - How can Alice send 2+ messages in the beginning of the Signal Protocol? I'm studying about Signal Protocol and I had a doubt in Double Ratchet Algorithm. This section describes how to derive the receiving and sending key messages.

Alice is initialized by Bob public ratchet key but what if Bob is offline? For example:
  Alice starts the X3DH with Bob sending the first message but Bob is offline. So Alice decide to send a second message, this second message will be delivered via X3DH?

X3DH derives a shared secret using Alice' static identity and fresh ephemeral with Bob's static identity and semi-ephemeral (and optionally, if available a one-time ephemeral).

Alice sends Bob her static identity and a fresh ephemeral along with her encrypted messages. Bob can complete the handshake and read messages Alice sent him. All messages so far may be compromised if Bob's static and semi-ephemeral keys have been compromised and Bob didn't have any one-time ephemeral keys left. Bob may respond and introduce a fresh ephemeral key. All messages after this point are safe even if Bob's static key and semi-ephemeral were compromised.

Notice how the hash-ratchet is deriving per-message keys independent to the dh-ratchet, so it does not wait for any round trips as it derives multiple message keys.

For more information you may see the X3DH and Double Ratchet specifications.


Doing RSA-KEM with RSA-OAEP I am fiddling around with the JS Web Crypto API and creating a hybrid encryption system that uses a symmetric key to encrypt form data with AES256-CBC and and a public/private key-pair to wrap/encapsulate the symmetric key using RSA-OAEP.

Currently I am simply generating a random 256bit key that will get padded and wrapped by RSA-OAEP.

I stumbled across RSA-KEM in RFC 5990 and love the fact that I can derive both the encryption key and iv (and many other keys) from it via HKDF. HKDF is a supported algorithm in the Web Crypto API but RSA-KEM says I should use "simple RSA" without any padding to encrypt the random element for key derivation which is surprisingly an algorithm not mentioned in the W3C specifications.

Can I encrypt the random element used for key derivation with RSA-OAEP (even the padding is not needed) or are there any security concerns? Should I stick to my current implementation?

If what you have is a machine that computes RSAES-OAEP and not a machine that computes $x \mapsto x^e \bmod n$, you don't really have the tools to do RSA-KEM.  You're better off doing what you were doing in the first place—unless I can talk you out of going near the incoherent minefield of hysterical raisins without meaningful guidance that is the WebCrypto API.

Now, it is technically possible to abuse RSAES-OAEP to give the simulacrum of an RSA-KEM implementation.  It might even be compatible with RSA-KEM implementations on either side, but you really shouldn't try to simulate RSA-KEM using RSAES-OAEP unless you are desperate and your RSAES-OAEP machine accepts the OAEP randomization as a parameter and returns it on decryption and you have a separate subroutine to compute OAEP alone without the RSA part.

For a message $m$ to an RSA modulus $n$, the sender could do:

Pick $k_0 \in \{0,1\}^{256}$ and $r \in \{0,1\}^{256}$ uniformly at random.
Compute $x = \operatorname{OAEP}_n(k_0, r)$.  (This is the padded element of $\mathbb Z/n\mathbb Z$ before we compute modular exponentiation, raising it to the power of the public exponent $e$.)
Compute $k = H(x)$ (e.g., use HKDF).
Compute $y = \operatorname{RSAES-OAEP}_n(k_0, r)$ so that $y = x^3 \bmod n$.
Yield the key $k$ and its encapsulation $y$.

On receipt of $y$, the recipient could do:

Compute $(k_0, r) = \operatorname{RSAES-OAEP}_n^{-1}(y)$ or reject if RSAES-OAEP decryption fails.  (Beware padding oracle attacks!)
Compute $x = \operatorname{OAEP}_n(k_0, r)$.
Compute and yield the key $k = H(x)$.

Note that this also requires a subroutine to compute OAEP itself, and requires the public key operation $\operatorname{RSAES-OAEP}_n$ to accept the OAEP randomization $r$ as a parameter alongside the short string to be encrypted, and requires the private key operation $\operatorname{RSAES-OAEP}_n^{-1}$ to yield the OAEP randomization $r$ that was encrypted alongside the short string.

So in the end, although as a black box this is probably (unless I made a mistake) indistinguishable from RSA-KEM, it's much more complicated to implement than just encapsulating the randomly generated key $k_0$ with RSAES-OAEP as a sort of ‘RSAES-OAEP-KEM’ as you were doing in the first place.


Specific example of a MAC in TLS? This seems like quite a dumb question, but I really don't know if I'm finding a answer anywhere. I understand that if i access a website that is secured with TLS, we exchange ciphersuites and so on, then decide on what algorithms to use. But, specifically, what is an example of a specific MAC my browser could use with a website secured with TLS? I mean the MAC itself and precisely how it works and so on?

Thanks!

The MAC algorithms used in TLS (and the older SSL) cipher suites have historically been HMAC, with the hash function used in the HMAC specified in the cipher suite.

HMAC is very widely used and described so I won't repeat the full description of it here, but it essentially hashes all the data in messages being sent to and from the webserver, combining the resulting hash with a key (which is negotiated during the TLS connection) into a short message authentication code that is sent alongside the message - the receiving end then repeats the process to ensure that the message has not been altered in transit.

Newer cipher suites used in later versions of TLS (e.g. TLS 1.2) include AEAD encryption algorithms, which you can think of as encryption with a built-in MAC, and .

e.g. viewing this question over https in Firefox 34, the cipher suite being used is TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256, meaning that the MAC algorithm being used is the built in MAC provided by the GCM AEAD encryption mode.

If the cipher suite had been TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA256, then the MAC algorithm would be 'HMAC with SHA-256`


How are side-channel attacks executed? What does an attacker need to execute a side channel attack? I've been reading about side-channel attacks on Wikipedia, and it seems that some of these can only be executed on the victim's computer. (I am specifically asking about the side-channel attacks listed on the Wikipedia page and any more that are theoretically possible)
What would an attacker need to execute each side channel attack?
How are side-channel attacks executed?

Here's a very simple timing side channel attack that you might even see in movies.  Suppose you're trying to log in to a computer with a password, and the victim compares your password byte by byte but stops early if there's a mismatch:

for (i = 0; i < n; i++)
  if (password[i] != input[i])
    return EFAIL;

How do you attack this?

Try a password like aaaaaaa, and use a stopwatch to measure how long it takes; then try baaaaaa, caaaaaa, and so on, and whichever one takes the longest time—say haaaaaa—tells you what the first letter is.

Of course, there may be noise in the timings, so you may have to try each one several times and gather statistics to see the signal through the noise, or carefully arrange that input[i] is in an unmapped or uncached virtual page to amplify the signal of whether the comparison routine reached it.

Then repeat with hbaaaaa, hcaaaaa, etc., until you find huaaaaa; then hunaaaa; then huntaaa; until you've got the password.

How do you defend against such an attack?  Standard countermeasures: rewrite the logic in constant time so that the time it takes is the same for all inputs, and/or judiciously randomize the problem so that any variation in the time is independent of the variation in inputs.

This is only one of many, many types of side channels.  Here are a few other examples and roughly what you need to pull them off:

The CRIME and BREACH exploits take advantage of the compression ratio as a side channel for secret content, namely HTTP cookies.

If the software foolishly passes secrets through compression and reveals the resulting length, what you need is a JavaScript program to run in the user's browser to trigger HTTPS requests for some target site, and an eavesdropper on the network to watch them.

(Most browsers don't do this kind of naive compression any more, because of such attacks!)
Padding oracle attacks like Serge Vaudenay's exploit different types of error messages—padding error vs. authentication failure—as a side channel for secret content of messages.

If the protocol is badly designed (like the original SSL protocol) and the software behaves differently for padding errors and authentication failures (like early SSL implementations), what you need is a MITM on the network who can intercept packets on the wire and modify them to see how the peer behaves.

(Modern TLS no longer uses cryptosystems susceptible to padding mistakes like this, and modern implementations of older versions of TLS/SSL take extra effort to avoid padding oracles—but even the countermeasures sometimes admit other side channel attacks like Lucky Thirteen.)
The Spectre class of attacks exploits side channels arising from timing of speculative execution in CPUs.

If the CPU naively implements speculative execution like essentially all mass-market desktop, laptop, and server CPUs for the past two decades, and if the software doesn't have extensive countermeasures to thwart this class of attacks, what you need is a JavaScript program running in the browser with access to a reasonably high-resolution timer (which, with extra effort, can be simulated using a lower-resolution timer) to set up a Spectre gadget and measure it—and it works even if all the cryptography is safely implemented without side channels of its own like timing attacks below, because it works by using the CPU's speculative execution to reach into memory it shouldn't have access to at all.

(Spectre is baaaaaaaaaaaad news.)
Timing attacks on cryptosystems exploit computations with secret-dependent running times as a side channel for the secrets.  There are many reasons computations might take secret-dependent time, a class of side channels reported in Kocher's seminal paper:

When computing, e.g., the RSA private key operation $x^d \bmod n$ for secret $d$, it is tempting to use a standard square-and-multiply algorithm that checks $(d \mathbin\gg i) \mathbin\& 1$ to decide whether to multiply by $x$ or not at the $i^{\mathit{th}}$ step.  CPUs are bad at keeping branch decisions secret in the first place; skipping a multiplication can changes the time even more substantially, which may reveal which bits of $d$ are set.  What you need to exploit this is an automated system that responds to (say) encrypted queries, and a stopwatch.
When computing, e.g., AES, it is tempting to use secret-dependent table lookups.  CPUs are bad at keeping memory addresses secret—CPU caches are crucial for modern CPU performance, but also exploitable as a side channel.  What you need to exploit this is a JavaScript program in a web browser that can trigger AES operations under the target key, say the power to trigger and measure disk encryption timing as Tromer, Osvik, and Shamir demonstrated (paywall-free).
When checking whether an attacker-supplied message authentication code matches the legitimate message authentication code to verify a message or drop it as a forgery, a naive implementation might check the code byte-by-byte and stop early when it first mismatches: for (i = 0; i < n; i++) if (p[i] != q[i]) return EFAIL;.  If the software does this, what you need is a MITM with a stopwatch to attempt forgeries and guess the correct MAC on a desired forgery byte-by-byte like hackers in movies figure out passwords letter-by-letter.

The EFAIL attack exploits cryptographic flaws in OpenPGP and S/MIME to selectively modify encrypted email messages so that the recipient's mail reader will act on modified messages to just leak the secrets out directly.  What you need to apply this is the dumpster fire of an implementation ecosystem that is OpenPGP and S/MIME.

(That said, most OpenPGP implementations have now fixed the cryptographic flaw that enables this one.)
Computers sometimes sound different depending on what operations they're performing and on what data, leading to acoustic cryptanalysis (paywall-free preprint).  This may sound far-fetched because you need a sensor with physical proximity to the adversary…but people seem inexplicably excited to buy remote surveillance microphones from Apple, Amazon, and Google and put them in their homes!  Alternatively, can you deliver a JavaScript program to a victim that turns on their computer's microphone?

This is not a comprehensive study of side channels.  There are other entire classes of side channels like electromagnetic emissions or power analysis or active fault attacks.  However, these are a little less compelling as a remote exploitation vector—power analysis (whether simple power analysis or differential power analysis) and fault attacks are most relevant to smart cards, for instance, where the adversary has physical access to the device to begin with.

This is not a comprehensive study of what you need in order to exploit side channels either.  There may be countermeasures in place to make them harder.  There may be noise that makes them harder.  You might run out of patience trying to draft a proof of concept.  I drafted a Meltdown exploit but ran out of patience with Spectre, when they were first released, or vice versa, I forget.  It was a fun afternoon toy.  But the side channels that you have the patience to practically exploit are only a tiny subset of the side channels that an adversary—with a market of off-the-shelf exploitation tools—is potentially able to take advantage of.


Testing whether a secret value is zero without security bits (in SPDZ) To test whether a secret value $[x]$ is zero, where $x \in [0,2^{k−1}]$, SPDZ uses the a based on the method of Catrina and de Hoogh [1].

This method requires to working on a field with modulus $p>2^{k+s}$, where $s$ is a is a statistical security parameter.

Does another method exist that perform this comparison but eliminate the need for security bits (performance is not my #1 concern)?

Thanks.

[1]-https://www1.cs.fau.de/filepool/publications/octavian_securescm/smcint-scn10.pdf

Secure zero-testing without working in a large field can be done with a protocol by Lipmaa and Toft, and with similar efficiency to the Catrina and de Hoogh protocols.

The basic idea is to open $m = x+r \bmod p$, where $r$ is a uniformly random field element and the parties have shares of the bits of $r$.

The parties will test whether $m$ equals $r$ by computing shares of the Hamming distance $[H] = \sum_i (m_i + [r_i] - 2m_i[r_i])$ (which is $\sum m_i \oplus r_i$). Note that $x=0$ iff $H=0$.

They test whether $H = 0$ with a polynomial interpolation trick - this can be done with around $\log p$ multiplications since $H \le \log p$, and most of these can be preprocessed in advance (see Section 3.1 of the paper for the details).


Decisional Discrete Logarithm problem? Has the decisional version of the discrete logarithm problem been studied somewhere? I mean, for known $G$ in a group, distinguishing $xG$ and $Y$ for unknown integer $x$ and group element $Y$?

The standard discrete logarithm assumption asks, given a group $\mathbb{G}$ of order $p$ with generator $G$, to compute $x$ given $xG$, where $x$ is a random. This means that $\{xG : x \gets \mathbb{Z}_p\}$ spans the entire group, so $xG$ is exactly a uniformly random group element. You cannot possibly hope to distinguish it from random, since it's perfectly distributed as a random group element.

That being said, there are "decisional variants" of the discrete logarithm problem:

distinguish $xG$ for a random even $x \gets \mathbb{Z}_p$ and $xG$ for a random odd $x \gets \mathbb{Z}_p$ (even and odd are defined by viewing $x$ as an integer between $0$ and $p-1$). This decision problem is equivalent to the computational discrete logarithm (the proof is a standard exercise, at least when the success probability is assumed to be 1 - it's harder in the general case).
distinguish $xG$ from a random group element, when $x$ is a random short element (e.g. between $0$ and $2^k$ for some $k$ related to the security parameter, such that $2^k$ is much smaller than $p$). This problem actually reduces to the computational "short-exponent discrete logarithm assumption", which asks to find $x$ given $xG$ for a random short $x$ (proof here).


FIPS 140-2 compliant algorithms in Enhanced RSA and AES Cryptographic Provider (Windows XP) We have a native C++ application that supports Windows XP SP3.

Recently we've decided to change our crypto algorithms to FIPS 140-2 compliant ones. We are planning to use the following algorithms in Enhanced RSA and AES Cryptographic Provider:

AES256 for encryption
SHA1 for hashing
RSA for key exchange with max key size

Is this setup going to work on WinXP SP3? Is it going to be FIPS 140-2 compliant? In my understanding, the answer to both questions in 'yes', but I want to be sure.

I can't help you with your Windows question, however I can chime in on FIPS:

  Is it going to be FIPS 140-2 compliant?

It might not be.  The problem is the "SHA1 for hashing"; SHA1 is no longer approved as a collision resistant hash function.  On the other hand, HMAC-SHA1 is still approved as a Message Authentication Code.

That is, if you are using SHA1 (within HMAC) to perform integrity checking, this is not an issue.  However, if you are using straight SHA1 as a part of (say) RSA signatures, this won't work; you'll need to switch to one of the SHA-2 algorithms (or SHA-3 when that is finalized).


Derive a secret from an RSA private key What I want to do is deterministically derive a secure key from an RSA private key, such that the RSA private key cannot be derived from the secure key.

The first approach that came to mind was simply using the private key (or some fixed part of it) as the seed for a PRNG.

Since the output of AES is random, another idea is to use AES to generate the secure key, using the first 256 bits of the RSA private key as the AES key, and encrypting some known data.

Can anyone verify either approach, or otherwise suggest an alternative way to do this?

EDIT
I left out the details of why I wanted to do this, to keep it focussed, but I guess it may be useful to know more:

I have an installer for a piece of server software that will run as part of a cluster. During installation, the installer will have access to a 'deployment' certificate - an X509 certificate that is used to sign certificates for each instance of the server (so, a CA certificate). Each server will also need to have access to a shared secret, which will be used to encrypt certain data that is shared between the servers (using AES). My thinking is that securely deriving  this shared secret from the deployment certificate private key during installation is a low friction way to do it.

Unless you really want to actually "use" the RSA key in a mathematical way, you could actually just derive a password from it using a key derivation function (KDF) and using the certificate as a password...
There are two different kinds of KDFs: those you use when you have a poor entropy and are afraid of Dictionary Attacks (typically if you store humanly memorable passwords) like Argon2, and those that you use when you have a good entropy, which is the case if you rely on an RSA key. In the latter case, the HKDF is well suited for this.
The advantage of using HKDF is that you already have all the nifty feature you should otherwise implement:

you have a Salt, so you can easily generate different keys, if one is compromised, for example.
you have the notion of the label, so you can generate different keys for different usages.
you have the size as a parameter, so you can easily plug in another encryption function in case AES gets broken, without changing the key generation algorithm.

Nonetheless, just hashing it would still be at least as hard as either:

finding your 'deployment' certificate
finding a preimage to that hash

And in case you worry, since an X509 certificate is certainly not a common password, it would require as much computation power to build a dictionary attack against it than to actually brute-force your certificate... (Which is hard.)
Note that 1. is true since we do not consider obscurity to be of any use, so you should assume that the attacker knows how you derive your secret key.
So in the end, if the "secret key" is compromised, finding the corresponding preimage (aka your certificate) of the cryptographically strong hash is hard for any cryptographic hash.
As hash, I personally like Blake2, since it can produce a digest of any size you may need for AES keys, is fast and is robust, plus it sports a Salt, so you can simply change that salt and keep going if a "secure key" is once compromised. But you could go with SHA-3 (aka SHAKE128 if you want 128 or 190 bits AES keys) and a custom salt you append to your certificate, too. Blake2X is also advertised as a KDF when you have a high entropy source.


Is it possible to validate an email address without the user actually revealing the email address? Say hypothetically I want a service where users express their opinions. But those opinions are heavily dependent upon where they work, and the best way to prove that they actually work at a specific place is by having access to an email address there. However, the service must guarantee that it (or anyone other entity) cannot know the user's specific email address, or else the user won't express their honest opinions.

Is this do-able?

So say I work at companyx, and my email is bob@companyx.com. When I sign up for this service, the service needs me to prove that I have access to a valid, current email address at the companyx.com domain. However I do not want to type in anywhere that my email is "bob@companyx.com" because then the service would know that I own that specific address. The service does not care that I specifically own "bob@companyx.com", just that I own some valid address at "companyx.com".

Your idea is exactly what is achieved in a recent paper:

  Blind Certificate Authorities.  Liang Wang, Gilad Asharov, Rafael Pass, Thomas Ristenpart, abhi shelat. At IEEE S&P 2018.

The server and client use secure multiparty computation to jointly make an SMTP+TLS connection to a mailserver, generating the appropriate encrypted packets to send an email to username@domain.com, so that the server doesn't learn username and the client doesn't learn the random challenge in the body of the email.


What are the practical differences between 256-bit, 192-bit, and 128-bit AES encryption? AES has several different variants:

AES-128
AES-192
AES-256

But why would someone prefer use one over another?

For practical purposes, 128-bit keys are sufficient to ensure security. The larger key sizes exist mostly to satisfy some US military regulations which call for the existence of several distinct "security levels", regardless of whether breaking the lowest level is already far beyond existing technology.

The larger key sizes imply some CPU overhead (+20% for a 192-bit key, +40% for a 256-bit key: internally, the AES is a sequence of "rounds" and the AES standard says that there shall be 10, 12 or 14 rounds, for a 128-bit, 192-bit or 256-bit key, respectively). So there is some rational reason not to use a larger than necessary key.

A larger key size also resists better to large quantum computer attacks: Using Grover's algorithm, a brute-force attack on any k-bit key block cipher would only take $O(2^{k/2})$ steps, so a 256-bit key would still give 128-bit security, while a 128-bit key could be cracked in 2^64 operations, which is doable. But as far as I know, the threat of QC was an ulterior rationalization; also, it does not explain the 192-bit key size.
(And quantum computers of this size are not yet in sight for the next some years.)


Protocol that generates keys every 2 minutes using KDC I am using a Key Distributed Center (KDC) and a key distribution protocol such as Kerberos. In order to limit the amount of ciphertext produced with the same
key, I want to renew the session keys every 2 minutes. However, for performance reasons I only want to involve the KDC once per hour.

I thought about extending this protocol by making use of the Diffie-Hellman key exchange but this would require generating a new alpha and a prime number each time which is quite expensive, considering it has to be carried out once every two minutes.

Any suggestion how I can extend this protocol in an efficient way please?

Look into the Signal protocol and its associated Double Ratchet algorithm. This changes DH keys after every message without much overhead. As no prime generation is involved in generating new DH keys, there is no expensive processing that would make this impractical. If you don't want to change as often as once per message, you can perform the ratchet once every n messages, or once every two minutes.

The Double Ratchet algorithm is designed to be what the designers describe as "self-healing". That is, if an attacker manages to transiently compromise the system at any point in time, they will be unable to retrieve any previous messages. Likewise they will not be able to decrypt any future messages. The protocol is fairly complex and must be in order to provide all the necessary security properties and recover from compromise. Simply regenerating your public keys every so often isn't always sufficient.

To improve security even further, you can also generate a new DH modulus from time to time, e.g. once a month. This does require generating new primes and can take a long time, but doing this makes precomputation attacks like logjam less feasible, even if attacking a non-export key becomes possible.


Would key stretching help mitigate concerns with "verifiably random"? Daniel J. Bernstein (and others) have expressed concern over how "verifiably random" curve parameters are generated.  He points out that hashing a public seed doesn't prevent, say, the US government (NIST/NSA) from choosing a seed that produces parameters with a one-in-a-million weakness that is not yet known to the academic community.

If the seed were hashed iteratively instead of just once, would this help address these concerns?  If my thinking is correct, iterating a hash function $2^{40}$ times on the seed when producing the standard should make one-in-a-trillion weaknesses mostly infeasible and one-in-a-million weaknesses much more difficult.

No, not really. The problem is that these kind of parameters may themselves be chosen deliberately. In other words, NIST/NSA may have performed a pre-calculation to make sure that the key stretching outputs a value that opens the algorithm up to some kind of attack.

Lets take an example, would you trust: SHA-256^2^40("Trust me, I'm an innocent string?"). Is that more or less secure than SHA-256^2^40("Trust me, I'm an innocent string"), i.e. without the question mark? How would I know that e.g. NIST or the NSA didn't do a few of these calculations up front to create their preferred output? the amount of iterations may be varied as well.

It's probably easier to secure the input of the hash. If they would say to a group of trusted experts: you all jot down a string, then concatenate them all (ordered by last name), and finally SHA-256 the ASCII string then the output is determined by the aggregated input of the experts.

The Brainpool curves were created in a controlled environment, which makes them more safe - according to DJB - than the NIST curves. Of course this is still less secure as not having to pre-determine any input values. This is the road taken by the highest level safe curves.


Crafting secure block ciphers that lack key expansion There was some article published by on the IACR's website that outlined a block cipher that only used the "master" key and no round keys. I can't recall the cipher's name, not that it matters, nor do I know if it had been subjected to cryptanalysis.

If one has a block cipher that has an $n$-bit key and an $n$-bit block size, what would be some ways that a secure one could be made that does not use key expansion?

The Even-Mansour construction gives you a block cipher from public, unkeyed permutations $P_1, \ldots, P_n$. It works like:

$$ x \mapsto  \cdots  P_2(P_1(x \oplus k_0) \oplus k_1) \cdots \oplus k_n $$

In original/traditional Even-Mansour, the round keys $k_i$ are independent. But recently there have been many papers studying the security of various "minimalistic" variants of Even-Mansour (basically any variant where the round keys are not independent).

The most minimal variant uses a "trivial key schedule" where $k_0 = k_1 = \cdots = k_n$. This variant naturally leads to a cipher that has no need for key expansion (key size is naturally equal to the block size). The following recent paper shows the security of 5-round Even-Mansour with trivial key schedule:

  Yuanxi Dai, Yannick Seurin, John Steinberger, Aishwarya Thiruvengadam: Indifferentiability of Iterated Even-Mansour Ciphers with Non-Idealized Key-Schedules: Five Rounds are Necessary and Sufficient, Crypto 2017


What is the length field in SHA-512 padding? If I am using SHA-512 on a message and need to determine the padding field and length field, how do I determine the length field?  I think I understand the padding, but not the length field.

For instance, if I have a 1919-bit message the padding field would be one 1 and zero 0's.  But what would the length field be?  1919?

In $\text{SHA-512}$ the size of the blocks is 1024 bit. The last block must contain:

the rest of data in message (mod 1024).
some filling (padding)
the last 128 bits as length

If the message is 1919 bit length:

Calculate the size of the data in the last block:
$1919 \mod 1024 = 895$
Add the size of length field(128 bit) to the last block size(895 bit), $128 + 895 = 1023$
See that we have to add 1 bit as padding to the last block to became 1024 bit

The answer will be:

size of padding field = 1 bit
data of padding field = 1
data of length field = 1919 as an unsigned 128-bit big endian integer 0x0000000000000000000000000000077F


What exactly is the purpose of the multi-tree variant in hash-based schemes? In hash-based signature schemes that use Merkle trees (e.g. XMSS), what is exactly the purpose of the multi-tree variant? Seems like the same number of keys can be represented by a single larger tree? Am I missing something?

What exactly is the purpose of the multi-tree variant in hash-based signature schemes?

The biggest reason for using a multitree variant is to keep the public key generation time reasonable, even if the upper limit on the number of signatures is huge.
With a single Merkle tree, the value of the root is a function of all the Winternitz public keys.  That is, if we wanted to create single Merkle tree that could sign (say) a trillion (circa $2^{40}$) messages, we would need to compute all $2^{40}$ WOTS public keys.  And, if a single WOTS public key requires a thousand hash computations (say, with LMS and W=16; XMSS would take about three times as many hash computations), we're looking at $2^{50}$ hash computations - that takes too long for most purposes.
In contrast, if we have multiple levels of trees, we only need to compute the top level Merkle tree; if that's a $h=20$ tree, then the same public key computation would take $2^{30}$ hash computations - still quite a lot, but far more feasible.
Of course, as we sign all trillion messages, we'll need to generate all trillion WOTS public keys as a part of that process.  However, the vast part of that computation can be done as a part of the trillion signature operations we'll (adding a small fixed cost to each one), and hence is never a large burden to an one operation.


Really simple RSA style public private key generator I am giving a talk to high school students and would love to do a real life encryption/decryption demonstration. I am not too familiar with the maths but is it possible to create like a 5-10 bit public-private key set, so I can get two teams to encrypt / decrypt  a message that is passed across the room? I need something simple enough to do on paper?

A simple example would be:
$e=3\;$ which is the lowest usable public exponent in RSA, and will simplify encryption
$p=23\;$ a prime such that $\gcd(p-1,e)=1$
$q=41\;$ a prime other than $p$ such that $\gcd(q-1,e)=1\;$ and
          also such that $e^2\bmod\operatorname{lcm}(p-1,q-1)\ne1$
$n=943=p\cdot q$
$d=147=e^{-1}\bmod\operatorname{lcm}(p-1,q-1)\;$ or $d=587=e^{-1}\bmod((p-1)\cdot(q-1))$.

Encryption of a message with symbols restricted to !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ and perhaps control characters such as LF, using public key $(n,e)=(943,3)$ is, for each symbol in the message:

convert the symbol to an integer less than 91 by using its ASCII code; for example, A would give $65$.
right-pad a random digit in range [0…9], yielding an integer $m$ less than 910, thus less than $n$; for example A giving $65$ and the random digit $7$ would yield $m=657$.
compute $c=m^3\bmod943=m^e\bmod n$ which can be done with a 9-digits calculator and a single final modular reduction (or by hand; in that case, or using an 8-digits calculator, we want to compute $m_2=m^2\bmod n\;$ then $c=m_2\cdot m\bmod n\;$); for example $m=657$ would yield $c=288$.
output ciphertext block $c$ as 3 decimal digits, with leading zeroe(s) if necessary.

Decryption using private key $(n,d)=(943,147)$ is more tedious, because it involves computing $c^{147}\bmod943=c^d\bmod n$. It can be done by left to right scanning of the binary expression of the exponent $147=10010011_b$, thus computing $c_2=c^2\bmod n\;$, $c_4={c_2}^2\bmod n\;$, $c_8={c_4}^2\bmod n\;$, $c_9=c_8\cdot c\bmod n\;$, $c_{18}={c_9}^2\bmod n\;$, $c_{36}={c_{18}}^2\bmod n\;$, $c_{72}={c_{36}}^2\bmod n\;$, $c_{73}=c_{72}\cdot c\bmod n\;$, $c_{146}={c_{73}}^2\bmod n\;$, $c_{147}=c_{146}\cdot c\bmod n\;=m\;$.

With $c=288\;$, we compute $c_2=903\;$, $c_4=657\;$, $c_8=698\;$, $c_9=165\;$, $c_{18}=821\;$, $c_{36}=739\;$, $c_{72}=124\;$, $c_{73}=821\;$, $c_{146}=739\;$, $c_{147}=657=m\;$; we then discard the rightmost digit giving $65$, and fetch the ASCII table to be back to A.

Notes:

Random padding is a necessary step in secure RSA encryption; the minimalist scheme used here is enough to hide repeated uses of the same symbol (with odds 9/10 for any pair of uses of the same letter). Many RSA illustrations with artificially small parameters omit random padding, thus are very vulnerable to construction of a dictionary of plaintext letter to ciphertext block, using only the public $(n,e)$.
With the artificially small parameters, and even though we are at the upper-end of the 10-bit limit of the question, there are two major weaknesses:

it is trivial to factor $n$ to yield $p$ and $q$ and compute a working $d$; we'd need to go to at least 320 bits to make this attack even so slightly challenging.
it is also possible to compute the 10 possible encryptions for each symbol (perhaps starting with the most common ones); this attack turns out to be easier than the normal decryption procedure for message of any significant size; larger parameters allow to fix this, see 6.

The condition $e^2\bmod\operatorname{lcm}(p-1,q-1)\ne1$ ensures that the public key can not be used as private key, which is all too common in artificially small RSA examples, and would introduce confusion in the audience if anyone tries it, perhaps by accident. Checking this condition is pointless in real uses of RSA, because it is true with overwhelming odds.
$d\equiv e^{-1}\pmod{\operatorname{lcm}(p-1,q-1)}\;$ is the necessary and sufficient condition for $d$ to be a working private exponent, and tends to ease calculations.
A spreadsheet such as Excel is suitable for such explorations, including with slightly less small parameters; it can easily handle modulus $n$ up to at least 25 bits; =MOD(A1*A2,A3) will compute $A_1\cdot A_2\bmod A_3$ exactly and =MOD(MOD(A1*A1,A3)*A1,A3)will compute ${A_1}^3\bmod A_3$ exactly, assuming $A_1$, $A_2$, $A_3$ are at most 24-bit.
Suitable parameters with 25-bit modulus are $n=28157923=4967\cdot5669\;$, $e=3\;$, $d=360863\;$; that allows encoding $0\le m<2^8$, with 5 decimal digits of random padding instead of 1.


Making ECDSA public keys one bit shorter In compressed form, ECDSA public keys are one bit larger than the curve size. There are some situations where this extra bit is extremely inelegant. So I had the following idea as a way to remove it.

For a public key, the extra bit is always zero and so does not need to be sent.
If a private key produces an extra bit of one in the public key, it is not used. (In SECP256K1, some private keys have to be folded anyway, so this would just be folding more keys.) One suitable folding method would be to generate a new random private key. Another, probably slightly less optimum, would be to keep incrementing the private key until a valid one was found.

I'm interested in the security consequences of doing this. The following are my educated guesses, in order of my confidence in them:

This is definitely no worse than picking an equally secure curve that is one or two bits smaller. So it can't be less secure than, say, SECP224K1 unless SECP256K1 is broken or SECP224K1 is somehow unusually strong.
This is actually stronger than that because although only half the private keys are valid, an attacker probably can't really take advantage of that fact.
In fact, it doesn't weaken the algorithm at all. We could probably even force the first 4 bytes of the public key to be zero if we wanted and the only real cost would be that it would be a lot harder to find a valid private key. The private key search space is actually no smaller, only the chance of colliding keys is higher, which is still effectively zero. Only reducing the private key space in ways an attacker can take advantage of make the algorithm less secure.

Am I correct?

I think your question can be reduced to the question whether there is a significant subset of weak public/private key pairs in any of the EC groups you mention. I am not aware of any such weakness, but if it exists, it would put a large dent in the security of Elliptic Curve Cryptography as a whole.

If there is no significant risk you will get a key pair with less than the expected security, if you generate it uniformly at random in accordance with the relevant standard, but without discarding key pairs that have a public key with unwanted properties, the risk will still be insignificant even if you discard on average every other randomly selected key pair based solely on properties of the public key. It is important to reiterate that this argument only holds if you do not modify the private key generation in any way, but only discard key pairs based solely on properties of the public key.

This argument is based on pure logic. If you get the expected security from each of 1000 uniformly generated key pairs, and the adversary sees the public key of each one of them, you get the expected security from each ~500 of those that have a public key with the property you want. If the latter had been false, clearly the former couldn't be true either. Reduction ad absurdum.


How to transform a text into numbers in the shortest way possible? My challenge is to transform a text into a representation of numbers 0-9. The number representation has to be as short as possible. What are the best options to achieve this?

Edit: I also need to transfer it back to text.

The best approach is to compress the text, then encode the output as decimal digits.

For the compression, the state of the art is complex; it was/is PAQ8 (used by the current holder of the Hutter Prize); PPM* is also quite good. In the realm of common, there's bzip2 and other methods based on the Burrows-Wheeler transform. In the realm of easily done, there's zlib, which is built in java.util.zip

Encoding the output in decimal is the easy part. A trivial method is to consider the bit string or octet string output by compression as an integer in a prescribed endianness, and convert that into decimal. The method is well known (basically: divide by 10, use the remainder as an output digit, and repeat dividing the quotient until that's 0). That's even built in Java's java.math.BigInteger (for big-endian). The only caveats are that with the big-endian convention, removing leading zeroes will be a disaster; the original length might be needed to allow decompression (depending on the compression method); and (with the standard algorithm outlined) execution time grows with the square of the size. If the later becomes a problem, one can subdivide the binary output into fixed-size blocks (except for an agreed-upon one, e.g. last), efficiently converted to a fixed size decimal output with a small size overhead. For example, 22 octets can be converted to 53 digits with less than 0.036% overhead, noticing that 25622 is just shy of 1053.

The reverse operation is trivial: convert from decimal digits to bitstring or octet string, then decompress. One caveat is that erroneous input might trigger strange bugs in the decompressor.

Note: The compression will make the output a lot shorter for real text, but in the worst case can cause a slight expansion (that can be limited to 1 bit). If the worst case size is what matters, remove compression.

Note: This is only tangentially on-topic, unless it is added encryption between compression and encoding as digits. In this case, the compression can have undesirable effect (like, ciphertext size leaking information on plaintext nature for one knowing plaintext length).


Which TLS features are vulnerable to chosen-prefixes collision on SHA-1? Gaëtan Leurent and Thomas Peyrin's preprint From Collisions to Chosen-Prefix Collisions - Application to Full SHA-1 (in volume 1 of proceedings of the forthcoming Eurocrypt 2019) shows a feasible chosen-prefixes collision attack on SHA-1. Given distinct prefixes $P_A$ and $P_B$ of equal length, the attack produces suffixes $S_A$ and $S_B$ with $\operatorname{SHA-1}(P_A\mathbin\|S_A)=\operatorname{SHA-1}(P_B\mathbin\|S_B)$. The attack has feasible cost: a few times that for shattered, which given prefix $P$ produces distinct suffixes $S_A$ and $S_B$ with $\operatorname{SHA-1}(P\mathbin\|S_A)=\operatorname{SHA-1}(P\mathbin\|S_B)$.

Which TLS features (ciphersuites, certificates, etc..) are vulnerable to such chosen-prefixes collision attack?

Executive summary:

The history of attacks on SHA-1, especially by Marc Stevens et al since about 2012, made people realize SHA-1 will get broken soon enough and it's time to stop using it. This process was complete before SHA-1 got completely broken, so nothing terrible happened with the latest publication.

So let's review how TLS uses hash functions.

As PRF to derive shared secret values (symmetric keys, IVs, nonces, MAC keys, etc.) from key exchange.

The PRF of TLS 1.1 and below uses SHA-1, but in HMAC. HMAC-SHA1 is not affected by the latest break.

SHA-1 is used in HMAC-SHA1 as MAC for the TLS Record Protocol, in cipher suites that use HMAC (i.e. cipher suites whose names end in "_SHA").

HMAC-SHA1 is not affected by the new break of SHA-1, so those cipher suites are not affected. You shouldn't use them anyway because it's MAC-then-Encrypt and there are many bad implementations in the wild (lots of Lucky13 variants, lots of POODLE variants).

SHA-1 can be used to issue leaf certificates and intermediate certificates.

SHA-1 certs have not been allowed for a few years (both leaf certs and intermediate certs). At the time, Facebook, Cloudflare and Symantec fought for SHA-1 certificates, the first two because they saw some traffic from clients that only support SHA-1 certificates and the latter because they had customers who were willing to pay a lot of money for such certificates to enable support for old hardware that can't be patched to enable SHA-256 certificates. A few CAs got caught issuing SHA-1 certificates after the deadline and were punished by browsers. This is all old news by now.

SHA-1 was known to be weak long enough in advance that the Web PKI TLS ecosystems is unaffected.

I suppose private PKIs using TLS are affected if they don't follow the best practices enforced by Web PKI, the CA/Browser Forum Baseline Requirements, Chrome security (as the largest browser, when they deprecate something it's dead), etc.

SHA-1 can be used for authentication, to sign the handshake key share messages ServerKeyExchange (DHE and ECDHE cipher suites) and CertificateVerify (only used with client certificates).

TLS servers that perform SHA-1 signatures over ServerKeyExchange message and TLS clients using client certificates that perform SHA-1 signatures in CertificateVerify messages using the key of their certificate might be vulnerable (I suppose those are almost exclusively RSA-SHA1 signatures, though I suppose other kinds can be used too).

I was under the impression that SHA-1 signatures produced by the TLS server itself have also been not allowed, but now I see that the TLS RFC doesn't say that, and there is a proposal to change the RFC.

Chrome removed support for ECDSA-SHA1 signatures in 2016.

Google said that they really want servers to support SHA-256 or SHA-512 for signing ServerKeyExchange (and Chrome might treat servers not supporting "modern TLS" as insecure), but I guess Chrome does not require it yet, so existing TLS 1.2 servers might sign ServerKeyExchange using SHA-1. I don't think the current attacks on SHA-1 let you do anything with this (it's a signature over client random, server random and server DH params).

Conclusion:

I think the current attacks only break SHA-1 CAs, and only those that issue certificates with predictable serial numbers (all of that has not been allowed for a while for publicly trusted certificates).

Recommendation: Don't use SHA-1 certs even if they are not publicly trusted, don't support SHA-1 signatures in the TLS handshake, use SHA-256 and SHA-512 instead.


Key rotation (or other measures) for PASETO v2 "local" I was looking at using PASETO's v2 "local" encryption (XChaCha20-Poly1305) to implement short-lived tokens to share claims between microservices via an untrusted client. PASETO's documentation is strong on its implementation detail, but I'm left with questions at a higher level.

Specifically, I want to avoid a scenario where an attacker could breach a key and use it to forge claims. I'm under the impression that the likelihood of an attacker brute forcing a key increases with time and quantity of encrypted data samples, so key rotation seems like a great way to limit both the time and available data related to any single key, as well as to limit the duration which any breached key would be useful for.

I see from this answer that the primary purpose of key rotation for symmetric ciphers is to limit the damage that would result if a key was breached (e.g. only the data encrypted by that specific key would be exposed). In our use case, the claims would not contain any sensitive data, so this is not a concern.

Is key rotation a valid approach to avoid an attacker being able to forge claims? Is it overkill? Is there something else I should consider?

Key rotation is important.

Besides data breaches, unintentional key disclosure happens. For example by committing an unintended file to a public GitHub repository. Also, people having access to a key today can take a copy of that key when they leave the company.

In case of PASETO, brute-forcing the key is not a concern. The key space is ginormous (2^256), so this is infeasible, no matter how much data is collected.

If you control all the applications using that key, and you probably do, key rotation should also be fairly easy to implement.