Term for non-ARX symmetric-key cryptographic primitive design strategy What's the term for describing designing symmetric-key cryptography primitive out of bitwise operations and shifts and rotations?

The closest thing I've found is this Keccek team's page calling it NORX, but the linked reference says NORX is actually an AEAD algorithm.

Primitives based purely on bitwise and shift/rotate operations can be described as being based on:

Binary Polynomials

Bitwise and, or, not, xor are element-wise $\mathbb{F}_2$ additions and subtractions; $n$-bit shift are based on multiplication by $x^n$ reducing $x^w$ where $w$ is the width of the word; rotation are based on multiplication reducing $x^w+1$.


The approaches in the question are leading nowhere.

In both the present question, and the other question that it links to, it is used textbook RSA encryption (no padding), and two public keys sharing the same public modulus. But the similarity stops here. In the present question the plaintext is enciphered with the first public key, that first ciphertext (that we do not get) is enciphered again with the other public key, and we only get the final ciphertext. In the other question, it was given two separately obtained ciphertexts, and that's central to the cryptanalysis method that was used.

There's no easy way to find a $d_1$ corresponding to $e_1=11$; whatever was made to get $d_1=2$, that's wrong. To find a $d_1$ directly, we would need a factorization of $n$ (or equivalent information), and it is 1022-bit, which is out of our reach for proper generation.

A first observation is that the first of the two chained encryptions perform $m\mapsto c_1=m^{e_1}\bmod n$; and the second $c_1\mapsto c={c_1}^{e_2}\bmod n$. Thus $$\begin{align}
c&=(m^{e_1}\bmod n)^{e_2}\bmod n\\
&={(m^{e_1})}^{e_2}\bmod n\\
&=m^{(e_1\cdot e_2)}\bmod n
\end{align}$$
and we see that the two encryptions are equivalent to one encryption using $e=e_1\cdot e_2$, which we can compute. But that alone is not enough to conclude.

The crucial observation is that $e_2$ is unusually large (1018-bit): there's seldom a good reason to use $e$ larger than the common $2^{16}+1$, which is 17-bit, and it is exceptional to use $e$ more than 128-bit.

This hints that $e_2$ (and/or $e=e_1\cdot e_2$) may have been chosen such that a corresponding private exponent $d_2$ (or $d$) is short. Like, a $d_2$ sizably shorter than $n$ was chosen, then it was computed an $e_2\equiv {d_2}^{-1}\bmod\lambda(n)$, where $\lambda$ is the Carmichael function (or same for $e$ computed from a short $d$). In practice that would be almost as silly as reusing the same $n$ is, and comparable to the sin of leaving aside random padding; but this obviously is a puzzle. For short-enough choice of $d_2$ (and/or $d$), such a poor key generation method would allow to carry Wiener's attack. If that succeeds, we can factor $n$ and conclude. As a shortcut, if we find $d$, we can directly use it to decipher $c$.

It turns out attacking either $e_2$ or $e$ works, I guess because the actual generation method chose $d$, computed $e$, then chose $e_1$ as a small factor of $e$.

Note: a question with the same numeric values was recently asked, and got rightly deleted as off-topic after failing migration (this one is better because there is some general question, and some level of effort shown). It was discussed in the side channel.


In A5/1 stream cipher, why are the specific bits in each register chosen for the majority rule and for the XORing step? My two part question is:

1) How are bit positions 8, 10, and 10 chosen for the majority rule for the respective registers?

2) How are bits {13, 16, 17, 18}, {20, 21}, {7,20, 21, 22} chosen for the XORing step for the respective registers, and why the different number of bits for each register?

Were they arbitrarily selected when designing the protocol or is there some advantage to using these bits specifically and this number of bits from each register?

Welcome to crypto.stackexchange. Your second question could be easily answered by a simple search on this site, or elsewhere, but anyway, here goes:

Firstly, A5/1 is well-broken, the non-uniform clocking ends up not helping much, and lots of different initial states merge as the clock ticks--look at the Wikipedia page for A5/1 for a long list of papers with attacks. Now, onto your questions:

Question 1: The majority rule bit positions are not so crucial, as long as they are not from a bit which is being fed back, or from the output bit. Also your observation in the comments: "if you used the same index for all registers, you would get a loop where all the registers shift each time" is incorrect in general. Depending on loading and feedback same any 3-tuple of bits can end up in the majority positions.

Question 2: The LFSRs used are primitive, their tap positions correspond to primitive polynomials, and give the maximum possible output sequence period of $2^L-1,$ if $L$ is the length of the LFSR, a so called maximal length sequence. So the tap positions are crucial. For more on LFSRs and periods, see, for example, the following question which asks what happens when you have non primitive LFSRs.

With the three LFSRs in A5/1 having relatively prime lengths $19,22,23$, (thus relatively prime periods) the internal state of the cipher has possible size $(2^{19}-1)(2^{22}-1)(2^{23}-1)$ instead of being much smaller. Of course due to irregular clocking not all states need be visited.


Storing Credentials for a Third Party (Originally posted to SOF, but I got no answers)

I am designing a small application for use inside my company. My application needs to connect to a third party website on behalf of my application user. I would like to safely store the user's credentials for the third party site in my database. Obviously, storing the third party password as plaintext is out of the question.

What I am proposing is the following:

When a user creates an account in my application, the application generates two salt values.
The user enters a new password for my site as well as credentials for the third party site (username and password).
My application uses the first salt value and PBKDF2 or bcrypt to hash the user's local password. This hash is saved in the database for later authentication.
My application uses the second salt value and the same key derivation function to generate a second hash. The second hash is used to AES-encrypt the third party credentials. The encrypted credentials are saved in the database for authenticating to the third party site.

The only weakness that I can find is that if the users' local password is weaker than the third party password, an attacker need only guess the local password and both are compromised.

Are there any other problems with the algorithm? Is there a better way to accomplish the same result?

I've written extensively about how to solve this problem, over on the IT Security Stack Exchange site.  Let me point you to my answers over there:

What is the best way to securely keep clear passwords?
How can I create a service that automatically logs onto a third-party service without storing credentials in plain text?
How should you store a password that needs to be retrieved as plaintext?

Basically, I'm suggesting you set up a separate machine that stores people's credentials for the third-party website as well as a hash of their local password, authenticates the user, and then connects directly to the third-party website.  That separate machine should be secured and locked down as carefully as possible, to reduce the likelihood that it is compromised.  But read those links for all sorts of extensive details and suggestions.


Is it possible to translate a piece of language into your own without knowing the language? I understand the the texts within the Voynich Manuscript are of an unknown language, and yet cryptographers are still working on it and still trying to decipher it. Does that mean that it is possible to crack any piece of writing even if it's in a language you don't know, and assuming you have no access to any tools that can translate the language?
For example, let's say I see a piece of writing in Arabic, which obviously has no cohesion to English. Is it possible to translate it just by working on that piece of writing alone without nothing else? If so how would I go about this?

A core assumption of natural languages is that conceptual frequency and the grammar to construct and articulate concepts is not evenly and randomly distributed; so pattern discovery can occur.

However, two problems can quickly arise:

If the language sample (or collection of samples) is too small, the patterns may not be distinct and consistent. Cretan Linear A for example lacks a large enough corpus for robust patterns.
If you have a decent corpus with lots of patterns, say a 1GB block of natural language text, the language could still be hermetic. You may know how symbols relate and which should occur when but you would still need intense in-depth knowledge of the human brain to map each pattern to the most probable human motivation or abstraction. So the language would have be of human origin with no explicit intent to befuddle the uninitiated reader.

If I chose a novel in a language I don't know (say Russian) and converted it into Wingdings; my brain would still feel that the text "fits" my innate idea of written language without knowing why. Ilmari Karonen is correct that this problem is inherently cross-disciplinary.

The cryptanalytic curio is that a natural language isn't secure according to mathematical models but can still be completely unintelligible, thus serving the same outcome. This is a security-through-obscurity irritant that some cryptanalysts love to scratch. :-)

So yes, it is possible with the right provisos. If you can decipher a previously unknown natural language with a large corpus, yet disassociated from all other languages - you will probably win a Nobel prize in something.


Why is padding used in CBC mode? I am newbie to CBC crypto: When I try decrypt the cipher text to recover the plain text, things are not going smoothly as I face some issues in the decryption process with padding and not obtaining the plain text finally.

So I would like to know about why padding is used in this CBC method?
Why is it not used in the ECB method? Should we pass padding for the decryption process?

Below are the cipher text and IV which I have used in my testing:

cipher text(hex) - 6d 25 1e 90 44 b0 51 e0 4e aa 6f b4 db f7 84 65

Initialization Vector(hex) - 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

Expected Plain text(hex) -  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

Could someone try this ciphertext and IV and share the results?

Key size: 16;

Key used in hex: 10a58869 d74be5a3 74cf867c fb473859

So, I'll answer the theoretical part of your question, since we need a key to address the practical part.

Why is padding used in CBC?

Blockcipher such as AES are encrypting blocks of a fixed given size only, we call it the "blocksize". So, what if your data is smaller than the blocksize ? An easy solution is to add what we call "padding" to your plaintext in order to have its size match the block size.
So, padding is there to allow you to encrypt data smaller than the blocksize... But what if you want to encrypt something bigger than your blocksize?

That's where the mode of operations, such as CBC, come into play. Modes of operations are there to allow you to encrypt more data than the blocksize of your symmetric blockcipher.

But since those modes of operation are still using the underlying blockcipher to encrypt data, it means that they can only encrypt a multiple of the blocksize. So, if you have $4\ell$ bits of data to encrypt, for $\ell$ the block size of your cipher, then you're fine.
But what if you have $4\ell+5$ bits of data? (I am assuming the blocksize does not divide 5.) Then you need to pad the data with $\ell-5$ bits of padding in order to end up with a multiple of the blocksize of data ready for encryption with your mode of operation.

There are multiple methods to pad data, which can completely undermine the compatibility of a given encryption program with others. The most used padding method in symmetric ciphers and mode of operation is certainly PKCS#7.

Worth noting

There exists methods to avoid padding, in order to avoid padding completely so the ciphertext is the same size as the plaintext, the most common of those methods is certainly the one called ciphertext stealing.

There also exists modes of operation, such as CTR, which do not need any padding.

Now, contrarily to RSA encryption for instance, padding in symmetric encryption does not add security.

Checking the padding upon decryption can allow to catch errors in the transmitted ciphertext, because of the avalanche effect, (depending on the mode of operation used), but can also lead to terrific padding oracle attacks.

As explained in that question, it is better to use a cryptographic MAC to protect your ciphertext, and verify it first before performing decryption or even padding checks. I also refer you to that legendary question, regarding the way one should MAC its data when using encryption.

About ECB

Actually ECB also encrypts only multiples of the blocksize, so you will also need padding or another method to have enough data to encrypt. However, you should not use ECB for the reasons pointed out there.

Regarding your practical problem

So, I've tried your values:

from Crypto.Cipher import AES
import binascii

key = binascii.unhexlify("10a58869d74be5a374cf867cfb473859")
iv = binascii.unhexlify(16*"00")

plaintext = binascii.unhexlify(16*"00")
ciphertext = binascii.unhexlify("6d251e9044b051e04eaa6fb4dbf78465")

ciph = AES.new(key, AES.MODE_CBC, iv)

test1 = ciph.encrypt(plaintext)
print("The ciphertext is what we expected:", test1==ciphertext)

#We need to reset the cipher to get the correct IV
ciph = AES.new(key, AES.MODE_CBC, iv)

test2 = ciph.decrypt(ciphertext)
print("The recovered plaintext is what we expected:", test2 == plaintext)

and as you can see if you try it with Python and PyCrypto, it works but your ciphertext strangely differ from the actual value at offset 4, as pointed in the comment by fgrieu. The actual value is 69, not 90.

This error at offset 4 explains why you couldn't get the correct recovered plaintext, because of the avalanche effect, the whole AES block was being impacted by that little mistake.


Curve25519 extension field The paper regarding curve25519 presents a theorem in chapter 2 (specification). The extension field $F_{p^2}$ is used in this theorem. I don't understand why this extension field is needed for the curve25519. This is how far I got:
The theorem implies that for some elliptic curves $E$ exists a unique $s \in F_p$ for every point multiplication $n \cdot Q$ ($s$ is the x-value of the resulting point). Point multiplication can be done using the Montgomery Ladder. Curve25519 has a base point $P = (9,y)$, where $y$ is not used in the Montgomery Ladder. Because $P$ is a point on the Curve, the point multiplication $P' = n \cdot P$ has also to be a point on the curve. Now one can multiply another scalar with $P'$ which again results to point on the elliptic curve.
In this context, only $F_p$ should be needed for the curve25519.
Hence, I think that the extension field is only used, if you consider the point multiplication for all point $Q = (q,r)$ for every $q \in F_p$. That means $Q \notin E(F_p)$ but $Q \in E(F_{p^2})$. I don't understand why this case in considered, when it is never used.

I don't really know so I'll tell you my best guess: One of the design goals was "free point validation". To do this, we want to make sure that no matter what $x$-value in $F_p$ we're sent, it is a valid point on the curve.
If $x\in F_p$, then to make an elliptic curve point we need $y$ such that $y^2=x^3+488862x^2+x$. But we have no reason to expect that $x^3+488862x^2+x$ will be a quadratic residue, so in general we will need to define $y$ over $F_{p^2}$. Thus, if I send you any value $x$ in $F_p$ and tell you it's a point on the curve, you know that there is some $y\in F_{p^2}$ such that $(x,y)\in E(F_{p^2})$, but you have no guarantee that $y\in F_p$.
The key exchange uses $x$-only arithmetic, so the key exchange will never need to use the extension field in any computations. Theorem 2.1 tells us that all multiples of a point with an $x$-value in $F_p$ will also have $x$-values in $F_p$, which proves correctness of the $x$-only arithmetic, more or less. So I think the case of $Q\in E(F_{p^2})$ but $Q\notin E(F_p)$ is used, but only via an implicitly-defined $y$-value.


How can I generate a deterministic evenly distributed random number in a blockchain Here's the hypothetical. There's a blockchain, which for the sake of simplicity, is modelled around Bitcoin and proof-of-work.

My goal, is that for each mined block, rather than a set reward (12.5 BTC), each block has a deterministic reward value, and that value can only be determined after the block has been submitted. Here's the process:

The miner constructs a block.
Once a block hash under target has been found (through POW), the miner submits the block, not yet knowing the reward they will receive for mining that block, because it is computationally complex to derive it.
Once outside the reach of possibly manipulating the output hash to optimise the value, likely by time passing "mining" the value, the value for that block is finally uncovered, and is easy to verify as quickly from the block hash.

I've looked at a few possible solutions for this, like collecting entropy from previous blocks, future blocks, etc., but it always comes back to the issue of actors optimising blocks to get a good final value for the block.

The second issue I've thought of, is how solutions to the values of blocks will be distributed in the network. How would a solution to the block value be stored? Could they be sent in parallel to the blocks, and then each client can verify the solutions as they receive them?

Am I thinking about this the wrong way? Here's a thread on my previous research into the topic.

You are looking for a Verifiable Delay Function (VDF). Roughly VDFs are functions which are hard to parallelize but easy to verify (for some sense of easy).

One simple example is to just iterate a hash function, although this has linear verification time while more advanced functions may have sublinear verification complexity.

Here is an overview of VDFs for deterministic unpredictable values


AES encryption without salt and IV I need to encrypt blocks of 16KiB with AES256. I have only one requirement to satisfy - If one day a hacker gets the data without the keys, he will not be able to decipher the data.

According to the design:

Each block will have a different random key
Blocks are differ from each other

Due to a space problem, i'm planning to use no salt and no IV.

Given 1 + 2, is it still safe to waive the salt and the IV?
Which mode should i use?

Thanks

There are two blocks to consider here. The 16KiB blocks you mention you have to encrypt and the blocks as encrypted by the AES block cipher. Let's call your blocks fragments.

ECB is secure for blocks that are not related to each other in any way. Your fragments, however unique, may still contain blocks that are not unique. If this is the case then ECB will leak information about identical blocks. CBC will overcome this, especially if each block has it's own key.

So:

  Given 1 + 2, is it still safe to waive the salt and the IV?

Yes, but not for ECB; ECB is almost never a good idea.

  Which mode should i use?

CBC or any other mode that is secure for protecting data at rest.

You need an authenticated cipher or MAC if you also require integrity and authenticity. These are basically always required within transport protocols.


Building large S-Boxes from smaller ones I would like to make an exhaustive list of all relevant techniques that have been studied in order to build a large S-Box from smaller ones.
As far as I known, three structures are usually preferred:

The Lai-Massey construction (used to design the IDEA block cipher)
Feistel networks (used to build $2n$-bit permutations from $n$-bit permutations)
MISTY networks (initially combines an $(n-1)$-bit S-Box with an $(n+1)$-bit one in this document)

Notably, this publication analyzes pros and cons of using either Feistel or MISTY networks to build 8-bit S-Boxes.

Are there any other relevant techniques to design large S-Boxes from smaller ones?

Yes , there are others such as SPN (CLEFIA , Khazad Middori-128 ,etc)

in addition to xor-based Feistel  structure , the Kuznyechik is based on product-based Feistel  structure.

I suggest to read this thesis (it summaries all) : CRYPTANALYSIS, REVERSE-ENGINEERING AND DESIGN OF SYMMETRIC CRYPTOGRAPHIC ALGORITHMS


Hamiltonicity proof of knowledge I'm learning the POK notion and definitions and as a self exercise I wante to prove the statement that the Hamiltonicity protocol is a POK system with knowledge error $1/2$.

So the question will be self-contained, I provide here the slide describing the protocol (credits to Moni Naor, Weizmann institute).

And the definition as copied from Goldreich's book (Foundation of Cryptography):

  Definition 4.7.3 (system for POK): Let $R$ be a binary relation and $\kappa :N\rightarrow [0,1]$. We say that an interactive function
  $V$ is a knowledge verifier for the relation $R$ with knowledge error
  $\kappa$ if the following two condition holds:

  Non triviality: There exist an interactive machine $P$ s.t. for every $(x,y)\in R$, all possible interactions of $V$ with $P$ on
  common input $x$ and auxilary input $y$ are accepting.
  Validity: $V$ satisfies the Validity requirement with knowledge error $\kappa$ if there exist a polynimial $q(\cdot )$ s.t. for every
  $P^*$, every $x\in L_R$, there exists a probabilistic oracle machine
  $K$ with oracle access to $P^*$, that run in expected polynomial time
  ad outputs a witness with probability at least $\frac{p-\kappa(|x|)}{q(|x|)}$ where $p$ is the probability that $P^*$ succeeds to
  convince $V$ to accept on common input $x$.

My Intuition:

First, it is known that if the commitment scheme is perfectly binding then the above protocol is a IZK proof system with soundness $1/2$.

Non-triviality requirement is trivial to satisfy (specifically, $P$ from the protocol itself satisfies it).
In regard to the Validity requirement, it is easy to construct a Knowledge Extractor

My question:

We know that the soundness of this protocol is $1/2$, so $p\leq 1/2$. Now, it required that there exists a poly $q$ s.t. $K$ succeeds to extract a witness with probability at least $\frac{p-\kappa (|x|)}{q(|x|)}$. If we assigne $p\leq 1/2$ and $\kappa =1/2$, how can such a $q$ exist?

Let $q$ be given by $\:$ for all $n$, $\: q(n) = 1 \;\;$. $\;\;\;\;\;$ For every $P^*\hspace{-0.05 in}$, every $\: x\in L_R \:$,

$\frac{p-\kappa(|x|)}{q(|x|)} = \frac{p-\kappa(|x|)}1 = \:p\hspace{-0.04 in}-\hspace{-0.04 in}\kappa(|x|) \: \leq \: p\hspace{-0.04 in}-\hspace{-0.04 in}0 \: = \: p \: \leq \: 1 \;\;$.

For every $P^*\hspace{-0.05 in}$, every $\: x\in L_R \:$:

Since $\: x\in L_R \:$, $\:$ there exists $y$ such that $\; (x\hspace{.02 in},\hspace{-0.02 in}y)\in R \:\:$. $\;\;\;\;$ Let $w$ be a minimum-length

example of that, and let $K_w$ be the oracle machine that immediately outputs $w$ and then halts.

Since $K_w$ ignores its input and halts, $K_w$ runs in expected polynomial time.

Since $K_w$ outputs $w$ with certainty and $w$ is a witness, $K_w$ outputs a witness with certainty.

In particular, its probability of outputting a witness is at least $\frac{p-\kappa(|x|)}{q(|x|)}$.

Therefore the given Validity condition holds.

Conclusion: $\:$ That book's Validity condition is trivial.


Is AES without T-Tables nor S-Box resistant to side-channel? T-Tables and S-Boxes are prone to side-channel attacks, is an implementation without any lookup tables resistant to side-channel ? In this answer, https://crypto.stackexchange.com/a/63520/80926, the author says that secret-dependent if statements, loops and mathematical operations like multiplications may not be constant time, can they make a side-channel attack possible ? ( On an implementation without any llokup tables ).
If they can, what can we do to have a side-channel resistant implemnetation of AES ? Because it seems that it is much slower than a regular implementation.
Is bitsliced the only solution for a device without AES-NI ?

Is an implementation without any lookup tables resistant to side-channel ?

That's only answerable by no unless it is added some limitation to the attack capabilities of adversaries. No implementation of cryptography involving a secret is resistant to sufficiently advanced side channel-attack. What was resistant a decade ago is no longer now, that's been true for the >3 decades I watched that game (I believe before that), and history will repeat itself, I guess.
Specifically, I'm ready to bet that the first applications to cryptanalysis of the advanced technologies currently developed in quantum computing will be sensitive/fast sensors for side channel-attacks then carried with classical computers.

Secret-dependent if statements, loops and mathematical operations like multiplications may not be constant time, can they make a side-channel attack possible ?

Yes, they have the potential to create a side-channel by timing. But for the AES block cipher, once lookup tables are removed or made constant-time, timing side channels are easily avoided (just don't explicitly test a data or key bit). Other side channels (probing, power analysis, electromagnetic emission), and fault attacks (which are not always classified as side channels, but stand in the same league) are the difficult ones.

Is bitsliced the only solution for a device without AES-NI ?

No. There are security-evaluated AES hardware and even software implementations that do not use bitslicing. Their internal design is typically secret (well-guarded from me, at least), and even their API is under NDA. See this marketing material from a company licensing IP in that field.
And if we restrict to side channels by timing, it is possible to remove theses in software-only AES and keep lookup tables. Fast, simple, secure, portable: pick one, perhaps two.

Can an attack (by side-channel) on an (AES software) implementation without any precomputed tables nor any test on key or data but without any additional security like bitslicing be performed over the network in practice with current technology ?

It depends on what's meant by "attack" and "over the network".

No, for attacks aimed at recovering the AES key being used based on timing measurements of network packets. The precautions stated have fully deprived the adversary of information thru that side-channel. It is even doubtful that we really need the "without any precomputed tables" part of the statement for anything else than a simple thus strong argument.
Yes, otherwise:

Software often ends up using the deciphered data in ways that leak information about that data (not the key under use) thru a timing side channel exploitable by remote timing of network packets. Padding oracle attacks are one class of such attacks. They can reveal a key under transfer.
Exploitation of bugs (buffer overflow…) and miss-configuration in the software using the AES implementation under attack is a very real threat.
When an adversary accessing the machine "over the network" has or gains the ability to run facilitating code on the machine under attack, we can't rule out a side-channel attack: there's a steady flow of new or slightly different architectural CPU side-channels discovered on CPUs which promised process isolation, even recent ones. And there are even more attacks on OSes and virtualization environments with the net effect of breaching process isolation.

The most secure ways to rule out key leak "over the network" involve not manipulating the key with a general-purpose modern computer¹. Like, keeping keys in a dedicated security device (Smart Card, TPM, HSM). That can give strong insurance against key leak, but not key abuse: it remains possible that an adversary remotely deciphers data enciphered with the key.

¹ I nearly wrote a networked general-purpose modern computer, then went back: there are reports of side-channel attacks that could be carried using a nearby compromised networked computer.


Are there security issues with discrete logarithm keys not being uniformly distributed? Generally, algorithms based on discrete logarithm specify that private keys are chosen as scalars between 1 and the order of the group (denoted $q$ here). For instance IEEE P1363 and FIPS 186-3 both specify this range for DL private keys. Is it a problem if the key is not uniformly chosen from this range?

One possibility would be choosing a random integer of $k=\log_2(q)$ bits and reduce it mod $q$. In this case, the private key would be more likely to be in the range $[1,2^k-q]$ than otherwise. Another situation where this would occur is if the implementation fixes a top bit, for instance repeatedly generating $k$-bit integers until one less than $q$ is generated). So the attacker knows the key is not in the range $[1...2^{k-1}]$.

How much of an advantage do attackers gain when key generation techniques like these are used? Obviously the total key space is reduced, but is there a reduction in security beyond that? For instance is a DSA key with 160 bit $q$ and $x$ fixed to being 159 bits easier to break than a DSA key with 159 bit $q$ and $x$ fully random?

The discrete logarithm problem can be attacked with either a specific or a generic algorithm. A specific algorithm is one that tries to exploit structural weaknesses of the specific group in which discrete logarithm is used; e.g. Index Calculus when we are talking about exponentiation modulo a big prime. Generic algorithms only use the group law and thus work on "any" group. For normal elliptic curves (excluding those which allow for an efficient pairing), no specific algorithm is known.

For a group with $N$ elements, where the private key is chosen uniformly, the best generic algorithms work with cost $O(\sqrt{N})$; so with a 160-bit group you have security $2^{80}$. If the private key is not chosen uniformly, then the generic algorithm can be adjusted to take that into account: ultimately, this is equivalent to reducing $N$. In your examples, the "equivalent" $N$ is no smaller than $q/2$, so you reduce your security by no more than a $\sqrt{2}$ factor: not really worth worrying.

However, in (EC)DSA signature generation, a new value (called $k$ in FIPS 186-3) must be generated modulo $q$ for each signature; it is sometimes called a "transient private key". Contrary to the private key $x$, the value $k$ MUST be generated uniformly. For instance, if $k$ is chosen by selecting a sequence of random bits of length one less than the length of $q$, or if $k$ is selected by taking a sequence of random bits of the same length than $q$ and reducing it modulo $q$, then the private key $x$ can be reconstructed by observing many signatures and total cost $2^{63}$, which, while still big, is substantially lower than the expected $2^{80}$. This was found by Bleichenbacher in 2001; I am not sure it was formally published anywhere (Vaudenay talks of it as a "private communication"). The problem here is not in the discrete logarithm per se, but in how $k$ and $x$ are used in the computation of $s$ (the second half of an (EC)DSA signature).

The current FIPS 186 (FIPS 186-3) fixes that issue by generating a bit sequence at least 64 bits longer than $q$, then reducing it modulo $q$ (this makes the bias small enough to be unimportant). In X9.62-2005 (the ECDSA standard), they simply generate bit sequences of the length of $k$ and start again if this yields a value which does not lie between $1$ and $q-1$.

Either way, for a properly secure (EC)DSA signature generation, you must have a way to generate reasonably unbiased $k$ values; hence, you can use the same generator for producing the private key $x$.


How bad is it to use the identity function as hash for ECDSA? I was recently asked whether a certain library supports the ECDSAwithNone Signature algorithm. Clearly this would mean ECDSA with the identity function as the hash function. I know this is a really bad idea. And I also know that there's a trivial attack if two messages have the same prefix as the "hash" gets truncated to the first q bits (q being bitlength of the order of the curve).

However I wanted to know: What are the "worst" possible attack(s) against this signature scheme?

The worst attack is hereby defined to be the attack that needs the least known or chosen signatures while being executable in reasonable amount of time.

There is a way to generate forgeries for (EC)DSA when the hash function is not one-way:

Let $n$ be the order of the group, $P$ a generator, and $Q = aP$ for some secret $a$;
Pick arbitrary $\alpha$ and $\beta$ $\in \{0, \dotsc, n\}$;
$r = x \bmod n$, where $(x, y) = \alpha P + \beta Q$;
$s = r \beta^{-1} \bmod n$;
$h = s \alpha \bmod n$;
Invert $H(h)$ to get $m$. Since we are using the identity function here, $m = h$.

You can verify that $(h s^{-1}) P + (r s^{-1}) Q = (\alpha P + \beta Q)$, whose $x$ coordinate is precisely $r$. Therefore this is indeed a valid signature.


JWT Common Practices I had a few questions in regards to certain practices used by JWT developers.
I'm relatively new to both encryption and JWTs and the context given is for developing a system on nodejs.

How should verification work? Should I look at the JWT's signature section and verify with the private key each time? Or should I store the token in a No-SQL database and see if it contains it for verification (checking expiration dates too)?
How many bits should each secret key be? Is 2048 too much? What's the 'good medium'?
Is RSA with the HMAC SHA256 signing method okay? What's the best method for key creation? Should keys be generated on multiple occasions (ie. per server startup)? Or is having it static fine?

How should verification work? - JWT documentation are your friend.
Should I look at the JWT's signature section and verify with the private key each time? - https://scotch.io/tutorials/the-anatomy-of-a-json-web-token
should I store the token in a No-SQL? - NO, there's no need if you are able to decode the token that mean the token is valid.
secret key be? it's depends the bigger the key the slower your api so its a trade off (remember you need to decode the token on every request)
Is RSA with the HMAC SHA256...? Most people using HS256,

I'm recommending for you to check out this url

Hope it helps,


Efficient Incremental Updates to Large Merkle Tree I have a data set with 300 Million entries and every 5 minutes 4000 random entries in this table change.  I need to calculate the merkle root on this data set to validate integrity multiple times every 5 minutes.

Assuming sha224 hashes this would be 8 GB for just the leaf nodes and almost 16 GB of data would have to be processed via sha224 to calculate the root and would take over 5 minutes to calculate.  To accelerate the calculation I must cache the tree and make incremental updates.

Is there a any known approach to accelerate incremental updates without requiring 16 GB memory mapped merkle tree?

Yes, you should be able to handle this situation readily.  There are many optimizations available.

One key observation is that if you're going to go to disk, then you might as well read lots of data: it takes just as long to read an entire block of data as to read 1 byte.  So, I suggest you store the data on disk in 4096-byte blocks, and do a Merkle tree over these blocks.  In particular, you will have one leaf per 4096-byte block.  Then you can store the Merkle tree in memory.

Second, there's no need to use SHA224.  A 160-bit hash is sufficient, so you could use SHA1 (or SHA224/SHA256) truncated to 160 bits.  This way, each hash will be 20 bytes long.

How will this perform?  Each 4096-byte block on disk can store about 200 hashes.  Therefore, you'll have about 1.5 million blocks.  Treating the hash of each block as a leaf, we have a Merkle tree with 1.5 million leaves.  Such a Merkle tree has 3 million nodes in total, which you can store in memory using just 60 MB of RAM.

Every 5 minutes, 4000 random entries will be modified.  This requires you to read 4000 blocks from disk, update them, recompute their hashes, and update the Merkle tree.  To read the 4000 blocks, update them, and write them back out to disk will involve reading 16 MB of data and writing 16 MB of data; no problem.  Hashing all of this data will take about 40 ms, since you can hash a 4096-byte block in about 10 microseconds.  Then, you'll need to update about 8000 nodes in the Merkle tree.  This involves computing 8000 hashes on short inputs, which will take about 4 ms, since it takes about 0.5 microseconds per hash of a short input.  Overall, the performance impact on your system should be very low.  (These numbers are on one particular machine I happened to have laying around, using SHA1.  Your numbers may vary by a constant factor, but probably not by an order of magnitude.)

Overall, this solution should perform extremely well, both in memory consumption as well as in CPU usage.

If you want to squeeze out every last byte of RAM, there are other tricks available.  You can save up to a factor of 2x in memory usage if you use a tree with a much higher branching factor, rather than a binary tree (though this will cost you a little bit in CPU utilization).

Also, you can safely truncate the size of the hash down to about 80 bits (10 bytes), if you use a UOWHF.  One way to do this is to pick a secret 128-bit key $K$, and then the hash of the data $X$ is $H(X || K)$ (i.e., append $K$ to the data before hashing), truncated to 80 bits.  The use of the key $K$ (i.e., the use of a UOWHF) eliminates the opportunity for birthday attacks, so in this situation, 80 bits is enough.  This can save you another 2x in memory usage.


When does multiple OTP encryption become insecure if new keys are permuted?  I understand that OTP encryption fulfils perfect secrecy, meaning you can't decrypt the encrypted text to it's original plaintext (and know that this plaintext is indeed the original plaintext) unless you possess the OTP key.

Let's assume this:

Alice creates a truly random alphabetical stream of 10 characters (key).
The key is shared with Bob (we assume that it's secure and no one else can get knowledge of the key)
Now Alice can encrypt a text with length $\le$ key-length
Encrypted text is sent to Bob
Bob can decrypt the encrypted text with the key

Now the "new" part:

Alice again wants to sent a message to Bob by using OTP-encryption. But instead of creating a completely new truly random OTP key, Alice permutes the previously used OTP key. This permuted key is then used for further OTP encryption/decryption. The permuted key is checked with previous keys to ensure that no encryption happens with an identical key.

We assume that Bob always receives the new (permuted) key over a secure channel and no one else (ever) knows the key. We also assume that no one else knows any plaintext messages before/after encryption/decryption.

Example of keys:

$k_1 = \text{gubapqrytt}$ (truly random)

$k_2 = \text{permute}(k_1) = \text{ptyaqgtbur}$

$k_3 = \text{permute}(k_2) = \ldots$

Does this affect the security of OTP?
When is the first message vulnerable to decryption by an adversary?
Do all further keys (if none get leaked) still provide perfect secrecy?

EDIT:

We assume that all keys are kept secret and no keys will be leaked (no matter how unrealistic this might seem). I'm only concerned if this scheme would somehow be vulnerable to any known attacks, like frequency-analysis, since the key has always the same characters.

This is an inconsequential variation on a two-time pad and falls just as readily.

Say your pad is $n$ symbols long.  Fix a permutation $\pi \in S_n$ of $\{1,2,\dots,n\}$—this is determined by your $\operatorname{permute}$ operator.  If the pad is $(p_1, p_2, \dots, p_n)$ and the $i^{\mathit{th}}$ message is $m_i = (m_{i,1}, m_{i,2}, \dots, m_{i,n})$, then the $i^{\mathit{th}}$ ciphertext $c_i = (c_{i,1}, c_{i,2}, \dots, c_{i,n})$ where $$c_{i,j} = m_{i,j} + p_{\pi^{i-1}(j)}.$$  Here $\pi^i(x) = \pi(\pi(\cdots \pi(x)\cdots))$ is the $i$-fold iteration of $\pi$, with $\pi^0(x) = x$.

So far this is just a restatement of your system, with specific names given to each symbol in the message, pad, and ciphertext.

If I learn the ciphertext $c_1$ of a single known message $m_1$, then I can trivially recover your pad by $$p_j = p_{\pi^0(j)} = c_{1,j} - m_{1,j},$$ and then decrypt the next ciphertext $c_2$ or any other by simply permuting the pad $(p_1, p_2, \dots, p_n)$ with $\pi$.

Obviously, if I don't know $m_1$ exactly but can narrow it down to a small set of options, then I can narrow down the $p_j$ to a small set of options too, and thus narrow down $m_2$, and so on.

In general, if the pad for the first message is $p$, the pad for the second message is $F(p)$, the pad for the third is $F^2(p)$, etc., where $F$ is a fixed function of pads (in this case, $F(p_1, \dots, p_n) = (p_{\pi(1)}, \dots, p_{\pi(n)})$), the stream cipher you get is completely broken.  When $F$ is a permutation with an easily computed inverse, as it is here, a known plaintext anywhere among the messages is enough to decrypt all other messages, even prior ones.

For the same reason, $\operatorname{MD5}(k) \mathbin\| \operatorname{MD5}^2(k) \mathbin\| \cdots$ makes for a terrible stream cipher even though $\operatorname{MD5}(k \mathbin\| 1) \mathbin\| \operatorname{MD5}(k \mathbin\| 2) \mathbin\| \cdots$ is basically fine.


Decryption with password, compiled code and ciphertext known There's a program I'm using that downloads encrypted XML files to a user's computer that can be decrypted within the program with a provided password. I have the correct password for one of these encrypted XML files.

Basically my question is: Is there any way to decrypt an encrypted file without using that file's specific program if I have the password to decrypt it?

(I know it's some form of base64 encryption and that the program itself can be decompiled to an extent with a VB decompiler, but that's it for any extra, quite possibly useless info)

Yes, you can, but you may have to reverse-engineer the algorithm. Crypt-analists usually consider the algorithm known. But this is more because the algorithm acts as a single secret if it isn't known.

If the algorithm is really intricate then it may be hard to reverse it from compiled code. If it is however managed, unobfuscated code then it may be pretty simple to decompile. It's quite easy to see that you have all the information present, but it may still be hard to extract it.

I once attacked an amateurish encryption scheme in Java Script (web-page encryption) and as a result I didn't just get the plaintext but also a table with names and passwords - and in that case I didn't even have a password.

So it depends on the ciphertext and application on how easy it is to decrypt. As the algorithm is deterministic and since you have all the inputs: password, code and ciphertext it's clear that it can be done.


How does BLAKE2 ensure that hash(A) != hash(B) when B = A||0 and both A & B have the same number of blocks? Suppose I have two arrays :

A = a single byte, being zero.
B = two bytes, both being zero.

B = A||0 (i.e. B starts with A, and differs only by appending a zero byte)

BLAKE2(A) != BLAKE2(B)

Yet, according to the scant documentation I can find, BLAKE2 pads with zero bytes.

Given that both an array with just one byte, and an array with two bytes, are well within the size of a single block, theoretically their full-block-length zero-padded equivalents are identical.

So, if it isn't padding the inputs with a length indicator, and if the finalization flag mentioned in the scant documentation is either all binary 1s or else all binary 0s as the scant documentation clearly states (thus providing no indication of which bytes in the final input block are padding), how is BLAKE2 able to make a different hash for these two inputs?

Note: It does make different hashes from these two inputs, and that's a very good thing, and I'm in the process of writing some software that relies on this property of BLAKE2, but I would feel more confident if I understood why/how this is happening.  Thanks!

P.S. I tried tagging this BLAKE2 but the system wouldn't let me - apparently the tag doesn't exist yet.

You are right that the padded message by itself is ambiguous.

But the Blake2 compression function does not just take the message block and the chaining value as input. It also takes a finalization flag (to mark the last block and prevent length extensions) and the message size in bytes.

Passing the size to the non final blocks mainly serves to prevent certain multi target attacks. For these blocks the size is always a multiple of the block size. For the final block it's different: Here the size parameter is the total size of the message in bytes and it disambiguates messages which map to the same zero padded message and only differ in size. The flag ensures that compressing a message which ends at the end of the current block, and a message which continues (and thus has the same size argument) have different inputs.

Beyond the specification, which Nova already quoted, it might also be interesting to read:

The Skein specification, which uses a similar approach where the tweak contains the length of the message and which inspired the Blake2 padding.
My blog post Alternative Blake Padding where I propose a simplified padding, which with some minor tweaks turned into the Blake2 padding.


Non-trivial examples of a system being a zero-knowledge proof system but not zero-knowledge proof of knowledge It got me confused these days when I encountered the notions of zero-knowledge proofs (ZKP) and zero-knowledge proofs of knowledge (ZKPoK). As far as I know, the two terms are not the same, but all the ZKP systems I know so far also happen to be ZKPoK systems.

Can anyone tell me if there is any non-trivial example of a system being a zero-knowledge proof system but not zero-knowledge proof of knowledge, and vice versa?

At first, every ZKPoK protocol is ZKP protocol. This is obvious: if you proved that you know a witness, therefore a witness exists, therefore the statement belongs to the language.

The interesting question is whether a protocol exists which is ZKP but not ZKPoK.
It holds for trivial languages, but you're justly not satisfied with this.
My idea in a discrete log settings, similar to Schnorr protocol, is the following:
 take a protocol proving the equality of the discrete logarithms of $y_1$, $y_2$ to
bases $g, h \in G$,
i.e. for a language $\{ g||h||y_1||y_2 : \exists w, y_1 = g^w \land y_2 = h^w  \}$,
where $w\in Z_q$ is a witness. $G$ is cyclic group here.

The classical Schnorr-like protocol for that is the following:

Prover chooses $k\in Z_q$, calculates $C_1=g^k, C_2=h^k$ and sends $C_2, C_2$ to Verifier.
Verifier chooses $e\in Z_k$ and sends it to Prover.
Prover calculates $r = k + ew$ and sends it to Verifier.
Verifier checks: $C_1 y_1^e = g^r$ and $C_2 y_2^e = h^r$.

You can easily build knowledge extractor E which will extract $w$ (just the same as in Schnorr protocol), so this is clearly ZKPoK protocol for a language $L_1 = \{ g||h||y_1||y_2 : \exists w, y_1 = g^w \land y_2 = h^w  \}$.

But, notice that this is also a ZKP for a language $L_2 = \{ g||h||y_1||y_2 : \exists v, h = g^v \land y_2 = y_1^v \}$.
The language is actually the same ($L_1 = L_2 = L$), but it's defined through another witnesses.
And knowing a witness $w$ doesn't help you to find witness $v$.
So, this protocol is not a ZKPoK for $L_2$, while it's ZKP for it.

The trick we did here is in the following. We have a language which could be
independently defined by two types of witnesses. You can use say the witness of the first type to provide a proof, but you could not know the witness of the second type. You can say that it's just a trick and this protocol is still a ZKPoK, just for another type of witness. You're right, but this trick is inevitable: if a prover can provide a proof, and the language is not trivial,
the prover necessarily knows something special (otherwise, anybody can conduct such proofs for himself, and language becomes trivial! ).
And this special thing is a witness! But, this could be another type of witness,
not that one which you initially supposed. This is a core idea of the trick.

WARNING: this is an improvisation and I'm not 100% sure in this, so please wait for endorsement of other people.


OpenSSL FIPS integrity check As far as I know, FIPS requires a set of self tests (POST) to verify the cryptographic algorithms permitted and the integrity of the module.
These tests are performed at run-time, so OpenSSL does a HMAC-SHA1 of the code loaded in memory and compares its output with the HMAC-SHA1 computed at build time.
I think that an attacker could modify the source code compile it and then both hashes would match too. Also, HMAC secret key is disclosed as OpenSSL is open-source software.
Where is the security here? Keeping the HMAC key secret? Which is the most-common approach to fulfill this FIPS requirement?

Indeed FIPS 140-2 requires a module to validate itself, and this has no security benefit.
In order for a code integrity check to have a security benefit, both the code that performs the verification and the data that it uses (hash value for a hash, MAC value and secret key for a MAC, public key for a signature) need to be integrity-protected (and with a MAC, the key also needs to be confidentiality-protected). Since the verification code is part of the module, the code integrity verification does not provide any security benefit. It guarantees the module's integrity under the assumption that the module's integrity is not breached.
As far as I know, this started as a requirement for hardware modules, which had to perform some kind of self-test that would typically fail if the physical integrity of the module was compromised. Basically, a physical tamper detection mechanism: make sure that the keys are unusable if the box has been opened. This doesn't translate to software well, but the requirement has been kept and has evolved to require cryptography, partly due to inertia and partly due to the illusory wish that something should be done.
An integrity (or authenticity) check is useful when the module that performs the check is better-protected than the module that is checked. For example, some devices boot from ROM (as in, physical ROM, which can only be modified by completely taking the device apart), which then transfers control to updatable, physically exposed storage (such as a hard disk or flash memory). If the ROM contains signature verification code and a root public key, and the ROM code verifies the integrity or authenticity of the external storage before transferring control to it, there is a real security benefit: it can ensure that the device will only run trusted code. Depending on who you ask, this is called secure boot or trusted boot. There is often a chain of secure boot, from ROM to firmware bootloader to operating system bootloader to operating system kernel to user land utilities. This chain relies on physical integrity protection for the first element, and cryptography to extend trust to subsequent elements.
Some security standards that are applicable to a specific kind of device (for example a PC, a smartphone, a smartcard, etc.) have specific requirements on secure boot. But FIPS 140 is too generic for that.
So treat the FIPS 140 integrity check as a compliance requirement, not as a security requirement. It's one of the many hoops through which you need to jump. Fiddle with your operating system's low-level interfaces to figure out how to read code in memory before any dynamic linking or randomization takes place. Calculate the expected MAC value and store it somewhere that isn't part of the verification (because it's infeasible to find $v$ such that $\mathsf{MAC}(m) = v$ and $v$ is a substring of $m$). Arrange for your code's initialization sequence to verify the MAC of the code against the reference value stored next to it. It's part of the cost of getting a FIPS stamp.


Decrypting 3-DES with DES I have a ciphertext, that is encrypted using 3-DES.
I wondered, why is it possible to decrypt it using 1-DES.
1-DES key is shorter than 3-DES that is used. How does it work like that?

Triple DES (Wikipedia) is simply DES used three times, usually ciphertext = E(k3,D(k2,E(k1,plaintext))), although I have seen other arrangements such as E(k1,E(k2,E(K3,plaintext).  So just split the 3-DES key into three (sometimes two) parts k1, k2, and k3, and run 1-DES three times, using the appropriate key each time.

So, for example, if my 3-DES key is aaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbcccccccccccccccc (hex), then the 1-DES keys would typically be aaaaaaaaaaaaaaaa, bbbbbbbbbbbbbbbb, and cccccccccccccccc, with the system documentation letting us know which one is k1, k2, and k3.  So assuming we encrypted using ciphertext = E(k3,D(k2,E(k1,plaintext))), then we can decrypt using 1-DES as follows:

temp1 = D(k3,ciphertext)
temp2 = E(k2,temp1)
plaintext = D(k1,temp2)

And of course if we are using something like Cipher Block Chaining, the whole sequence above would be considered one block cipher decryption.

Edit:
1. If only two keys are used (the ABA mentioned in the comments), the general approach is the same, except instead of having a separate k3, we just set k3=k1 and do the same as before.

Just to be clear, E(k,p) is enciphering the plaintext p using the key k, and D(k,c) is decrypting the ciphertext c using the key k.  For this example, we are using plain DES for both E() and D().


Breaking RSA with Factor in Range of $\sqrt{N}$ Suppose on of the RSA prime factors $p$ is the range of $\sqrt{N}$, in particular it holds that $|p-\sqrt{N}|<\sqrt[4]{N}$
I want to show that RSA can be broken in time poly(log N)
Given hint: $N = pq = (\frac{p+q}2)^2 - (\frac{p-q}2)^2 $ , also $\frac{p+q}2 \approx \sqrt{N}$
$\textbf{This is my approach:}$
First of all, we can calculate $\sqrt{N}$
From $|p-\sqrt{N}|<\sqrt[4]{N}$ we know that $p$ can only be $2 \sqrt[4]{N}$ distinct values, namely anything in$ \{\sqrt{N}- \sqrt[4]{N}, ...,\sqrt{N} + \sqrt[4]{N} \}$
Of course $\sqrt{N}$ is usually not a whole number, but we can round up
So now we can test for every element $p$ in this set, if $p | N$ , in which case we could easily calculate the other factor
If i am not mistaken, this reduced bruteforce would cost $\mathcal{O} ( \sqrt{N} )$ , which does not seem to match with what we want to show, e.g. $\mathcal{O} ( \sqrt{N} )$ $\not=$ poly(log N)

Although this might not be the solution you're looking for, the Coppersmith theorem offers a simple answer to this.
The (general) Coppersmith theorem states: let $f(x)$ be a monic univariate polynomial of degree $d$ with coefficients modulo a positive integer $n$. One can find all integers $x$ such that $|x| \le n^{\beta^2/d}$ and $\gcd(f(x), n) \ge n^{\beta}$ (or $f(x) = 0 \bmod b$, $b$ an unknown divisor of $n$ of size $\ge n^{\beta}$) in time polynomial in $\log n$ and $d$.
Now here we have $|p - \sqrt{n}| < n^{1/4}$. Setting $f(x) = x - \lfloor \sqrt{n} \rfloor$, this means that there is an $x_0$  bounded in absolute value by $n^{\left(1/2\right)^2} = n^{1/4}$ such that $\gcd(x_0 - \lfloor \sqrt{n} \rfloor, n) \ge n^{1/2}$ (that is, a factor of $n$), and such an $x_0$ can be found in polynomial time in $\log n$.


Why "pairings on elliptic curve" are used? I'm just curious why do we use pairings on elliptic curve cryptography.
There is a lot of information about how to use it, but I cannot find information about why to use it.
Can somebody help?

Although the question is a bit broad, I think it's an interesting one.

Giving a bit of context helps with the explanations. In the 80's, many cryptographic primitives have been design, based on group structures (usually relying on variants of the discrete logarithm assumption over this group). The rationale behind the initial introduction of elliptic curves in cryptography was the following: over a group with no additional structure, solving discrete log is hard (we say that discrete log is "hard in the generic group model"). Elliptic curves are groups, yet they seemed to have little, if any, additional structure that one could exploit to solve the discrete log problem (and related problems).

In the 90's, an apparent weakness was discovered in many types of elliptic curves: in some curves, people observed that there was in fact more structure than expected, as there was an operation that could move (in polynomial time) the discrete log problem from the curve, to a target space (as you can guess, this operation is the pairing operation). Therefore, when the target space was a space with a lot of structure (such as a field), this allowed to reduce solving a hard problem (dlog over a curve) to a considerably easier one (dlog over fields). A variety of attacks were developed, based on the computation of these pairings.

Then, in the 2000's, Boneh and Franklin on one side, and Joux on the other, came up with the idea that this apparent weakness could become a feature: intuitively, a pairing allows to "multiply" the exponents of two group elements, while the usual group structure only allows to add an substract exponents. To do so, one had to use a curve where the pairing was not a strong weakness (i.e., a pairing moving the discrete log to a group sufficiently large to make the computation of dlog still infeasible in the target group). Then, they came up respectively with the following applications:

Identity based encryption, which was a long standing open problem. One can obtain very efficient instantiations using pairings. It has recently been shown that standard groups (without pairings) suffice for identity-based encryption; however, pairing-based solutions remain considerably more efficient.
Tripartite non-interactive key exchange. Here, the idea is simple: the standard two-party DH key exchange works by exchanging two group elements, $g^a$ and $g^b$, and letting the two players locally compute $g^{ab}$. If one has a pairing, we can add a third player without further interaction: the players exchange $(g^a,g^b,g^c)$, and can locally compute $K = e(g,g)^{abc}$, where $e$ is the pairing operation.

This last example is perhaps the most useful one for you, because it illustrate on (arguably) the simplest possible scenario the reason why the additional structure given by a pairing allows for new applications. Following the above applications, many more have been discovered, which can be obtained from pairing but not (or not efficiently) without them. This includes:

Non-interactive zero-knowledge proofs
Verifiable pseudorandom functions
Short Signatures

... and many more. In addition to the "multiplication in the exponent" allowed by pairings, another feature which is at the core of many applications is the fact that they allow to build a gap group, i.e., a group in which the decision problem (DDH) is easy, but the search problem (CDH) remains hard. Such gap groups have many applications (e.g. identity-based signatures, undeniable signatures...).


How to encrypt email address using FPE? Could anyone guide me on how to implement FPE (Format Preserving Encryption) for Email address masking?

For example: if my ID is Poornima1@gmail.com then it should be encrypted something like   asdfghjk4@zxcv.qwe

Preserving the format and datatype.

Preserving the format of an email address (see RFC 5322 § 3.4.1) when encrypting it is quite easy. All you have to do is encode the ciphertext in base64 and prepend it to something like @a.invalid if you want to make sure that it cannot be resolved even by accident. This results in emails like this:

3IPRr5/0rrgWuzZBFoRDpl8PYE76xuHxYdRJzfu2mKw=@a.invalid

That is a technically valid email address for a non-existent and non-resolvable domain.

Note that this does not preserve the length of the plaintext. If you wish to do that as well, you could use a dedicated FPE mode of operation as per NIST SP800-38G. Unfortunately, that would likely result in an email address that is invalid due to the fact that the format specified in RFC 5322 is too complex for it.

While not strictly FPE, you may be able to get what you want by using a Vigenère cipher with the key generated by a secure stream cipher, such as ChaCha20. The set of characters in the Vigenère key must be valid for that atom of the address. You must of course skip the @. This will preserve the length. Note however that it requires a more complicated construction as fgrieu pointed out, notably due to the fact that the IV would need to be stored separately or a unique key must be used for each email.


What is the "shared secret" used for in IPSec VPN? Can somebody explain what the "shared secret" and "password" do when opening/creating a VPN tunnel?

In this specific case I setup a VPN to my Fritz!Box and I had to provide a shared secret (which was pregenerated and very long) and a password.

I'd like to understand how each of these two credentials is used in terms of encryption.

Most likely, this 'shared secret' was actually an IKE "preshared key"; it is used to authenticate the two sides (and, for IKEv1, is stirred into the keys).  It actually isn't used as a key (and hence someone learning that key cannot use it to listen in, unless they perform an active Man-in-the-Middle attack).

I suspect the password is the authentication credential to the remote operating system; it doesn't get involved with the encryption at all.

Now, if you're asking "how is this IKE preshared key" used, well, I'll try to outline it for you; the bottom line is that someone with the preshared key cannot listen in (or be able to decrypt previously captured sessions).  They would be able to perform a man-in-the-middle attack; that's because the preshared-key works as authentication data; someone with it can impersonate.

To make this even more complex, there are two different version of IKE (IKEv1 and IKEv2), and they use the preshared key somewhat differently.  Since I don't know which one you're using, I'll list how they both work separately.

For both versions of IKE, the negotiation happens in two phases; the differences (that you care about) occur in the first phase (which generates the IKE SAs; that is an encrypted control channel that the two sides use to coordinate things).

Here's how the first phase of IKEv1 works (assuming that you're using preshared key authentication, and omitting the parts not relevant to the key generation):

The two sides exchange nonces
The two sides perform a Diffie-Hellman exchange
The two sides each take the nonces, the Diffie-Hellman shared secret and the preshared key), and generate a set of IKE keys
They exchange IKE encrypted messages (to verify that both came up with the same IKE keys; if they used different IKE keys, they won't).

For IKEv2, this first phase looks like:

The two sides exchange nonces
The two sides perform a Diffie-Hellman exchange
The two sides each take the nonces, the Diffie-Hellman shared secret, and generate a set of IKE keys
Via IKE encrypted messages, they exchange authentication data.  For preshared key authentication, this is a complex (noninvertable) function of the preshared key, and the keying data.  The idea is that if there was a man-in-the-middle who didn't know the preshared key, the keying data between the actual two sides woudl differ, and the man-in-the-middle wouldn't be able to adjust this authentication tag to account for that).

Now, for both IKEv1 and IKEv2, they perform the second phase; they generate the IPSec SAs, which are the keys (and other data) used to actually encrypt the traffic.  To do this, they exchange SPI values and nonces, possibly do another Diffie-Hellman exchange, and they create the IPSec keys from some IKE keying data, the SPI values (and the Diffie-Hellman shared secret, if a Diffie-Hellman was used.

Now that the two sides have the IPSec SAs established, they can now send and receive encrypted traffic.

And, because a Diffie-Hellman operation was involved, someone listening into the traffic is unable to decrypt anything; even if they know what the "preshared key" was.

From the fritzbox website on "VPN for experts":

  IKE negotiation takes place in two phases. The first phase serves to
  establish an encrypted connection; in the second phase the actual VPN
  tunnel is established - already encrypted. Special authentication
  procedures ensure that no password or key is transmitted in plain text
  during the negotiation. A hacker tracing the establishment of the VPN
  connection using IPSec cannot procure any security-sensitive
  information.


Do the limitations of PRNGs apply to CSPRNGs when shuffling a list? Suppose, as an example, we want to use the Fisher-Yates algorithm along with a pseudorandom number generator to shuffle a deck of cards. We know that there are limitations with respect to the internal state of the PRNG and its ability to reach the distinct permutations of the deck. If, for example, the PRNG can only be seeded with $2^{32}$ bits, then it cannot possibly produce all the $52!$ distinct permutations. In addition, even if we could meet the 226 bits needed for a 52-card deck, the distribution may not be uniform.

Now, suppose we switch and swap the PRNG with a CSPRNG. How do these limitations apply? In practice, they're seeded and reseeded frequently, depending on implementation, but this is generally done behind the scenes. Since CSPRNGs are PRNGs, my initial thoughts would lead me to believe that they will suffer the same limitations. Yet, if we used a PRNG with the same seed, but continuously draw numbers from it, we could reach additional permutations.

Over yonder in response to this question, one answer suggests that a cryptographically strong source of unbiased numbers will reach the desired permutations. Would you agree?

Finally, I used a deck of cards as an example. I'm curious about list sizes with respect to this question. I know that with PRNGs, the seed bits must increase to accommodate larger lists.

If, for example, the PRNG can only be seeded with $2^{32}$ bits, then it cannot possibly produce all the $52!$ distinct permutations. In addition, even if we could meet the 226 bits needed for a 52-card deck, the distribution may not be uniform.

This is true, but a good PRNG (even non-cryptographic) will give you a random sample from a uniform distribution. That means that until you get close to the square root of the seed size, your sampling will still look random. With a 32-bit seed you can easily go over that limit, but with larger seeds you will not.

  Yet, if we used a PRNG with the same seed, but continuously draw numbers from it, we could reach additional permutations.

Yes, but even then the state size will limit which outputs are possible.

  Now, suppose we switch and swap the PRNG with a CSPRNG. How do these limitations apply? In practice, they're seeded and reseeded frequently, depending on implementation, but this is generally done behind the scenes.

If you take a sequence from a CSPRNG that is longer than the state size, without reseeding in between, it cannot produce every possible output value. However, it is guaranteed to be indistinguishable from random.

For example, suppose you have a CSPRNG based on AES CTR. A single AES key will produce $2^{128}$ different 128-bit outputs, but as long as you see (significantly) fewer than $2^{64}$ you do not notice this. As long as the RNG is reseeded often enough and you do not use it enough that both keys and inputs would repeat (impossible in practice), you are fine.

So yes, there are $52!$ different ways to shuffle cards, but since there is no chance that you will look at them all, it is sufficient to generate deck orders from a set of e.g. $2^{128}$ that are themselves a random selection of all possible ones.


What is the significance of IV in stream ciphers like Trivium? In Trivium cipher, an 80-bit key and 80-bit IV (initialization vector) are used initially to set up the initial state. I would like to know,

Role of IV in stream cipher?
Can we make IV a secret parameter? and
How IV values are chosen/updated in Trivium?

Role of IV in stream cipher?

Like in block ciphers; it helps to achieve randomized encryption. Also, using different IV under the same key prevents the crib-dragging attack like in all stream ciphers. This enables us to reuse a key without causing the crib-dragging attack ( that works on two or many-times pad) by using different IVs.

If the IV repeats under the same key, the keystream will be repeated and an attacker will x-or the two or more encrypted messages to the x-or of the messages

$$C_1 = M_1 \oplus keystream$$
$$C_2 = M_2 \oplus keystream$$ then

$$M_1 \oplus M_2 = C_1 \oplus C_2$$ and a passive attacker has the access $C_1 \oplus C_2$ since they are listening the channel. Now, they need to execute crib-dragging and that can be automated.

A Natural Language Approach to Automated Cryptanalysis
of Two-time Pads

  Our method, which is related to HMMs, recovers the most probable plaintext of this
  type by using a statistical language model and a dynamic
  programming algorithm. It produces up to 99% accuracy on
  realistic data and can process ciphertexts at 200ms per byte
  on a $2,000 PC.

It should also be noted that the IVs of such (synchronous) stream ciphers play an important role as a means of resynchronization, e.g. on a per-message basis.

  Can we make IV a secret parameter? and

IV's are public values and never intended to be secured, otherwise, we can call them as the part of the key. Remember the Kerckhoffs's principles; only the key is the secret.

  How IV values are chosen/updated in Trivium?

The Trivium specifications doesn't mention about generating the IV values. We, however, can use the common knowledge about it.

Since the repeat of the IV under the same key can cause catastrophic failures as in all stream cipher that confidentiality is failed. One must guarantee that is is not repeating.

Random IV: Since Trivium uses 80-bit IV, after $2^{40}$ random IV generation it is expected that the IV will be repeating with 50% probability due to the birthday attack. Actually, one must stop way earlier to use the current encryption key and generate/exchange a new one.
Counter/LFSR based IV: Counter/LFSR bases solutions are fine except that on the system failures where the last value of counter/LFSR may not be stored correctly that cause repeats. To mitigate this either generate/exchange a new key or see the next solution.
Random combined with counter/LFSR: This time the randomized part can help to eliminate the system failure even the last values of counter/LFSR are repeating after the system recovery.

$$\text{IV} = \text{[40-bit random]} \mathbin\| \text{[40-bit  counter/LFSR value]}$$

Some Nice crib-dragging answers for more details;

Taking advantage of one-time pad key reuse?
How does one attack a two-time pad (i.e. one-time pad with key reuse)?
Little problem with Vernam Cipher


How can I convert a mathematical formula into a logical formula? I'm using cryptominisat2.9.6 to solve equation set (including more than 160 equations). There are 160 variables in total, which are as follows: $x_0,x_1,x_2,...,x_{78},x_{79},y_0,y_1,y_2,..,y_{78},y_{79}$.

For example, the first equation is as follows:
$$x_1+x_2+x_4+x_{10}+x_{31}+x_{43}+x_{56}+y_3 \times y_{25} \times y_{46}+y_3 \times y_{46} \times y_{64}+y_3 \times y_{46} \times x_{63}+y_{25} \times y_{46} \times x_{63}+y_{46} \times y_{64} \times x_{63}+y_3 \times y_{64}+y_{46} \times y_{64}+y_{64}*x_{63}+y_{25}+x_{63}=1$$
Every  equation is different.

In every equation, every variable is 0 or 1.  So I want to put all the equations into

cryptominisat to solve the 160 variables.  But cryptominisat requires a standard input format, either CNF or XOR format.  I have no idea how to change the equation into the format.

Considering you are working in $GF(2)$, every multiplication is equivalent to a AND and addition to a XOR.

  $GF(2)$ also known as $<\mathbb{Z}_2,+,\times>$ is the Galois Field (GF) of two elements: $0$ and $1$.

  Because $GF(2)$ is a field,

  addition has an identity element ($0$) and an inverse for every element;
  multiplication has an identity element ($1$) and an inverse for every element but $0$;
  addition and multiplication are commutative and associative;
  multiplication is distributive over addition.

  One of the most interesting property of $GF(2)$ is its link with the logical functions over booleans. An analogy can therefore be done between the two:

  The field addition ($+$) correspond to the logical XOR operation ($\oplus$), also $\forall x \in GF(2), x + x = 0$.
  The field multiplication ($\times$) correspond to the logical AND operation ($\land$).

  Remarks: $0 + 1 = 1$ ($0 \oplus 1 = 1$) and $1 + 1 = 0$ ($1 \oplus 1 = 0$), therefore $x \mapsto x + 1$ is equivalent to the logical NOT. With this in mind, every booleans operations have an equivalent in $GF(2)$.


How does stream cipher works? I will be grateful if someone can explain how stream cipher works using Pseudorandom generator(PRG).

Steam ciphers work by encrypting the counter / nonce with the master key (generated from a cryptographically secure psuedo-random number generator).

For example with AES in CTR mode, you would run the usual AES Encryption algorithm, but instead of inputting a message you input the counter/ nonce.

This creates a stream. A portion of the stream equal to the length of the message you want to encrypt is XORed with the message, and sent to the recipient.

As for the psuedo-random generator, a stream cipher can be used as a PRG, but there isn't a PRG in the stream cipher itself, as both parties have to be able to construct the key and encrypt / decrypt the message.


Does blinding work against side channel on RSA? In the so called "blinding" technique for RSA, prior to decryption, the ciphertext is multiplied by random $r$ raised to the power of $e$; e.g., $C$ is replaced with $C\cdot r^e$; and then after decryption, the result $(C\cdot r^e)^d\equiv C^d\cdot r\pmod n$ is divided by the random $r\pmod n$.

Is that efficient against timing or power attack? I saw that technique in some articles, nevertheless I though that the power / timing attacks are aiming at discovering the bits of the exponent $d$, and if so, the value of the cipher text, whether its $C$ or $C\cdot r^e$ does not really matter, does it?

Blinding protects against some side-channel attacks in RSA: those that target variations in the timing or other side-channel information as a known function of $C$ (or $C^d\bmod n$ should that end up to be available).

As noted in the question, blinding is pointless against the most basic (Simple) Power Analysis attack, which determines the bits of the private exponent $d$ (or the CRT exponents $d_p$ or/and $d_q$) by finding from power traces if binary exponentiation is performing a multiply or not. Protection against such attacks must be by other ways (e.g. using a Montgomery ladder, a randomized exponentiation algorithm, or/and making square fully indistinguishable from multiply from a hardware standpoint, including when measuring execution time between these operations).
However, blinding is useful as a countermeasure against some timing attacks, which operate differently. In essence, they correlate variations of execution time (for the same unknown $d$ ) with the particular value of $C$ being deciphered or the deciphered result. The original idea is in Paul C. Kocher's Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems, in proceedings of Crypto 1996. With blinding, the attacker is deprived of direct information about what the exponentiation has as input or output, which both are masked with random secret $r$. Some implementations do not even care to make the computation of $r^e\bmod n$,  $C\cdot r^e\bmod n$, or $r^{-1}\bmod n$ constant-time, or/and make $r$ much smaller than $C$.
Even when exponentiation is inherently constant-time (as many carefully written or/and hardware implementations are), blinding can also be useful against other side-channel attacks, in particular, those targeting variations in power consumption / electromagnetic emission according to known $C$ .

Details per comment
One of the reason that the execution time of the computation of $C^d\bmod n$ depends on $C$ can be that modular reduction modulo $n$ sometime needs to fix a bad estimation of quotient. For example, the HAC's algorithm 14.28 for classical modular multiplication uses algorithm 14.20 for multiple-precision division, which step 3.4 reads

if $x<0$ then set $x\gets x+y\,b^{i−t−1}$ and $q_{i−t−1}\gets q_{i−t−1}-1$

with the condition $x<0$ rare (enough that it won't occur for most parameters to algorithm 14.28, but still frequent enough to be observable for random inputs), and the conditional computation lasting a significant time ($x$ and $y$ are vectors of machine words).
In the following, we'll assume that modular multiplication takes sizably varying time according to parameters; that the time it takes is predictable as a function of the two inputs to be multiplied; that the adversary measures the execution time of the computation of $C^d\bmod n$ for many values of random $C$ (no power analysis involved); and that this computation is per left-to-right binary exponentiation, as:

$S\gets C$
for each bit of $d$ from high order to low, except the highest one

$S\gets S^2\bmod n$
if the current bit of $d$ is set

$S\gets C\cdot S\bmod n$

The attack tests if overall execution time conclusively correlates positively with the (computable!) execution time of $S\gets C\cdot S\bmod n$ with $S$ initially $C^2\bmod n$. That computation occurs if the bottom step of the algorithm is executed on the first iteration of the for a loop. If such correlation is found, the attack concludes that the second-highest order bit of $d$ is set; otherwise, clear. While there are other sources of timing variation than those in the particular $S\gets C\cdot S\bmod n$ targeted, and they are cumulatively much larger, correlation of enough measurements cancels out these other sources because they occur practically independently of the tiny variation targeted.
The attack can then proceed and test if overall execution time conclusively correlates positively with the execution time of $S\gets C\cdot S\bmod n$ with $S$ initially $C^4\bmod n$ (if the previous detection found the bit clear), or $C^6\bmod n$ (otherwise). This will reveal the third-highest order bit of $d$.
All bits of $d$ can be found this way (though only some fraction is enough to mount a factorization). The attack can be improved, in particular, leverage timing variations in the next $S\gets S^2\bmod n$ step; guess several bits of $d$ simultaneously to get an even stronger correlation, and recover from an accidental wrong decision (no later correlation is observed). There's a trade-off between the number of available measurements, and the post-processing cleverness/effort necessary to find $d$.
Reference for essentially that attack: Jean-François Dhem, François Koeune, Philippe-Alexandre Leroux, Patrick Mestré, Jean-Jacques Quisquater and Jean-Louis Willems; A Practical Implementation of the Timing Attack, in proceedings of CARDIS 1998.
Blinding prevents this archetypal class of timing attacks very well. It is also effective against some power-analysis variants, which test if power traces varying according to $C$ best correlate with this or that hypothesis on early-tested bits of $d$.

[Note following other comment: the attack does not directly target the timing variation caused by the guessed bit of $d$ being set or not (it can't because that bit is fixed, thus there is no such variation). Rather, the attack targets the timing variation caused by $C$. The attack determines if the overall computation time is correlated with variations that would occur, or not, depending on if the guessed bit of $d$ is set or not.]


AES, is this method to say "The password you entered is wrong" secure? (TL;DR at the end)

Let's say the plaintext hello is encrypted with AES (CFB mode). I noticed that decryption works no matter the given password! Of course if the password is wrong, the output will be garbage, but no error will be thrown (example in Python):

import Crypto, Crypto.Random, Crypto.Hash, Crypto.Cipher.AES
p = b'hello'
iv = Crypto.Random.new().read(Crypto.Cipher.AES.block_size)
cipher = Crypto.Cipher.AES.new(Crypto.Hash.SHA256.new(b'password1').digest(),
                          Crypto.Cipher.AES.MODE_CFB, iv).encrypt(p)
print(Crypto.Cipher.AES.new(Crypto.Hash.SHA256.new(b'wrongpassword').digest(),
                          Crypto.Cipher.AES.MODE_CFB, iv).decrypt(cipher))
# b'\xfdQ\xd7\xa3\x1b'

I read that HMAC etc. can be used to ensure integrity, or AES in GCM mode.

But to keep things simple, I wanted to know if this method is secure or not:

p = b'hello'
startingtag = b'504B0304'   # fixed constant, like "MZ" for DOS .exe files, or "%PDF-1.5" for PDF files
iv = Crypto.Random.new().read(Crypto.Cipher.AES.block_size)
cipher = Crypto.Cipher.AES.new(Crypto.Hash.SHA256.new(b'password1').digest(),
                          Crypto.Cipher.AES.MODE_CFB, iv).encrypt(startingtag + p)
s = Crypto.Cipher.AES.new(Crypto.Hash.SHA256.new(b'wrongpassword1').digest(),
                          Crypto.Cipher.AES.MODE_CFB, iv).decrypt(cipher)
if s[:len(startingtag)] == startingtag:
    print('ok good password, here is the plaintext:')
    print(s[len(startingtag):])
else:
    print('wrong password entered.')

What does it do? A starting tag is encrypted along the plaintext. Then we check if the first bytes of the decrypted text matches this starting tag.

This is basically the method explained here. I had the same questionning than a comment there:

  if the first block of the plaintext is a known value, can't an attacker easily get the key from looking at the first block of the ciphertext?

But on the other hand this seems true as well:

  Having a known header isn't a problem, otherwise encrypting something like a Microsoft Word document (that also has a known header) would be insecure.

TL;DR:

Is it secure to encrypt with AES CFB mode a plaintext for which the first bytes are known (e.g. %PDF-1.5 for a PDF document),
or does this give too much information to an attacker? Then does this mean it's a bad to encrypt documents with known headers with AES?

Is it secure to encrypt with AES CFB mode a plaintext for which the first bytes are known (e.g. %PDF-1.5 for a PDF document)

Yes. Known (and even chosen) plaintext is a standard assumption in any moder cipher, including AES-CFB (and CTR, CBC, OFB...). It does not "give too much information to an attacker", and it is not "bad to encrypt documents with known headers with AES".

True, having a known plaintext at start to allow a test of the password makes password search a little simpler. But only a little, and we customarily ignore that little. One reason (stated in the question) is that actual plaintext typically contains recognizable sequences. And when not, it is typically compressible, when the incorrect plaintext obtained for the wrong password is not, which allows automated recognition of having the correct password anyway.

Another problem is that CFB is weak at detecting message alteration. Using a modern, authenticated encryption mode such as AES-GCM would solve that. It turns out this is readily available in PyCryptodome's Crypto.Cipher.

However, there is a different, serious problem with the code !

It has poor security because the Crypto.Hash.SHA256.new(b'password1') part of it builds the AES key from a password using a standard cryptographic hash (SHA-256). That conversion from password to key is fast, and that allows to test passwords at high speed. This makes the system very vulnerable to password crackers (which essentially test plausible passwords at high speed, including short ones, and those from or inspired from a dictionary of common passwords/words).

  I use a random Initialization Vector, so doesn't this help (against the above problem)?

No, because that does not appreciably slow down testing a password.

That issue has plagued password-based encryption since the origin of that, and progress in computing (faster CPUs, GPUs, FPGAs, ASICs..) directly worsen it, to the point that nowadays, very practically, if users can memorize a password, and a standard hash is used to turn it into a key, then the system is very weak (much to the pleasure of Three Letters Agencies and more casual/greedy attackers, which routinely use password crackers, and succeed).

In the 1990 we started to get iterated password-to-key derivation functions, like PBKDF2 of RFC 2898, which essentially slow down conversion from password to key by requiring many hashes. Initially "many" was at least a thousand, but nowadays we'd need hundred thousands just to keep with the progress of technology. Until about 2015, that was the industrial state of the art (what your mobile phone or computer used).

We are slowly moving to memory-intensive (or memory-hard) password-to-key functions. The pioneer was bcrypt (which almost accidentally required sizable memory), then scrypt (theorizing the use of large memory and multiple CPUs when available). The Password Hashing Competition gave us Argon2 (which unfortunately fails to catch AFAIK, perhaps because it's complex and has many options). There is also Balloon (which does not catch either, perhaps because it was not in the PHC).

In any case, it is nowadays inadequate and grossly incompetent to turn a password into an encryption key using anything lesser than an iterated hash with many thousand iterations; and it is highly recommendable to additionally make that process require sizable memory.

  Could you include an example of code with which you would replace AES.new(SHA256.new(b'password1').digest(), AES.MODE_CFB, iv).encrypt(p) to make use of another hash?

Crypto.SE is not for code recommendations; and we need another kind of hash. One variously called entropy-stretching key derivation function, password-based hash, or some mix of that. It must be purposely as slow as possible for the attacker, yet fast enough for the application. Also, it will have a salt input, and it is a good idea to feed that with the IV/nonce, of at least server+user ID (this was missing in an earlier version of this answer).

The good news is that we no longer have to choose between several evils (see earlier version of this answer): PyCryptodome now has entropy-stretching key derivation functions, including scrypt which is memory-hard. This is the obvious choice. Be sure to up the N parameter as much as bearable.

Sample Python code there, illustrating how PyCryptodome's scrypt can turn a password into a key of AES-GCM, with GCM's nounce also scrypt's salt.

Caveat: nothing in this post should be construed as an endorsement of PyCryptodome's security.


Using a block cipher with timestamp instead of counter I have a system where machine A sends updates to machine B. The updates are sent over the internet, where each update is a single UDP datagram. Machine A sends a local timestamp in each update (we can assume that the timestamp increments for each message). Messages can vary in length, but there is a maximum size (consider it <1kb).

I would like to secure this communication. Specifically I require that:

Machine B can verify that an update is from machine A, and no tampering has occurred.
An attacker cannot decrypt the updates.
The implementation on machine A is simple and lightweight.

It's okay for an attacker to drop, reorder and replay the updates. (The timestamp in the update mitigates such attacks.)

I can arrange for both machines to share a symmetric key.

My initial thought is to encrypt each message with a block cipher in ECB mode, where each message fits in a single block. I believe the timestamp in the message mitigates the problems with ECB, performing a similar function to the incrementing counter in CTR mode. Are there problems with substituting a timestamp in place of a counter?

One problem here is that the messages are larger than most cipher block sizes. I could instead use a stream cipher, but I'm not sure of the consequences of doing so. Alternatively, there are apparently constructions to make a block cipher with a larger block size, but I'm not sure how they work either.

A timestamp in the message won't fix the problem with ECB mode. ECB mode uses the same key for each block, so you will leak the fact that blocks are the same within the same message, and if you use the same key static key for every update, between different messages as well.

Consider a higher level library such as libsodium or spiped from tarsnap to avoid worrying about these details.


Applying machine learning algorithms to homomorphic encrypted data I have a basic understanding of encryption and I got back to the topic because of an interesting site that encrypts financial data using  homomorphic encryption (HE) and I would be happy for any input from the community here.

They don't really tell the precise method they use. In the blog they mention the Fan and Vercauteren scheme and on the other hand they mention order-preserving symmetric encryption.

They say that as addition and multiplication in HE is "preserved" one can apply machine learning algorithms (they usually use all operations - not only polynomial ones).

My question: if data is enrypted then the data that was originally on the real line is usually mapped to the algebraic structure of a ring. Thus if we get those elements of the ring, we have to perform the operations that are defined on this ring. Finally we can not (!) apply the usual real number operations that the ML algorithms consist of.

Is this tue for HE? Is it true for order-preserving symmetric encryption?

An example as EDIT as I am not a crypto-pro at all:
say I am given the following data:
$$
(0.2,0.1,0.5,0);
(0.1,0.2,0.3,1); (0.02,0.7,0.33,1)
$$
and several rows thousands of them (and in my application more columns). In this example the first 3 entries are inputs and the 4th one is the target. All I know is that the inputs were decrypted (either HE or order-preserving symmetric) and I see that each column has exactly 1001 unique values (which makes me think that the data is not real numbers but data on some grid or finite ring).
If I interpret the inputs as real numbers and perform the usual ML-algorithms (logistic regression and more complex ones). Is this mathematically sound or am I doing complete nonsense (because the data is not real numbers but rather objects in an algebraic strucutre that does not allow for the usual $+$,$\times\ldots$?

Homomorphic Encryption on Reals
In theory, homomorphic encryption can be done on real numbers. This answer describes two options you have when dealing with real numbers or operations that will result in real numbers. Kristin Lauter is doing some of the cutting edge research in this area. In a recent paper, CryptoNets: Applying Neural Networks to Encrypted Data with High Throughput and Accuracy, the authors (which includes Kristin), state:

  One thing to note is that the encryption scheme does not support floating-point numbers. Instead, we use fixed
  precision real numbers by converting them to integers by proper scaling, although there are also other ways to do this
  (Dowlin et al., 2015).

They go on to say:

  The neural network takes as its input a vector of real numbers and, through a series of additions, multiplications, and other real functions, it computes its outputs, which are also real numbers. However, the homomorphic encryption scheme works over the ring $R_n^t := \mathbb{Z}_t [x] /(x^n + 1)$. This means that some conversion process between real numbers and elements of $R_n^t$ is needed.

So they are not operating on real numbers directly. Instead, they encode (using scaling as mentioned in the other answer I linked to). And then decode after decryption. III.B of the Dowlin paper discusses encoding methods for real numbers. Real numbers are encountered everywhere in data analytics, and so I expect there to be continued research into how best to operate on reals using homomorphic encryption. In other words, it is an active area of research and not something that you can just quickly pull a tool out of your hat and off you go. Some thought and care must be taken in making sure you aren't invalidating the analysis techniques by using some of the encoding methods that are out there.

Order-Preserving Symmetric Encryption
The claim in the blog post is

  Simpler schemes like order-preserving symmetric encryption also allow strong security in certain settings, and are easy to use with out of the box machine learning tools.

The author doesn't appear to go into much more detail than that, which leaves me wondering what they really mean. Order-preserving symmetric encryption is all about encrypting data in such a way that a natural ordering of the plaintexts is preserved. This allows you to, given only ciphertexts, do comparisons. This leads to useful operations. Specifically, the paper the post links to mentions range queries on encrypted numbers. The 2004 SIGMOD paper by Agrawal describes how their OPE scheme can be directly applied to IEEE 754 single precision floating point numbers.

Not being a machine learning expert, I can't tell you how useful only being able to do comparisons, operations like min and max, and range queries would be for machine learning. I guess if your machine learning tools require only range queries and comparisons, OPE could be used with "out of the box machine learning tools", but something tells me that would leave much to be desired in terms of data analysis.


BGV for three multiplication level/depth Can BGV homomorphic encryption scheme support three multiplication level/depth with the help of key switching and modulus switching?

If Yes, how does one set up the parameter to achieve that?

Actually It depends on which library you use. If you use Palisade, you can set numberoftowers (L level) to 3.


Crack RSA with additional information Suppose $N=3953$, Alice encryption key is $e_A = 337$ and bobs is $e_B=23$. Eve happens to know the corresponding decryption keys, $d_A=3385$ and $d_B=2663$. Can I use this information to find the prime factorization of $N$?

Here you have an overkill of information, really. We know that $e_A$ and $d_A$ are related by the fact that $e_A d_A \equiv 1 \pmod{\phi(N)}$, normally, and then this answer gives an algorithm.

But here we have more info, as both $e_A d_A - 1$ and $e_B d_B - 1$ are multiples of $\phi(N) = (p-1)(q-1)$. We need some multiple of their gcd, that is close to $N$ to get $\phi(N)$.
Their gcd is 7656, and half of that is 3828, which is probably $\phi(N) = (p-1)(q-1)$.

Now from this you can solve the quadratic equation $(x-p)(x-q) = 0$, because the left hand side is now known: $x^2 - (p+q)x + pq = x^2 + (N - \phi(N) + 1 )x + N = 0$, and $p$ and $q$ follow from the standard formula.


Is there an advantage to "weak" hashing and stretching over strong hashing? Is there any sort of practical advantage to using a stretching algorithm such as PBKDF2 on say SHA256 over a straight SHA512 hash?

If the purpose of key stretching is to increase the length and thus prevent any shortcuts in cracking short keys, is there still a purpose when it is fairly easy to generate keys of lengths that make them close to impossible to brute force?

The purpose of key stretching is to increase the strength of the resulting output keying material, compared with the input keying material. The input of the keying material is of course generally a password. If the strength of the keying material is already high enough then there is not need to stretch the keys.

Note that the word "length" is in this case a bit of a misnomer. "This is a very secure password" is obviously not a very strong passphrase, even though it probably exceeds the length requirements of many (badly programmed) systems.

PBKDF2 also has a salt component to it which makes it possible to derive keys that also depend on a unique salt, which makes sure that if it is used multiple times with a different salt that it produces different keys. This is an advantage of PBKDF2 against a secure hash.

It seems that you want to use SHA-256 for deriving keys however. For this purpose there are other algorithms that are closely related to PBKDF's: KBKDF's.

A PBKDF is an algorithm where a key is derived from a password, while KBKDF's derive directly from a key that already has enough strength. The strength of the input key is directly transferred to the output keying material (to a certain high maximum, depending on the KBKDF algorithm that is chosen).

As with PBKDF2 it is not required that the randomness in the input keying material is well distributed, so it could for instance be the output of an asymmetric calculation that doesn't provide this distribution.

KBKDF's have some advantages over secure hashes, as they have been especially designed for this functionality:

they can use additional diversification data, e.g. the ASCII encoding of "ENC" and "MAC" to derive multiple keys;
they often have an input parameter for a salt;
they often have a configurable output key length;
they can be implemented in cryptographic hardware where the input / output key are kept inside the hardware, without being exposed to the outside world.

The most modern, standardized KBKDF is HKDF, which itself is based on HMAC, and HMAC in turn is based on - you'd guess it - a (reasonably) secure hash.

You could use PBKDF2 as a poorly designed KBKDF, and similarly you could use a hash yourself to create a poorly designed KBKDF. But I'd just use HKDF. It would seem from the question that you'd need the full HKDF by the way, HKDF-extract and -expand.

If you're faced with a direct choice of using a PBKDF2 with SHA-256 over SHA-512, I would say that it doesn't make too much of a difference, especially if you can set the iteration count to 1. I'd choose PBKDF2 as it was at least designed for this purpose and you can tweak it with a salt and generate as many output bits as required, using a standardized algorithm.

That would however be after indicating that a KBKDF should be used instead.