texts: Are convergently-encrypted ciphertexts safe from collision attacks?

texts:
Convergent encryption uses a message digest of the plaintext as the key to encrypt the plaintext to produce the ciphertext.

This is useful for automatic content sharing because it produces a deterministic ciphertext between unrelated parties who encrypt it without revealing contents to parties who never encrypted it. Weaknesses exist, but it can be a useful thing for automatic content sharing in storage systems.

e.g.

compute SHA256 of plaintext -> KEY1

Use KEY1 to encrypt plaintext using AES256 with CBC -> ciphertext

compute SHA256 of cyphertext -> ID1

When sharing, it would be nice to avoid malicious collisions (e.g. widely distributing the funny graphic in email, identified by ID1, and converting it to something obscene in automatically-shared storage that also happens to have ID1).

The straightforward way is to make sure the hash algorithm is secure. SHA256 is reasonably secure even against collision attacks, which is a greater vulnerability than the preimage attacks.

But let's say you want to store your blocks in a medium that identifies objects by a weaker hash, such as MD5, which is vulnerable to collision attacks. In the above example, this means that ID1 is computed or verified using MD5 instead of SHA256, because it is done by the system when storing the ciphertext. Specifically AWS S3 supports MD5 on objects, specifically not
intended for security but it is there. KEY1 is still computed using SHA256 since that is not part of the object identification/verification process.

The question is, does the process of convergent encryption protect adequately against collision attacks to make them infeasible like preimage attacks of MD5?

It seems like on the one hand, producing a plaintext that after encryption with a known key collides might not be difficult because you can decrypt anything with a symmetric key.

But convergent encryption means that as you mutate your cyphertext looking for a collision changing the plaintext, the key changes as well. Colliding cyphertexts can be produced, but finding cyphertexts that can be mapped back to a plaintext whose MD used as a key produces the cyphertext during encryption seems difficult.

Is it likely that there is a practical way to compute collisions, or did the convergent encryption preprocessing make the weaker MD5 of the storage medium no longer vulnerable to collisions of content that originated as plaintext?

All I have to go on is that it boggles my mind how this collision could be computed, but this sort of instinct can be wrong, so I was wondering whether anyone else had thoughts on whether it might be achieved.


texts: How long would it take to brute force a 32 or 16 bit integer and which type of processor would brute force this in the shortest period of time

texts: I was actually wondering... How long would it take to crack/brute force a 32 bit key/encryption and a 16 bit key/encryptions respectively on a 4GHZ and a 2GHZ PC. I know that a 32 bit integer has 4,294,967,296 combinations while a 16 bit number has exactly 65,536 combinations but I don't know how long It'll take. and what processor would be able to brute force this in the shortest period of time


texts: Prove that certain amount of data was stored

texts:
I'm looking for a way to prove that a certain amount of data was stored, through some easily verifiable piece of information. Similarly to how proof-of-work can prove through a hash that a certain amount of work was done to generate such hash.

I don't need this "proof" to tell me whether that data is currently stored somewhere, I'm just interested in proving that a certain amount of data was stored (anytime in the past) via some sort of hash or other piece of information.

For instance, imagine I have to prove to someone that I was able to store 5 GB. Doesn't matter where, I could use many different computers. One requirement I guess is that the proof should be easy to validate.

Any ideas?


texts: Coppersmith attack on NTRU and non-commutativity

texts: In this paper, Coppersmith and Shamir used lattice reduction to attack NTRU. At the very end of the paper, they note that developing non-commutative variants of NTRU would be wise, in light of their attack, and indeed numerous such variants have been developed (e.g. here, here, and here). Moreover, the authors of such papers often claim that the non-commutativity of their constructions prevents Coppersmith's attack. But where in the original paper does the argument rely on commutativity? I have been unable to pinpoint the step in their argument which requires it.


texts: Generate a random number $r \in \{1,2, \dots , k\}$, where $k$ is not public and is distributedly held

texts:
A set of parties can securely generate a random number $r \in \{1,2,3,\dots, k\}$ when $k$ is publicly known. However, can we generate the random number $r$ if $k$ is not publicly known and is held by the parties using a VSS scheme?

Can you point me to any Multiparty Computation literature which looks at the above question?


texts: Mathematical proof or any reference of "Deterministic random bit generator cannot produce more randomness than the randomness of seed"

texts:
The heading tells everything. Any proof or any kind of reference is welcome regarding this:

Can we get more randomness from a deterministic random bit generator than the entropy that we feed to the generator?


texts: Diffie-Hellman Key Exchange attack on small secret keys

texts:
The question as the title suggests is based on the key exchange with Diffie-Hellman protocol and is something like this:

*"We have intercepted a communication between Alice and Bob: intercepted-communication

We also have read out the code Alice was using to communicate: alice.py

Unfortunately, the flag is no longer in the code. Can you reconstruct it from the communication between Alice and Bob?

Usually, the Diffie-Hellman key exchange can not be broken easily. However, our analysts told us that Bob used a small secret key that can be brute-forced."*

I am having a really hard time understanding this. Any help with this will be helpful.


texts: Time-memory tradeoffs in Shor's algorithm

texts:
Can a quantum computer with insufficient qubits to factor an integer of a given size make any progress in factoring it? For example, what if a quantum computer is only one qubit short of what is necessary to attack a specific integer? Is it capable of making any progress in factoring it, or would it be just as useless as a 2 qubit machine? Assume qubits refer to logical qubits in a general-purpose cryptanalytic quantum computer with sufficient quantum error correction to solve the problem of decoherence.

Given that qubits can be thought of as the memory for quantum computers, I am essentially asking if time-memory tradeoffs are possible with Shor's algorithm when too few qubits are available.


texts: Why are obfuscators generally defined to be probabilistic algorithms, rather than deterministic ones?

texts:
One possible explanation is, randomness is not going to hurt you, so might as well use it. Also, if we are hoping to prove impossibility, it only makes the result stronger.

One other explanation is if the obfuscators are defined to be deterministic, then to satisfy the strong virtual black-box definition (and the weaker indistinguishability obfuscation definition), it should be the case that all functionally equivalent circuits (that are of similar sizes) must be obfuscated to the same circuit, and this is difficult.

But, what if we are considering a class of circuits where no two circuits in the class are functionally the same? For example, a class of point circuits (where each circuit in the class evaluates to 1 on a specific point that is hard-wired in that circuit, and evaluates to 0 on all other points). Does it make sense to think of deterministic obfuscation in this case?


texts:
Can anyone please help me on how to prove or disprove (by counterexample) whether the following function $G'$ is a PRG (Pseudorandom Generator) given that $G$ is a PRG.

$$G'(s) = \operatorname{trunc}(G(\operatorname{trunc}(s))) \text,$$ where $\operatorname{trunc}(x)$ for a nonempty string $x$ denotes all but the last bit of $x$. (For this part, assume that $l(n) > n + 2$, and ignore the fact that $G'$ is undefined on input strings of length $1$.)

I've tried to think of an approach, but did not come up with anything.
I have some basic ideas like using hybrid arguments!


texts: How to prove element equality in G1 using Groth-Sahai proofs

texts:
In the BeleniosRF e-voting scheme, Groth-Sahai proofs with the "Instantiation based on the SXDH assumption" are used (see https://eprint.iacr.org/2007/155, version 20160411:065033, page 24).

In the BeleniosRF paper on page 8, Figure 2, a Groth-Sahai proof is used to prove $g_1^\overline{r} = c_1$ with $g_1$ being the generator of the first group of a pairing. Using the notation of the Groth-Sahai paper, an equality of two elements in $A_1 = G_1$ must be proven. How can this be done?

This is most likely a special case of one of the described equation types

pairing product equation
multi-scalar equation in $G_1$
multi-scalar equation in $G_2$
quadratic equation

but I'm not seeing how it fits into one of those.


texts:
Recently, Boyle et. al. proposed silent OT extension. In the paper, silent OT, it seems that a GGM based PPRF used as building blocks. However, after reading the paper, I have two questions that are not clear:

For $t$-points PPRF, the authors proposed to have $t$ independent single point PPRFs to be constructed such that those single point PPRFs can be added together to form one multiple point PPRF. Compared to Correlated OT(IKNP-style), which asks the receiver to input the choice bit vector (a.k.a. the points in PPRF), does it mean if I want $t$ 1's in COT choice bit vector, I need to set $t$ corresponding points in multiple point PPRF?

Even compared this multiple point PPRF to Random OT, which still asks the receiver to input the choice bit vector, is there anyway to convert this random choice bit to chosen choice bit with little or no extra communication costs?

Thanks for any suggestions and helps.


texts: Post processing of AAD and len A||C in a hardware AES GCM implementation

texts:
I'm new to GCM and I need to implement it in hardware, using FPGA.
The data bus is 640 bits, so I will use 5 adder/multiplier blocks in parallel.
The message size and AAD size are constant.
My design have a particularity that AAD and Len A||C are available only at the end of message and I don't kow how to process it.

A little example:
message = 5 x 640 bits.

cycle 1: process 640 bits (add/multiply)
cycle 2: process 640 bits (add/multiply)
cycle 3: process 640 bits (add/multiply)
cycle 4: process 640 bits (add/multiply)
cycle 5: process 640 bits (add/multiply) and xor all results
cycle 6: process AAD
cycle 7: process Len A||C

After cycle 5 I have a 128 bits vector with all the messages added/multiplied and results xored.
So, how can I process AAD and Len A||C in this scenario?

Thanks
Rodolfo


texts:
I am working on a crypto project using the secp256k1 elliptic curve.

I know that I can select a random point $P = (x, y)$ from the curve by randomly selecting the first coordinate $x \in \mathbb{Z}_p$ (where $p$ is the prime of the elliptic curve field $\mathbb{F}_p$) and computing the second coordinate $y$ using the curve equation $y^2 = x^3 + 7$. Because the cofactor of the curve is $h = 1$, for every value $x \in \mathbb{Z}_p$ that spawns a valid $y \in \mathbb{Z}_p$, there is a point on the curve with coordinates $x, y$. In case there is a value $x \in \mathbb{Z}_p$ for which the curve equation does not find a valid value for $y \in \mathbb{Z}_p$, that means there is simply no point on the curve at that $x$ coordinate.

I also know that the curve order is $q$, with $q < p$. That means there exist $q$ valid points on the curve, which is less than all the values that $x$ could have in $\mathbb{Z}_p$.

My question is: How far are points from each other, in respect to the $x$ coordinate? What is the largest distance between two points on the curve? Is there any documentation in this regard?


texts: If we have chunk encryption for AES-Rijndael-CBC, should we hash Authenticate/tag each single chunk with a hash vs whole file?

texts:
was frustrated by which one to pick and my brain could not guess which one is better Authenticate the whole file as one with a hash vs authenticating each ciphered text.

So very quickly: i have super large files of many GB, these cannot be encrypted at once with AES-Rijndael-CBC, so i split these large files into smaller chunks that the computer memory can handle and fully encrypt each of these chunks one at a time and append the finished encrypted cipher text and their IV's next to each other. And i want to make sure no manipulation can happen to these ciphered chunks...

So my current setup is this for every plaintext that is encrypted the output looks like this:

first chunk    = [SHA256(PASSWORD + IV + CIPHERTEXT) + IV + CipherText]...
Second chunk   = [SHA256(PASSWORD + IV + CIPHERTEXT) + IV + CipherText]...
Hundreth chunk = [SHA256(PASSWORD + IV + CIPHERTEXT) + IV + CipherText]...

This way i can check if any manipulation has been done before decrypting the chunk by calculating the hash value with my own password...

But then it hit me... instead of doing authenticating each ciphertext chunk why not take the whole file and calculate the hash of it + password?

so it would be something like this instead:

SHA256[PASSWORD + ALLCHUNKS]...
First Chunk     = [IV + CIPHERTEXT]...
Second Chunk    = [IV + CIPHERTEXT]...
Hundredth Chunk = [IV + CIPHERTEXT]...

Am i maybe getting myself into a pitfall here or does this keep the same good tamper protection?

EDIT:
"password" has been derived with PBKDF2 in both showcases.


texts: What is the difference between: ecdsap, ecdsak, and ecdsab in the output of "openssl speed"? What do the letters P/K/B refer to?

texts:
openssl speed tests the speed of different protocols on your computer:

$ openssl speed something
Error: bad option or value

Available values:
...
ecdsap160 ecdsap192 ecdsap224 ecdsap256 ecdsap384 ecdsap521
ecdsak163 ecdsak233 ecdsak283 ecdsak409 ecdsak571
ecdsab163 ecdsab233 ecdsab283 ecdsab409 ecdsab571
...

For the ECDSA options, there are the above list of available ciphers (likely this list is different on different PC's).

What is ecdsap vs ecdsak vs ecdsab? What do the letters P, K, and B mean at the end of the ECDSA algorithm?


texts: CKM_RSA_PKCS vs CKM_RSA_X_509 mechanisms in PKCS#11

texts: What is the exact difference between the CKM_RSA_PKCS and CKM_RSA_X_509 mechanisms in the PKCS#11 v2.20 specification (Please explain with an example)?


texts:
In the paper Biased Nonce Sense: Lattice Attacks against Weak ECDSA Signatures in Cryptocurrencies on section 5.2 Cryptanalytic tests for biased nonces, one of test is:

Select two signatures at random and check for nonces of length less than 128 bits. We repeated this test ...

My question is how this can be done? Mean from one valid signature how can we check bits length of nonce used?


texts: How do you construct a practical full-domain hash function?

texts:
I am looking for practical constructions for Full Domain Hash.

I have read Random Oracles are Practical by M. Bellare and P. Rogaway, the construction suggested on page 8, under "Uniformity: a technicality", but it's unclear whether that is producing a full domain hash, or just ensuring the message is well-formed using an existing hash function.

I haven't found any other information regarding full domain hash constructions.


texts: AES-CTR key reuse attack with same IV and known plain text

texts:
this is from an IT Security exercise which my friend and me cannot solve.

Given

2 AES-CTR stream-cipher encrypted files
Same known initalizing vector
Same (unkown) key
Same 128bit Counter initialized with 0
Files are .png so there is known plain text in both files (the file header)

Our approach was to use the known equivalence of

$E(A) \oplus E(B) = A \oplus B$

From there the only option we see is to brute force $A$ and $B$ for the known $\oplus$ product.

Is there a smarter way to get $A$, $B$? Thanks for any hints!


texts: Is AES-GCM-SIV with fixed IV deterministic authenticated encryption?

texts:
Is there any functional or strong security difference beyond speed between

AES-GCM-SIV with implicit fixed public IV and no additional data
AES-CTR (or AES-OFB) with 128-bit IV computed per HMAC-SHA-512 on the message, included at start of ciphertext, and checked on decryption

when used with a key of the same length, 128 or 256-bit?
And if 2 was not proper deterministic symmetric authenticated encryption (when the total amount of plaintext encrypted under a given key remains well below the birthday bound), I also want to know!


texts: What is the most computationally efficient way of generating pseudo-random permutations?

texts:
I have an application in which I need to create up to J randomly shuffled-copies of an array of length N. Then I will have millions or even billions of iterations such that, in each iteration, I will have to fetch the value of K << N entries of the J permuted copies of the original array. The K entries that need to be accessed are the same for all the J shuffled-copies but that set of K entries changes from one iteration to another.

To give an approximate idea of the dimensions of the problem, assume J = 25000, N = 500000 and K = 50 even if those numbers are not fixed a priori.

The naive approach, which I've been following so far, is to use the Fisher-Yates algorithm (also known as Knuth shuffle) to create the permuted versions of the array, storing them as a NxJ matrix in memory. However, that matrix tends to be too large in many cases, which is problematic. Also, recomputing the entire matrix in each iteration would be painfully slow.

As an alternative, I have started to consider using pseudo-random permutations instead. Using a block-cipher for which the enciphering process had complexity O(1), I could ideally fetch the K entries I need with an extra complexity O(KJ) per iteration. Which appears to be acceptable empirically.

My question, as someone with an extremely rudimentary understanding of cryptography, is which scheme would you recommend me to perform such a task. The key point is that I would rather have a scheme for which enciphering is really fast, even if the security is very poor for cryptographic standards. As long as the set of distinct permutations which can be generated (and look random enough) is in the order of 2^32, it's perfectly fine. AES-like security levels would be a clear overkill.

As a reference, I am currently using a "handmade" 4-round Feistel network with ceil(log2(N)) bits and very simple round functions (16-bit round keys, 8-bits are XORed with one half of the plaintext and the result is passed through a S-box, the other 8-bits are used as an index for a set of 256 random bit shifts). I am also using a cycle-walking scheme to deal with the (common) cases for which N is not a power of 2.

I guess the scheme is a bad joke for cryptographic standards but, for my application (statistical hypothesis testing) it appears to be random enough. It would be great if I could reduce the complexity of the encryption scheme a bit.

I would be really thankful is any of you could provide some advice!

TL;DR I am looking for the fastest possible way to generate pseudorandom permutations of a set of size N. I care much more about the speed than the security of the scheme (about 2^32 "truly" random permutations is more enough).


texts: NIST implementation of the Lucas primality test

texts:
The NIST standard FIPS 186-4 describes an implementation of the Lucas primality test in section C.3.3.

I can follow the algorithm but I am puzzled by step 6.2:

$V_{temp}=\frac{V_{i+1}^2+DU_{i+1}^2}{2} \bmod C$

Where does this expression come from?

I do understand this is the step that computes $V_{2n}$ from $V_n$ and $U_n$. However, all relations I can find for Lucas sequences of any use in the binary expansion are in the form:

$V_{2n} = V_n^2 - 2Q^n$

Is there perhaps a way to go from this expression to the one used in the NIST implementation (with $Q = \frac{1-D}{2}$ and $D$ taken from the sequence $[5,-7,9,-11,\dots]$)?


texts: Attacks on code misusing RSA_public_decrypt

texts:
I've encountered some code that I'm reviewing that is misusing RSA_public_decrypt to "authenticate" a variable-length response without using any hash. The code assumes that a successful decryption means that the given data buffer was generated by the server and processes it without any additional checks.

I believe that this is unsafe, even though the code is using the RSA_PKCS1_PADDING mode. Is there a reference to a set of attacks on misuse of RSA in this way?

For additional context, this code is using a 2048-bit key with e=3.


texts: How does AES/CTR/PKCS5Padding works when the bits to encrypt is more than 8 bits

texts:
I am a bit new to java crypto, lately, I was going through some articles regarding the use of AES/CTR/PKCS5Padding for encryption. I read that

  The block size is a property of the used cipher algorithm. For AES it is always 16 bytes.
  So strictly speaking, PKCS5Padding cannot be used with AES since it is defined only for a block size of 8 bytes. I assume, AES/CBC/PKCS5Padding is interpreted as AES/CBC/PKCS7Padding internally.

So, Even if the data is more than 8 bytes (say 10 bytes), will this be padded upto the next block size of 32 bytes (AES Block size) or 16 bytes (PKCS5 block size) or will this not be padded at all?


texts: What is the importance of AES add round Key (K0)?

texts:
A high-level overview of AES is according to Wikipedia

Key expansion;
Initial round key addition;
9, 11, or 13 rounds;
Final round (making 10, 12, or 14 rounds in total).

I can understand all the steps except step 2 which is known as key widening.
What is the importance of the key widening step? How does it contribute to the overall security of AES? What is the importance of this step and how does it contribute to the overall security of AES?
[EDIT] I heard that it helps to in implementing the encryption recursively but can't see how is this possible. as this is done only time at start of encryption and end of decryption.  Implementing this in a recursive function will cause each round to XOR the input with 2 keys.
So what exactly are the benefits of this initial add key step?


texts: Is there any research about cryptography on nondeterministic Turing machines?

texts:
I know it's a highly theoretical topic, but I was wondering if there was any research out there about what cryptography would be like assuming that we had access to nondeterministic Turing machines.

It seems to me like you couldn't have the kind of exponential hardness assumptions that we currently have, but the Time Heirarchy Theorem states that we can create functions that require $O(n^k)$ operations for any arbitrary k, which seems like it's almost as good.


texts: Python implementation of a blind signature scheme which doesn't involve RSA

texts: RSA seems a bit creepy after the Snowden revelations and i'm looking for a simple python based blind signature library to fiddle around with. So far i've been unable to find anything. What am i missing?


texts: Why does BCRYPT_RNG_DUAL_EC_ALGORITHM get removed from CNG API on Windows 10?

texts:
On article at => Microsoft Docs

  CNG Algorithm Identifiers

I notice that BCRYPT_RNG_DUAL_EC_ALGORITHM is now removed since Windows 10.

  Beginning with Windows 10, the dual elliptic curve random number generator algorithm has been removed. Existing uses of this algorithm will continue to work; however, the random number generator is based on the AES counter mode specified in the NIST SP 800-90 standard. New code should use BCRYPT_RNG_ALGORITHM, and it is recommended that existing code be changed to use BCRYPT_RNG_ALGORITHM.

Does this imply that Elliptic Curve PRNG is considered unsecure already?

The Government's elliptic curve backdoor is real, isn't it?


texts: High-level overview of system architecture of LUKS/cryptsetup (how it works vs. how to setup)

texts:
I've been searching (unsuccessfully) online for a high-level overview of how LUKS/cryptsetup disk encryption works. I am reading through the cryptsetup source code to try to understand what is going on "under the hood", but my limited knowledge of C (and crypto code in particular) is making it difficult to understand how everything fits together.

I was wondering if short of reading the sources, there was a way to simply describe/visualize the major sub-systems of LUKS/crypt-setup, and the role they each play in creating secure disk encryption (i.e. the rationale behind the architecture).

I've found plenty of decent online guides that describe how to setup a LUKS/cryptsetup. For example:

How to set up an encrypted filesystem in several easy steps
HowTo: Linux Hard Disk Encryption With LUKS

... but very few of these types of "how to" articles actually go into the details of the overall architecture and why certain commands are being typed in. So it makes me feel like I'm just blindly typing in commands without really understanding what they are doing, and the implications of each on the overall security of the system.

I'm looking for something that doesn't necessarily focus on how to install LUKS/cryptsetup, but rather focuses on "high-level" discussion and diagrams covering the basic system  architecture, along the lines of these articles for other crypto subjects (just as a few random examples):

The Advanced Encryption Standard (Rijndael)
A Stick Figure Guide to the Advanced Encryption Standard (AES)
Let's Encrypt - Technology

Could someone either share a pointer to such a references, or share a brief overview of the LUKS/cryptsetup here?


texts: Unbalanced Feistel network only generates complete permutations with square lengths

texts:
I'm generating permutations with a generalized Feistel network which will output integer values $r_j$ in a specified range $[0,period]$ pseudo-randomly, according to the counter input, which will then cycle after having reached each of them all exactly once.

Rather than splitting the counter into two equally sized bitvectors $L$ and $R$, I'm operating on a quotient and remainder, with the ambition of generating permutations of arbitrary length, unlike the $2^n$ that a balanced network or maximal LSFR might generate.

uint16_t feistel(uint16_t counter, unsigned period)
{
    uint16_t d = sqrt(period);
    uint16_t s = period - d*d;
    uint16_t q = counter / d;
    uint16_t r = counter % s;

    for (int i = 0; i < 3; i++)
    {
        uint16_t nr = r;
        uint16_t F = (i * r + q);
        r =  F % d;
        q = nr;
    }

    return q*d + r;
}

This code can correctly generate some maximal permutations. However, it only does so for periods that are square numbers (where s = 0).

Can this be changed so that any choice of period generates a complete permutation? Also, are there any broader numerical issues surrounding the choice of how a number is split and manipulated in an unbalanced Feistal network (divisor * quotient + remainder, sum of two primes, left and right bitvectors, etc)?


texts: Is a stream cipher similar to One-Time Pad using hash secure?

texts:
I've read some Q&A about combining OTP with hash on this site, but I still wonder why some answers said that using hash for OTP key is not strong enough to resist brute force attack?

Assuming that the key is never reused and the adversary has unlimited computational resources so that the adversary can try all keys easily. Is the adversary able to find out which one is correct from all of the plaintexts after getting all possible plaintexts?

For example, if the adversary gets "Give me 100 dollars.", then he might get "Give me 200 dollars." too. If he can't filter out the wrong plaintext, how does he know the correct key and crack it?

I know the amount of possible plaintext depends on the amount of possible hash value, but if the adversary gets at least two possible plaintexts and has no any method to distinguish the right one from them, will this cipher encrypted by hash key have any chance to be cracked by brute force attack? If no, then are there any flaws in this encryption technique? (Ignore the message authentication problem)


texts: Trying to implement ring-LWE KE to understand the concept

texts:
Today, after reading so much about ring-LWE key exchange, I decided to implement it in java to see if it works. Not a real world implementation, just to see if math works out. My assumption was that writing a code would be simple given some sort of Polynomial ring. My assumption turned out to be wrong. I searched internet looking for basic uni-variate polynomial ring library and I found this. It looked simple and had some jUnit test already that code was passing. I copied the parameters from here. In short, $\mathbb{Z_{2^{23}-1}} / (x^{1024} + 1)$.

I followed Regev's basic reconciliation method and ran the code. Even if there is no error, the exchanged keys did not match. Obviously, something is wrong and I am certain it is from my code not the Polynomial ring library. Maybe I did not understand some fundamentals of ring-LWE. I attached the code here:

This is the link for GitHub repository. Any help would be appreciated. I don't know what I am doing wrong.

Math: dimension = 4 (arbitrary)

$A, S, S' = [rx^3 + rx^2 + rx + r,\\ rx^3 + rx^2 + rx + r,\\ rx^3 + rx^2 + rx + r,\\ rx^3 + rx^2 + rx + r]$

s.t. $r \in \mathbb{Z_{q}}$ (randomly generate)

$B = AS + error$, $B' = AS' + error$

$Shared key = SB' = S'B \to$ I did not use any error ($error =0$) but still shared key does not match.

Pseudo-code:

dimension = 8 # arbitrary
modulus = 65537
R = PolynomialRing(GF(modulus), "X")
S = R.quotient(X^1024 + 1, "x")

A = generate_matrix(dimension, modulus)
S = generate_matrix(dimension, modulus)
S_ = generate_matrix(dimension, modulus)

B = A.transpose()*S
B_ = A.transpose()*S_

alice = S*B_
bob = S_*B

print alice == bob  # returns false

Update:
I tried to write the code in sage (without any error) and still something is wrong. I am now sure my math is wrong. This is the link for sage code.


texts: Is BLS signature still conjectured to achieve $b$-bit security for $2b$-bit appendix?

texts:
The BLS signature scheme [1] promised $b$-bit security for signature with a $2b$-bit appendix, under classical hypothesis leaving aside the possibility of Quantum Computers usable for cryptanalysis. Hovav Shacham's 2005 thesis proposed to use Barreto-Naehrig curves to achieve security comparable to RSA-1024 ($b\approx80$-bit security) with a $2b=160$-bit appendix.

However, per this summary of 2016 attacks, BLS signature using BN curves turned out to require larger appendix; like perhaps $8b/3$-bit appendix for $b$-bit security with $b\approx128$ (with Barreto? and Menezes-Palash-Singh considering $3b$-bit for something conservative).

Is BLS signature still conjectured to achieve $b$-bit security for $2b$-bit appendix using some concrete construction, and which? If not, what comes closest?

If that's not too much a different question, what would be a concrete parametrization for $b\approx128$-bit security?

[1] : Dan Boneh, Ben Lynn, Hovav Shacham, Short Signatures from the Weil Pairing, in Journal of Cryptology, 2004, originally in proceedings of Asiacrypt 2001.


texts: Reason for including the public key of the key agreement in the KDF

texts:
I found the following text when looking up KDFs:

  In comparison, the so-called DHAES mode in IEEE 1363a mandates to use the binary representation of the sender’s public key as an input parameter.

where a quick lookup suggests that DHES and DHAES are simply earlier names for ECIES.

What would be the reason to include the sender's public key into the KDF as a parameter? Other ECDH based schemes do not seem to do this.

If the sender's public key is altered then the calculated shared secret $Z$ would be invalid and the KDF would fail to generate the correct key anyway. Is this just an additional spurious security measure or am I missing some significant reasoning?


texts: Why does DES implement so much Cross Wiring?

texts:
I've been going through DES, and I find that most of the blocks simply Reshuffle the input, which may be termed as "Cross Wiring". This include IP, IP-1, PC-1, PC-2 and even Expansion (although this seems to be more useful than the rest).

Why does DES do it? Is it for a reason, or just for fun maybe?


texts: What is the minimum recommended number of rounds for Argon2?

texts: I'm hashing passwords with argon2 using Python's passlib library and am wondering how many rounds I should use to future proof security. The default uses 2 rounds but I'm wondering if it'd be sensible to increase this. The documentation doesn't make any specific recommendations.


texts:
I'm trying to understand how AES works. I got as far as knowing how a password is converted to an unifinished key with the PBKDF2 function. After that RFC3962 says that an AES useable key most be derived from the unfinished key:

Then it refers to the DK function in RFC3961, and no further information is left on the DK function in RFC3692. So in RFC3691 it says that:

So I went to look for how the random-to-key function is defined. I couldn't find anything, only a small table in RFC3692 that said the random-to-key function is the 'identity function'. I could find no clue on what this identity function was in the RFC3692 document.


texts: Can we prove possession of an AES-256 key without showing it?

texts:
Imagine this situation:

Alice has an AES256GCM key $K$, a plaintext $X$, and $Y$ which is the ciphertext of $X$ encrypted by $K$
Bob has $X$ and $Y$
Alice and Bob can communicate with each other
Bob wants to know whether Alice holds the key which encrypts $X$ into $Y$

In this situation, Can Alice prove that she has $K$ without showing $K$?
and if so, how to do it?


texts: Is there any block-cipher, format-preserving or similar encryption method with known cycle size? (without short-cut, with known source/runtime vars)

texts:
E.g. given a $n$-bit message $m_0$ and an encryption function $f$
After applying the function $c$ times it will result in $m_0$ again.
$f^1(m_0) = f(m_0) = m_1$
$f^2(m_0) = f(f(m_0)) = f(m_1) = m_2$
..
$f^c(m_0) = m_c = m_0 $
On top of that an inverse function $f^{-1}$ with about equal computation time should exist as well. Also no short-cut in computing $m_i$ is allowed. It always either require the knowledge of  $m_{i-1}$ or $m_{i+1}$. Given two messages $m_i$, $m_j$ there should be no easy way to compute the difference $|i-j|$
Some example but with unknown cycle size would be AES.
I'm looking for an encryption method with known cycle size $c$ for all $m_0 \in  \{0,1\}^n$
.
Further notes:

$m_0$ will be a random number. An additional (fast) function is allowed
which select only numbers with certain properties

instead of $m_0$ a small known offset $k$ is allowed as well. With this
$m_c$ can be different to $m_0$ but $m_{c+k} = m_{k}$

'hacking'-time should scale linear with cycle size $c$

(Edit) Update: Additional requirements

an attacker has full access to the source code and runtime variables. All computations done at the local computer
given two valid random messages $m'$ the chance should be high they are part of the same cycle (lets say $>10\%$ or at least $>0.4\%$). Or in other words different cycles are allowed but not much more than $10$ or $256$ as max limit (lower is better, except $<20$ would even be better than just $1$)
exact cycle size don't need to be known. An approximation $\pm 50\%$ is sufficient (but if it contains multiple cycles those should be similar to each other ($\pm5\%$) )

Other than in most cryptography problems the relation in between should be encrypted not the messages themselves.


texts: Zero-knowledge proof for multiplication in the exponent

texts: We have $c_1=g_1^x$, $c_2=g_2^y$ and $c_3=g_3^{x/y}$, where $g_1,g_2,g_3$ are generator of a group of order $n$ and we don't know the DL between them. Is there any sigma protocol or zkp that can prove the language $L=\{c_1,c_2,c_3\mid \exists\, x,y, \text{ such that } c_1=g_1^x \ \& \  c_2=g_2^y \ \& \  c_3=g_3^{x/y} \}$?


texts:
Application uses AES in CBC mode with 128 bit key. In this implementation key is always same and is equal to IV.
Can attacker get the key or decrypt data? If he knows:

First and second blocks of plaintexts;
All blocks of ciphertexts.

The software mentioned above is malicious program, it encrypts all office files on user's computer. And I now attempt to help user get his data back. Reverse engineering of this program shows that key is unknown, but is always same and is equal to IV.


texts:
What I'd like to do is to have the Prover store a value x where x remains hidden.
From x, I'd like to extract one blob r1, and save it in the Verifier's database.
Later in the future, the same Prover who holds x should compute a new r2 from x, such that one cannot easily extract x from r2 and send it over to Verifier.
Verifier can compare that two distinct and different r1 and r2 and know that they came from the same x without revealing anything about x.
I hope I didn't misunderstand that this is what Fiat-shamir Heuristic tried to do.
I made a working example of this based on this code snippet structure:
p = Proof()
# k is random
p1.k = random()

# g is a prime number
p1.g = random_prime()

# where r is the commitment of Prover
p1.r = p1.g^p1.k

# Where y is the public key of x
p1.y = p1.g^p1.k

# Where c is the hash of the commitment
p1.c = Hash(p1.r)

# Where s is the output of the commitment algorithm
p1.s = p1.k + p1.c*x

# Now, the Verifier needs to store all of the above somewhere
# After X months, the same Prover makes another blob (call it p2) and wants to verify if p1 came from the same x as p2

(r1, r2) = (p1.g^p1.s * p1.y^p1.c, p2.g^p2.s * p2.y^p1.c)

What I'd like to know is the following:

Is there a known library or codebase that does this somewhere?
What is a safe bit-size for the prime numbers used (is 4096-bits realistically even possible?)
Assuming an attacker can sniff c and r and everything about p1 and p2. How realistically is it that they can A) forge a similar packet and B) extract x?

Much appreciated


texts: Why should one use a cypher-based message authentication code (CMAC) instead of symmetric encryption and CRC?

texts:
What are advantages/disadvantages for using a CMAC that proofs the integrity and authenticity of a message but doesn't encrypt the payload itself? Why should it be used instead of symmetric encrypted payload and CRC (CRC is encrypted as well)? This could also proof authenticity, integrity AND confidentially.
From my point of view the only reason is when one has a huge amount of data, encryption takes too long and confidentially is not required. But what about short message? In both situations the same key is used and using a symmetric encryption fulfills the security goal confidentially...


texts: Cipher Block Chain continued Initialization Vector

texts:
Assume a communication session between Alice and Bob (being client and server, in my case). Alice uses a secure random generator to generate both a key and an IV for use with AES in CBC mode.

Alice transmits both the key (and IV) over a "secure channel" (RSA is being used), together with a message that has been encrypted using these parameters, to Bob.

Bob decrypts the message, and wants to send a message back, obviously using the same received session key. As I am working using a bandwidth constrained channel, every byte saved is a win.

Is it okay for Bob to use the last AES ciphertext block as initialization vector for his transmission, given that this is the way CBC works?

If not, why not? If so, can I keep on chaining using this method, assuming a perfect lossless channel?

Bonus question: if it works, is it possible to apply this to other block modes?


texts:
I have a naive question(as non specialist in this field).

While reading Weierstrass Curve description,I found that it turns into 2 periodic tori on 2D complex plane.
Is is it possible to create fast multiplication attack on this curve by implementing this transformation into tori on complex plain - like 2D clock multiplication by decomposing numbers into two dimention on complex plane?
Here is something similar to this

Elliptic Curves Lecture #17
Complex Multiplication: Lecture 5


texts: Does public-key + hashing create a security vulnerability?

texts:
The title says it all really...let's say I have a packet of data that one of my applications needs to store encrypted with a public key (RSA, say, with the private key kept elsewhere). Let's say the application also then needs a way of determining if said packet has already been stored, so I combine it with a randomly generated salt and save the hash of packet+salt so I can check it later (e.g. MD5). Does storing the combination of these three pieces of data...i.e. encrypted packet, the salt and the hash....result in data that is significantly less secure than the encrypted packet alone?

I realize "significantly less secure" is an arbitrary metric. I'm not after anything military grade (for want of a better nonsensical term), I just want to make sure I'm not doing anything overtly silly.


texts: Why are good passwords required if we use good hashing algorithms?

texts:
Again and again are we adviced to make good passwords: At least 12 chars, numbers, signs, upper and lowercase.

But why is that really needed?

I can see the need, if the system uses a hashing algorithm that can be implemented in ASIC, where an attacker can test trillions of combinations per second.

But using scrypt, Argon2 and similar technologies we ought to be able to make it so expensive for an attacker that testing just billions of passwords will be infeasible. Both can be tuned to require a massive amount of RAM, and in that configuration they are not at all comparable to MD5, SHA-1, or SHA-2. E.g. if we make the hashing take 3 seconds and use 1 GB RAM it will take 100 CPU-years and 100 GB*years to test just 1 billion combinations.

Would it not be relatively easy to trade compute+RAM ressources for allowing simpler (though not completely trivial) passwords?


texts: Insecurity in Needham and Schroeder protocol?

texts:
I've been studying specifically the authentication algorithm Needham and Shroeder, and understand the idea in general of the message exchange. But, researching on the subject, I found a question that I do not know the correct answer to, and I would like to get some feedback from someone with more experience on the subject.

At one point in the algorithm agent A asks B to send an N encrypted with the session key in the form of challenge.

Example :

A - > B [ Nb ] Kab

Kab : session key,
Nb : a number sent by B,

Says the question that this step is not safe , and asks to explain why.
The only problem I see is the message of this session key, Kab, be violated . Anyone can access the session key, or there is some flaw in this step?

Because only if A and B have the key, Kab, this message can only be decrypted by these two agents.

Another problem may be the message playback, somebody third agent captures the [ Nb ] Kab and sends later getting the opinion that knows Kab, this can also be a problem? The latter case can be solved with a timestamp .


texts: SPDZ- How to do secure equality comparison

texts:
The SPDZ paper explains how the SPDZ protocol can be used to find the sum/product of secret values and find the sum/product of a secret and a non-secret value (page 6).

The paper seems to say that from this you can do any other operation. How would you use this to do secure equality comparison between a secret and a non-secret value?

The Array Lookup section of the Bristol SPDZ implementation tutorial shows that their implementation has a way of securely evaluating whether a secret value equals a non-secret value to get a secret result. This is heavily used in Array lookups so one would hope it is an efficient operation. How did they implement this? It doesn't seem to be in the paper.


texts: What does "crypto_box" actually mean in libsodium and NaCl?

texts:
I cannot find what "crypto_box" actually means. In general, and in specific cases, what does "box" do? I know that libsodium is authenticated encryption, but GPG is not. "Box" makes me think the encryption and signing are somehow sealed and protected.

What does "crypto_box" mean in libsodium and NaCl?


texts: Is this streamable combination of encryption and MAC secure?

texts:
I want to combine encryption and MAC.

For encryption I use AES-256 with CBC and PKCS5Padding.
For MAC I use HmacSHA512.

I use the Encrypt-then-Mac approach (calculate MAC over the ciphertext and deliver it with the ciphertext)

The algorithm should be able to process streamed data, and if I calculate the MAC once over the whole ciphertext, there are two possibilities:

Prepend the mac to the ciphertext:

This is a very bad idea, because the encryption part has to encrypt the whole text before it can output the mac. Therefore it's not streamable. On decryption, we have to process the whole ciphertext before knowing if is compromised (also not fully streamable).
Append the mac to the ciphertext:

Better idea, but the decryption part can only check the MAC in the end. Before that, it did output many bytes that could have been changed by an attacker, or it has to wait until it sees the MAC (not streamable again).

So I need a solution which divides the ciphertext into parts and then calculates a MAC for each part. Because the ciphertext shouldn't be much larger than the plaintext, I choose a MAC block size that is greater than the encryption block size (for example 4 kB).

I want to use a pattern like (with $c_X$ = part X of the ciphertext, $m_i$ = part X of the MAC):

$$ m_1 || IV || c_1 || m_2 || c_2 || m_3 || c_3 || \dots $$

The calculation of the first MAC is clear ($k$ being the MAC key):

$$ m_1 = MAC(k, IV || c_1) $$

But then we meet problems. If we just use

$$  m_X = MAC(k, c_X), $$

this wouldn't be secure. An attacker could change the blocks in order, he could duplicate or remove whole blocks, and so on.

So I thought about an idea similar to CBC mode in encryption:

$$ m_X = MAC(k, m_{X-1} || c_X) $$

Is this now secure? And is there a difference to this one?

$$ m_X = MAC(k, c_1 || ... || c_X) $$


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


texts:
I'm trying to encrypt a protocol that shares data between devices on a local area network (i.e.no connection to the internet). I don't want to use predefined keys because they're too easy to read from the firmware. What I'd like is for the devices to dynamically setup an encrypted network which prevents anyone reverse engineering the protocol. Someone once told me that when it comes to encryption "never roll your own" so I'm wondering what's out there.

The requirements are:

Must work over Ethernet (minimum of 10MB/s).
Must not require internet access.
Must not have hardcoded or otherwise predictable keys, and keys must be revocable/replaceable (from HedgeMage).
Devices can be added and removed from the network (note all devices are supplied by us).
Messages can be sent unicast and multicast (between multiple devices).
Encryption should be immune to replay attacks.
Encryption should be capable of being run on an ARM CPU with only basic HW cryptographic support (i.e. solution can't rely on any specialised HW).
No scope to add additional HW like smart card readers.

Does anything like this already exist?


texts: Is Chaocipher a secure cipher under ciphertext-only attack?

texts:
Chaocipher was invented by John F. Byrne in 1919. The algorithm was recently revealed – see Moshe Rubin's Chaocipher Revealed, the Algorithm (PDF).

While a known plaintext attack successfully finds the keys, nobody has been able to put forward a general solution to this cipher. Is that possible?


texts: How unsafe is to share parts of a password

texts:
The best way to ask this question and have a concrete answer is to set a very specific example. This is the example I would be interested in reading an answer to:

Consider that my friend Alice has several (~5) hard drives encrypted with Truecrypt. Alice is using AES (256-bit, 14 rounds) with RIPEMD-160. I could see that she has a script for mounting the different drives -I guess that because she's pretty lazy and just wants to type in one password. Of course, every disk is salted differently, etcetera.

From her script, I can figure out that the password for each drive comes from concatenating a common string (for all drives) with a fixed string set in the script (different for every drive). I don't know the length of the common string (it's user typed), but the fixed strings are like 6-10 characters long.

Let's then first assume that I don't know the common part of the password, but I know the fixed part for every disk because I see it in the script.

So the question is, and don't be afraid of diving into explaining the mathematical reason- how insecure is the fact that she uses a common string, and how could I attack that flaw?

And secondly, what if I didn't know the fixed part for every hard drive but I knew that they begin with the same common part (which value is unknown too)?


texts: Securing communication between limited embedded systems

texts:
I am currently trying to harden communication over a limited physical communication channel on an embedded system.
The Scenario
I think the system is rather typical for small embedded applications:

The embedded systems involved are small microcontrollers without any OS, which
can be assumed to be in a secure physical environment. The connection
channel is physically accessible to aggressors, they can interfere
with messages as desired.

Different communication channels are possible: e.g. RS485 or RS232.
There is a crude protocol which handles stuff like addressing and crude
integrity (e.g. CRC16 for bitflips) on which we can build. Think of
it as being a slow TCP.

Each communication partner knows a root certificate which can
act as a CA and has an own unique certificate(+key) signed by it. Certificates are self signed, elliptic curve prime256v1

The mbedTLS library is available for these systems (with DH, AES, ..).

Most of the time there is no internet available.

The systems can keep time and can create sufficient random numbers

I want to reach privacy, authenticity and integrity.
How it might be solved
A rule in cryptographic protocols is to never implement them on your own.
Unfortunately I did not find anything that matches this use case.
I also browsed through existing questions, but nothing provided the full solution i was searching for.
Finally in this answer implementing an own protocol is given as the last option.
This is why I came up with the solution described below - but I am not entirely sure about it.
I oriented on this answer on how to authenticate a Diffie-Hellmann Key Exchange, this answer on how to check integrity and this thread giving me some ideas on how to implement such a protocol.
Protocol to secure communication
First thing to do is to randomly generate a symmetric key K.
First thing sent is a handshake message.
It has the following fields:

Field
Description

DH
The Diffie-Hellmann key exchange msg gK

Cert
The certificate(-chain) of the sending device

MsgIdNonce
A random 64-bit value

Signature
A signature of the complete message using the private key of Cert

Both devices send (and receive) such a message.
When a message is received the following is done:

Check if cert is signed by the expected CA (has to be in chain)
Check if msg is properly signed with cert and its key

When these checks succeed the sent and received DH gK messages are used to calculate a symmetric key.
From this point on, applications can send messages encrypted with AES-CBC. As messages could be lost relatively often, IV is always in the message.
This is the message format:

Field
Description
Encrypted

IV
Initialy Random IV for AES
No

MsgIdNonce
Handshake/Last MsgIdNonce + 1 or + 2
Yes

Application Data
The data/commands to protect
Yes

CMAC truncated to 64 Bit
MAC for checking integrity
Yes

For a message to be accepted it must

Have the expected MsgIdNonce (1 or 2 above last received one) - preventing replay attacks, allowing to lose 1 message
Have a valid CMAC - preventing attacks on integrity
Be received max. T seconds after the last message - preventing delay attacks

If anything is not as expected, Handshake is sent again, then message is sent again with newly exchanged parameters.
Questions
Am I on the right path or should I try something completely different?
Does this provide my security goals or do I miss any obvious vulnerabilities here?
Can this work?
I hope you can help me and other embedded engineers facing similar problems!


texts: Is the inverse of a secure PRP, also a secure PRP?

texts:
If a block cipher is a secure PRP, is it's inverse a secure PRP as well?  My intuition says yes but I'm not exactly sure.

On a related note, if a block cipher is a secure sPRP, is it's inverse a secure sPRP?

I'm using the terminology "PRP = secure against chosen-plaintext attacks", "sPRP = strong PRP = secure against chosen-plaintext/ciphertext attacks", where "secure = indistinguishable from a random permutation".


texts: Can Differential Privacy be used to show that two distributions are indistinguishable?

texts:
Differential privacy can be used to show that the "privacy loss" of a certain computation is "bounded" in a meaningful way.
In cryptography, often "indistinguishability" is considered, i.e. we want $\Delta(D_0, D_1)$ to be small.
Can these two concepts be related?
I know vaguely that standard notions of differential privacy can be related to things like "concentrated differential privacy", which itself is a Renyi-type bound on two distributions (which is somewhat similar to the total variation distance bound that I want).
But I want to end my proof with "So, the two distributions are indistinguishable" --- can differential privacy help me with this goal?


texts: Why do we use prime numbers apart from hard factorization?

texts:
Why are prime numbers important in cryptographic constructs? I am not interested in RSA examples where factorization is the hard problem itself, that makes sense. However wherever I go I encounter prime numbers, especially prime order groups and more specifically safe primes from Discrete Log to ECurves etc. Is it only due to Pohlig-Hellman??

Logic says that any type of modular operation is a kind of trap door function that hides the original information regardless of being modPrime.


texts: KDF for generating RSA and ECC keys from a 2048 bit secret

texts: Do KDFs exist for generating RSA and ECC keys from a 2048-bit random secret?


texts: How can I prove that this encryption scheme from a random oracle is secure?

texts:
I am reading this example:

  A random oracle is an ideal object.

  What makes a random oracle convenient for proofs is the part about knowing nothing on the output for a given input if you do not try it. For instance, consider the following encryption scheme:

  $H$ is a random oracle which outputs $n$-bit values.
  The key is a $K$, a string of $k$ bits.
  A single message $m$ is encrypted by computing $c = m \oplus H(K || 1) || H(K || 2) || ...$ (you repeatedly "hash" with the random oracle the successive strings obtained by concatenating $K$ with a counter, and you concatenate the oracle outputs into a big stream which is XORed with the message to encrypt).

  If $H$ is a random oracle, then it is reasonably easy to prove that the encryption is secure up to a work factor of $2^{k-1}$ invocations of $H$.

How I will be able to prove that that the encryption is secure up to a work factor of $2^{k-1}$?

pdta: I think that the encryption is secure up to a work factor of $2^{k}$.


texts: How do we know if we have successfully decrypted something?

texts:
Suppose for any given typical Bob, Eve and Alice encryption example where Bob and Alice exchange information using RSA. Bob encrypts his message using Eve's public key and sends his message off to Alice.

If I was Eve, suppose I attempted to brute force the private key, and kept doing it mathematically by computing the encrypted message to the power of x, where x is the private key I am trying to find.

When brute forcing the message, how do I know what I have successfully found it?

For any given number x, there is an output, by how do we know that we have found the private key? Does it just check that the output is an english based sentence, what if the output is just something that is another encoding and the output is jibberish again, how would Eve know?


texts: Which flaws does the following 2 out of 3 threshold secret sharing algorithm have?

texts:
Let's say the secret is an ordered set of two 8-bit integers — $\{a, b\}$.

First, we generate additional entropy, another ordered set of random 8-bit integers — $\{c, d\}$.

\begin{gather}
a \oplus c = e\\
b \oplus d = f\\
c \oplus f = g\\
d \oplus e = h\\
\end{gather}
Using these equations we end up with three shards, ordered sets of two integers: $\{c, d\}$, $\{e, f\}$ and $\{g, h\}$. With any two of these, it would be possible to recover the original secret.

Are there any flaws in this algorithm? How secure is it given that a, b, c, d are all random?


texts: Cryptocurrencies: Undetectable Nothing-at-Stake - why does it matter?

texts:
The paper Formal Barriers to Longest-Chain Proof-of-Stake Protocols (Brown-Cohen, Narayanan, Psomas, Weinberg, 2018) describes an attack on Proof-of-Stake cryptocurrencies called Undetectable Nothing-at-Stake (p. 11, 4.2 - Recency, Definition 11).
I don't understand why this attack matters. The paper says

Depending on reward scheme, there may be an expected monetary gain for [undetectably] announcing [blocks on different forks].

As far as I understand it, the attacker simulates multiple independent miners like in a Sybil attack. But for the attack to be undetectable, it also needs to divide its stake among the miners it simulates. This way, each of the miners has only a fraction of the stake, so it can only mine as much as an independent, honest miner with this fraction of the stake. Otherwise it could be detected. This is because it can only behave the same way an honest miner with a high latency connection might behave. How can this lead to a higher gain?


texts: For TCG-Opal drives, which password is used to derive KEK?

texts:
SEDs use a user password (PIN) to generate KEK by a KDF algorithm. The KEK is then used to encrypt the MEK (where MEK is internally generated in the drive). But TCG-Opal drives have 9 locking-ranges and each of these ranges uses its own MEK (say MEK1 - MEK9). There are also 4 Admins and 8 Users, each has its own password. Which of these passwords are used to generate the KEK, or are there multiple KEKs? The TCG core spec and the Opal SSC spec don't detail the relation of a password to the MEK of any locking-range.

Links:
TCG Storage architecture core spec: https://trustedcomputinggroup.org/wp-content/uploads/TCG_Storage_Architecture_Core_Spec_v2.01_r1.00.pdf
TCG-Opal: https://trustedcomputinggroup.org/wp-content/uploads/TCG_Storage-Opal_SSC_v2.01_rev1.00.pdf
TCG and NVMe Joint white paper: https://nvmexpress.org/wp-content/uploads/TCGandNVMe_Joint_White_Paper-TCG_Storage_Opal_and_NVMe_FINAL.pdf


texts: Getting the key used for HMAC given the hash and the plaintext?

texts:
I'm working on a little exercise to understand the drawbacks of poor library choices and I've been presented with the following scenario.

The HMAC function in python is being used (md5). I know the message being hashed as well as well as the resulting HMAC for this message. The key being used is generated by random.getrandbits(128).

The only thing I can think of is to put the random.getrandbits(128) in some kind of while loop and generate HMACs for the message until I find a match with the given HMAC.

Is there any way I can extract the key being used by the hmac function knowing the message, the function used to generate keys and the message digest, that does not involve brute-force?


texts: Why isn't E' secure if it's built over a secure cipher?

texts:
Let $E$ be a semantically secure cipher.

Let $E'(k,m) = E(k,E(k,m))$.

How would one prove that $E'$ is not necessarily secure even if $E$ is?

It doesn't make sense to me. If you consider the advantage of an attacker $\mathcal{A}$ over a semantically secure cipher $E$, you have $SSadv[\mathcal{A},E] = \epsilon$, where $\epsilon$ is negligible.

If you call for $E(k,E(k,m))$, you should have $E(k,E(k,m)) = E(k,c)$, where $c$ is $\epsilon$-distant of being random, so you give an advantage of $\epsilon$ to the attacker.

When you compute $E(k,c)$, analogously you give another advantage of $\epsilon$ to the attacker, so you give an overall advantage of $(\epsilon + \epsilon)$, and such a sum would be negligible as well.


texts:
Consider the following property of one-time symmetric encryption scheme $(\mathsf{Enc}, \mathsf{Dec}, \mathsf{K})$. For Every message distribution $M$, every pair of messages $m_0,m_1$ belonging to $M$ and every ciphertext $c$ belonging to $C$, it holds that:

$$\Pr[M=m_0 | C=c] = \Pr[M=m_1 | C=c]$$

Argue that the above property is not a characterization of perfect secrecy via a counterexample. Consider the one-time pad and any non-uniform distribution over $\{0,1\}^j$.


texts: I have an embedded device with a AES CBC engine on it that is used to ensure the integrity of the firmware. I know that CBC mode requires unique IVs to be any good, but I'm unsure if it makes a large difference in this scenario. The AES key is stored in hardware on chip, and before firmware is loaded, it's decrypted with the key using decrypt hardware also on the chip. If I understand this correctly, that would mean that the same key encrypting the same plaintext will always result in the same ciphertext, meaning it's deterministic. Assuming the attacker can obtain the encrypted firmware (but not the key, so he can't encrypt anything with the key), does the fact that no IV is used really make a difference?


texts: Are sufficiently large key sizes enough to deter quantum attacks for symmetric key ciphers?

texts: Are sufficiently large key sizes enough to deter quantum attacks for symmetric key ciphers such as AES?


texts: How can I factorize a 350 bit (106 decimal digits) number in two prime factors?

texts:
I have this large number:

1728098743723095094470726818328193358068864405124007684733613106475812450278961107574624070107782941006379

which is the multiplication of two unknown large prime numbers. I try to factorize it with the "Yafu" tool, but i get an error of "time exceeded.

How can I factorize it? How many time will it take?


texts: The question "Virtual key generation in Logical Key Hierarchy" asks how specific keys are constructed in LKH. Since I haven't heard of it and it isn't immediately obvious (not even from the linked RFC) what it does or how, can somebody provide a short explanation?


texts: How can I tell which curve a given ECDSA implementation uses? (P-521 or something else)

texts:
I'd like to test and see if certain software uses P-521 ECC curves, or if it uses another variant.

Without having access to the sourcecode, or the specification, is there any way for me to test which ECC curve a given implementation of software uses?

Take a x509 certificate as an example, aside from ASN.1 information that may exist in the file, is there any way to look at raw cryptographic outputs and determine the curve used?

What is the minimum information needed to understand what curve is being used?  (What variables on the client, or on the issuer/CA are needed)?


texts: Chosen ciphertext insecurity in an ElGamal variant

texts:
I'm trying to prove something and if I can show that there is a simple way to calculate $(g^a \bmod p)^k$ if I know both $g^k \bmod p$ and $g^a \bmod p$, then (I think) it will help me prove it, but I'm not able to see an obvious way to use the two expressions to calculate the other. Is there a property in modular arithmetic that would allow for that? Or does it seem clearly untrue? I think there may just be some gaps in my knowledge about modular arithmetic so if you have a resource for that you'd like to point me to, that might also help.

If it makes a difference, the broader question I'm trying to solve is the following. We consider a modification of the ElGamal cryptosystem (called the basic ElGamal cryptosystem) where we have $p$, a prime, and $q$, a prime divisor of $p-1$. We have $g$, an element of order $q$ in $\mathbb{Z}^*_p$. The private key is an integer $a$ chosen randomly between $1$ and $q-1$. The public key is $h = g^a \bmod p$. And the ciphertext is $c=\langle c_1, c_2\rangle$ where $c_1 = g^k \bmod p$ and $c_2 = m \, h^k \bmod p$, where $k$ is random between $1$ and $q-1$. I need to prove that this is insecure under a chosen ciphertext attack (and whether it is insecure based on total break, one-way security, semantic security).

Since I know that the regular ElGamal cryptosystem is semantically secure if the Decisional Diffie-Hellman (DDH) assumption holds, I thought that if I can prove that it doesn't hold here, I can show that it is not semantically secure. That's why I wanted to ask this question but if this doesn't make sense as a way to show this, let me know so I can try something else.


texts: Finding Small Roots of Multivariate Polynomial Modulo an Integer in Sage (Coppersmith's Attack on RSA)

texts:
I am trying to implement Coppersmith's attack to find small roots of an example bivariate polynomial.

$f(x,y) = (8x+7)(8y+7) - N \pmod{8}$

In this example, the results should be $x = 2$ and $y = 8$  (obviously you could brute force it, but that's besides the point).

For univariate polynomials, Coppersmith's attack is implemented via the .small_roots() function.  However, it is to my understanding that finding small roots of a multivariate polynomial modulo an integer is not implemented in Sage.  Is there any workaround code / method that will allow for small root finding of multivariate polynomials?

Relevant papers:

http://honors.cs.umd.edu/reports/lowexprsa.pdf

http://www.jscoron.fr/publications/bivariate.pdf

Thanks, and your time and effort are greatly appreciated.


texts: CBC mode is not IND-CCA2 secure with no prediction of IV

texts:
How can it be explained that CBC mode is not IND-CCA2 secure, in case that the IV can't be predicted by adversary.

Edit:
In decryption of CBC, for each block it is XORed with previous block's cipher text. So there is no need to decrypt previous block before XORing it for the next block. Now if adversary change 1 bit in the received cipher text in IND-CCA2 and send it for decryption. As in IND-CCA2 only the challenge cipher text is not decrypted. Anything else will be decrypted. So as 1 of the bit in the challenge cipher text was changed so its plain text will be send back to adversary. For CBC modes decryption we know that plain text box corresponding to changed cipher will be corrupted and in following block of plain text corresponding bit to changed bit is inverted. Rest of the block remain same. So adversary will just compare these unchanged parts with the original messages it sent and with whichever message unchanged parts of cipher text messages matches it will pick that one and win the game. Is this approach to prove that CBC mode is not IND-CCA2 secure even if the adversary don`t know the IV?


texts: How secure is Firestore / Google Cloud server-side encryption?

texts:
We use Firestore. On their Google help page they say it is AES encrypted.

https://cloud.google.com/firestore/docs/server-side-encryption

But this means in the moment a user is logging in, the data is decrypted on the server not the client? So if there is a corrupt Google admin guy, could he wait till I login and then get the decrypted data?


texts: What is the relationship between attribute based encryption (ABE) and access control?

texts: So if possible could someone tell me or at least recommend a book.


texts: Brute-force breakability in practice determined by recognizability of plaintext?

texts:
It seems to me (a non-expert obviously) that the brute-force breakability of symmetric encryption algorithms is usually (always?) expressed as "would take approximately N time on such-and-such hardware".

But in practice, how would one single attempt among trillions at finding the key be identified as "the right one" that succesfully decrypts the message? Doesn't that require the result of the attempt (i.e. the "plaintext" result) to be recognizable as such?

If yes, doesn't this mean that if the plaintext is not easily and quickly recognizable as such (as for example ASCII-encoded English prose might be), brute-force is in practice MUCH harder than the so-much-time-on-such-hardware description suggests?

And if yes, doesn't this mean that a trivial (but unknown) "pre-encryption", e.g. ROT13 or base-64 encoding makes a brute-force attack hugely more difficult?


texts: Construct points with the same discrete logarithm

texts:
Assume we have an elliptic curve $E$ with a Tate (or Ate,...) pairing
$G_1 \times G_2 \mapsto G_T$
Now the task is to find $g_1, g_1' \in G_1$ and $g_2, g_2' \in G_2$
such that the discrete logarithm $x$ is equal, i.e.
$g_1' = g_1^x$ and $g_2' = g_2^x$

That is easy, but now comes the hard part:
This has to be done without knowing $x$. Moreover, the constructor of the points has to provide a proof that he does not know $x$.

With just $g_1' = g_1^x$ alone, that would also be easy by hashing into the group $G_1$.


texts: Computationaly hard detokenization algorithm for credit card numbers

texts:
I am designing a vault that tokenizes credit card numbers (a plaintext that consists of 16 decimal digits), with the following requirements:

Given some plaintext, the vault returns an index.
   If the plaintext does not exist it returns a new index.
   If it does exist it returns the same index it had returned before for that plaintext.
The vault allows detokenization (given index return the plaintext),
   however this is quite rare (once a month) and involves authentication procedure.
The vault stores the plaintext encrypted using an algorithm so that detokenization
   of one index is computationally possible but hard.
   Let the costs of detokenization be X per entry.
An attacker that got access to the vault should find it too computationally expensive
   to detokenize the entire vault.
A variation: the attacker may have access to a limited list of (index, plaintext)
   pairs that they injected into the vault before they compromised it.
   Let the length of this list be Y.

What is the encryption algorithm that should be used for this use case? Can it be designed so that X is configurable (given Y=0)? Can detokenizing the entire vault be computationally hard regardless of Y, or must we assume Y = 0?

Edit:

I've modified the original question. Instead of tokenizing a 6 decimal digit plaintext, the question is now about tokenizing a 16 decimal digit credit card number.

Both a legitimate user and a very skilled attacker has access to partial credit card numbers. A partial credit card number consists of the first 6 plaintext digits, the last 4 plaintext digits, and the index received from the vault. In order to find the remaining middle 6 digits the legitimate user would authenticate and detokenize, while the skilled attacker would have three options:

Perform a limited number of tokenizing operations without compromizing the vault.
Compromise the vault and perform 50,000 tokenizing operations per plaintext.
Compromise the vault and perform one detokenization per plaintext.

Additional information:

Many credit cards share the same first 6 digits.
Werther the plaintext is the complete 16 digits number or only the middle 6 digit number is part of the design.
The index length is part of the design
Once the vault is compromised the attacker has access to the vault storage/memory which contains everything except one-time keys that were properly erased. The same attacker has also compromised the detokenizer's private key stored elsewhere if there are such keys.

Edit 2:

Removed the requirement that the index is random. It just need not to be some hash of the plaintext to avoid brute forcing the index without compromizing the vault.
Changed brute force tokenization per plaintext from 100,000 to 50,000
Obviously the plaintext could be encrypted with a public key, and assume that only the authorized detokenizer has the private key. Alas, if a skilled attacker has enough resources to compromise the vault (by hacking into the vault machine) , the attacker has enough resources to compromise the private key (by hacking into the machine containing the private key).
 Assuming the hack is discovered in timely fashion, the cards would be canceled before the hacker sold the Cards in the black market.
 For that purpose, the detokenization of the entire vault must be so hard that it would delay the attacker for a long time, or would require vast amounts of compute resource to make it non-economical in the first place.
It is expected to make the tokenization computationally hard - so 50,000 tokenization operations per credit card number would be non-economical or would take too long (configurable)
It is expected to make the detokenization computationally harder than 1 and less than 50,000 tokenization operations (configurable).


texts: Is Bruce Schneier Applied Cryptography, Second ed. up to date?

texts:
I like Applied Cryptography, and I am returning to cryptography after a while. So I am wondering if that book is up to date or can be complemented with other references.
I am looking for a book, authoritative, well documented. Possibly including code.
I would prefer to have a book as a reference, instead of asking naive questions to the community for something I could find in a book like Schneier’s. I wish to ask the community for help to understanding what’s in the book or ask for help on specific real world problems.
I have a background in cryptography, number theory, data, and coding.


texts: Group Signatures with VLR Revocation Check

texts:
I was reading the paper by Boneh et al. Link. The scheme describes what is called a Verifier Local Revocation Technique. The Scheme assumes that a Revocation List [RL] allows each verifier to check the validity of the signature. The revocation check works as follows:

$e(T_2/A,\hat{u}) =^{?}e(T_1,\hat{v})$, Given $T_1 = A_iv^\alpha,T_2 = u^\alpha$
$e(A_iv^\alpha/A,\hat{u}) =^{?}e(u^\alpha,\hat{v})$

In the case that $A_i\in$[RL], $A = A_i$, then,

$e(v^\alpha,\hat{u}) =^{?}e(u^\alpha,\hat{v})$

The author then claims that these pairings are equal, The $(\hat{u},\hat{v})$ are generated as follows:

$(\hat{u},\hat{v}) \leftarrow H_0 = (gpk,M,r) \in G_2^2$ , Given that:
$u\leftarrow\psi(\hat{u})$, $v\leftarrow\psi(\hat{v})$,

  I have three questions:

Why the $(\hat{u},\hat{v}) \in G_2^2$ not $G_2$.
What is the Hash Function that generates two parameters and is there a relation between them?
How the check $e(v^\alpha,\hat{u}) =^{?}e(u^\alpha,\hat{v})$ is valid.


texts: Why do 1st and 3rd key have to be the same in 2 key 3DES?

texts:
From this answer:

  However, that wasn't the only situation they had in mind; they also
  considered the case where someone implemented 2 key 3DES in hardware
  (which the first and last subkeys were constrained to be the same)

Why are the first and last keys constrained to be the same?


texts: (Uniformly) Random Value when an element is picked with $\frac{1}{p-1}- \frac{1}{(p-1)^2}\ $ probability

texts:
Let's $\mathbb{F}_p$ be a finite field where $p$ is a large prime number(e.g. 256-bit)

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

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


texts: Known plaintext attack on 3 round SIMON block cipher

texts:
I am attempting to write a program to perform a linear approximation attack on a reduced round version of the SIMON block cipher, but I am stuck on how to actually apply the linear approximation to get the subkeys for each round. I found this paper, in which the following high-bias linear approximations are listed:

P[ F(X)_i = X_(i-2) ]                        = 3/4
P[ F(X)_i = X_(i-2) ^ X_(i-1) ]              = 3/4
P[ F(X)_i = X_(i-2) ^ X_(i-8) ]              = 3/4
P[ F(X)_i = X_(i-2) ^ X_(i-1) ^ X_(i-8) ]    = 1/4

Where F(X) is the nonlinear function in the SIMON algorithm and F(X)_i is the ith bit of the output of said function, and X_n is the nth bit of the input to the function. This all makes sense to me. I am stuck, however, on how to leverage these linear approximations to derive the subkeys for each round. How do I go from the linear approximation to a program that finds the subkeys? If anyone could help me close the gap in my understanding, or at least point me in the right direction, I would be very grateful. Thanks so much!

Edit: originally posted on Stack Overflow


texts: Why use PBKDF2 over SHA-512 to derive AES encryption key?

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

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

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


texts: What will happen to existing cyphertext when today's encryption is broken?

texts:
Even optimistically, I think we can all agree that many encryption algorithms that are widely used in production today will be "broken" sometime in the next decades.

With "broken", I mean that (probably because of quantum computing but maybe because of some black swan) it will be possible to decrypt ciphertext that is generated through those algorithms with a substantially lower effort as opposed to today. And over time, this "attack cost" will only decrease.

Again, no doom scenarios, I am optimistic. Let's assume that every system that uses cryptography will upgrade/switch to "quantum computing proof" cryptography before it becomes reasonably easy to break today's encryption.

However, even in this scenario, can we agree that all "old" ciphertext (that is being generated in PRD all over the world as we speak) will be easily breakable ? Again: "sometime in the next DECADES" ...

If we can agree on this, let's discuss the implications. I list some things that I can think of. Please comment, prove me wrong, add, ...

Encrypted e-mails, Whatsapp/Telegram/... messages, ... that are stored on any server or on any device in general (e.g. a mobile phone confiscated by police) will be easily decryptable. Idem for encrypted files on servers or any devices.
TOR traffic will become as crystal-clear as unencrypted direct traffic. Let's assume a TOR entry node logs everything. Once the encryption attack cost is low enough, those logs can be decrypted and they would show for example: "ip address 1.2.3.4 sent me a request at 1:01 AM May 12th to visit website X through TOR path A B C".
Idem for VPN's. Or for "VPN over TOR" or "TOR over VPN".
Also ISPs who keep logs can dig into all that happened in the past. Idem for example for public wifi hotspots who keep logs (or any "proxy" between the users' device and the ISP).
Passwords / secret keys can be "sniffed" from logs.
Payments through cryptocurrencies that promise anonymity (like Monero) will become just as crystal-clear as payments in non-anonymous currencies like Bitcoin.
Again, we assume that also cryptocurrencies will have switched to quantum computing proof cryptography by when the attack cost became very low, but the history of what happened while using the old algorithms will not magically disappear. Hell, not making it disapear is exactly what blockchain does ....

My guess is that this "event", sometime in the next decades, will unveil proof against a lot of criminals who are safe now thanks to cryptography.
Likewise it will open many doors for people with bad intentions ... Sniffing passwords from "old" logs. Blackmailing people through "old" secrets from "old" ciphertext. Company secrets being stolen. Etc etc.

I am not saying that this is good or bad. I am just saying that imo this will be a very notable event in the next decades and that it's worth discussing about what impact this will have.

Since this is a "question answering" and no discussion website, here you go:
If/when today's widespread encryption algorithms become easily breakable (for example through quantum computing), what will be the implications of the fact that the existing data encrypted through these algorithms becomes public to those in possession of the ciphertext ?


texts:
I am working on RC4 encryption/ decryption algorithm based on the following:

A wants to send M to B, for that A did:

H = Hash (K||M)
C = Ek (M||H)

A sent ciphertext C to B. (I have completed until this part)

Upon receiving of ciphertext B calculate:

M||H = Dk (C)

Now, how do we obtain M as I need to verify if H' = Hash (K||M) holds.


texts: Best method to achieve authenticated encryption with openssl

texts:
Problem

I want to send a plaintext document between from myself to someone else over an untrusted link. I want to firstly stop third parties from reading the document, I want the receiver to be able to authenticate that any message they receive comes from me. Finally I want the receiver to be able to read the document. I have the ability to give the receiver a key by a trusted channel.

Proposed solution

the document is encrypted with a symmetric cipher. The aes-key I was going to use for that could be turned into a signature. e.g.

openssl pkeyutl -sign -in "aes.key" -inkey privkey.pem -out sig.nature

This signature is not used for authentication (a separate signature based on the hash of the encrypted file is used for that), but it seems to hide the value of the key, which can then be extracted with the public key, e.g. openssl rsautl -verify -inkey pubkey.pem -in sig.nature -pubin >> aeskey.recov

The public key will not be made public, but will be given to the reciever via a trusted channel and secured. I understand however if the public key is ever compromised, then all my encrypted documents can be decrypted.

Is this valid (providing the public key remains private) or is there a better way to do this?


texts: Size of reduced bases of orthogonal lattice

texts:
I consider the following setting. Let $L$ be a lattice of rank $d$ in $\mathbb{Z}^m$ ($d\leq m$). The orthogonal lattice of $L$, denoted by $L^{\perp}$, is defined as the intersection of the orthogonal to the $\mathbb{Q}$-vector space generated by $L$ with $\mathbb{Z}^m$.

My question is in the following context: if I know that the determinant of $L$ is bounded from above, say $\det(L) \leq B$ for some $B$, what can I then say about the successive minima of the lattice $L^{\perp}$?

Some papers I came across suggest that $L^{\perp}$ has a reduced basis consisting of very short vectors compared to a reduced basis of $L$, and thus one expects that $L^{\perp}$ has a reduced basis consisting of vectors with norm around $\sqrt{m-d} \det(L^{\perp})^{1/(m-d)}$. (see for instance page 36 between Theorem 1 and 2 in the paper http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.90.7518&rep=rep1&type=pdf).

Concerning this heuristic, I would like to know how strong thedge the Gaussian heuristic applies to the length of the shortest non-zero vector and not to an entire basis of reduced vectors. Is there a generalised heuristic to explain this?


texts:
I've reading on GPG since yesterday and I have a doubt: the whole system of double key encryption does make sense but it looks to me like either way you are compromising something in terms of security.

If someone sends me an encrypted file using GPG and he/she wants to make sure that I'm the only one able to decrypt it then he/she will encrypt that file using my public key. Now, the only way to decrypt it is to use my private key, which supposedly I'm the only one in the world to have it. So far, so good.

However, if we also want to make sure that there are no forgers and that we're actually exchanging files between us (issue 1) then we would need to encrypt files using each one their own private key. This requires us to share our public keys. But here we go, another problem (issue 2): what if I published my public key on a website/blog/etc. some time ago and I had forgot about it? What if an intruder is able to intercept such messages and by using the public key (that he/she found online) is now able to decrypt files?

The way I see it you have to compromise, and you can't really mitigate 100% both issue 1 and 2. Did I misunderstood something about GPG?

At this point, why not simply try to rely on a 7zip encryption and use a (moderately complicated) passphrase that you both know?

Thanks!


texts: How to transform a text into numbers in the shortest way possible?

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

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


texts: Does it make any sense to hash parts of a hashing target?

texts:
TL;DR;
Assuming I'm calculating SHA256 for an ECDSA, does it make sense to do SHA256(item1 + SHA256(item1') + item2 + SHA256(item2') + itemN + SHA256(itemN')) or it's the same (security-wise) as SHA256(item1 + item1' + item2 + item2' + itemN + itemN')?
(hereunder + refers to as binary concatenation of operands' content in binary format)
Details
I have a data structure similar to the one below (presenting in JSON format for readability)
{
  "Lorem": 123,
  "Ipsum": "qwerty",
  "Items": [
    {
      "Id": 4321,
      "Data": "SOME_DATA_HERE",
      "ItemSig": "A_RELATIVELY_BIG_BINARY_STRUCTURE_AND_ECDSA_SIGNATURE_OF_HELLO_FIELD_CONTENT"
    },
    {
      "Id": 8765,
      "Data": "SOME_DATA_HERE",
      "ItemSig": "A_RELATIVELY_BIG_BINARY_STRUCTURE_AND_ECDSA_SIGNATURE_OF_HELLO_FIELD_CONTENT"
    }
  ],
  "Sig": "A_PLACE_FOR_ECDSA_SIGNATURE"
}

I also have an ECC key pair. Now, I need to sign over each element within the "items" array and then over the entire structure itself.
When signing over the entire structure, I'm proving some data in that structure (contents of Lorem and Ipsum), and per each Item, I'm proving that the item was in that structure (by including Id in the signature) and proving that item's content (by including ItemSig which includes the content).
I think it worth noting that I include ItemSig instead of the item's content in the structure's signature to prove that the item was signed by the same ECC key as the structure itself. This is because there are multiple ECC keys that are valid for signing, but it's considered invalid to sign items with one ECC key while signing the structure with another.
So the question is, what's better option for structure's Sig field (and why?), ECDSA(SHA256(Content)) where

Content = Lorem + Ipsum + Items[0].Id + SHA256(Items[0].ItemSig) + Items[1].Id + SHA256(Items[1].ItemSig) + Items[n].Id + SHA256(Items[n].ItemSig), OR
Content = Lorem + Ipsum + Items[0].Id + Items[0].ItemSig + Items[1].Id + Items[1].ItemSig + Items[n].Id + Items[n].ItemSig.


texts:
I've being studying up on AES, GCM, CBC, HMAC and a lot of other primitives and am somewhat ( a little bit, perhaps) familiar with them however I am still a bit weary on the use of the keys and nonce.

Background:
I have got multiple (embedded) devices (sometimes hundreds) all of which are connect to a server. These devices are to communicate with either AES-CBC HMAC or AES-GCM. when using HMAC I know first to encrypt then MAC. Further more these devices have a pre-installed key on them.

Here is what i think i know:
1. You can have 1 master key but AES and HMAC never use the master key directly
2. You should use a KDF like PBKDF2 to create a session
3. Every so often you should change the master key

Now say we start connecting a device to the server. Both the device and the server have the same master key but they must agree upon a session key. I cannot do this in any other way than to use Diffie hellman? simply sending over a salt for the PBKDF2 won't do since an attacker might alter it.

Then, when using CBC, we create a random number as IV, we encrypt the message, add the IV and then use the HMAC with the session key, append the result and send it over.

When using GCM we create a nonce, encrypt the text, append the nonce to the cipher text and send it over, we either keep sending the nonce over or we keep a counter on both sides either way we always +1 the nonce.

So my question:
is diffie hellman a must have? or is there an other way to do? keep in mind I am very restricted in processor power and memory so using a PKI with RSA is not an option.

is everything else i described correct?

1 final remark, It is often said it's better to use 2 separate keys (1 for encryption 1 for HMAC) this simply means using DH twice


texts:
In the paper Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller, Micciancio and Peikert mention that it is possible to save an additive $n$ term in the dimension $\bar{m}$  in paragraph $\textbf{Further optimizations}$ in section 5.2 if we use a single tag $H=I$. I want to use this together with the computational instantiation but I do not get how to reduce this case to the LWE-problem here.

We can obtain a gadget-matrix $G' = \left[ I \  | \ \tilde{G} \right]$ with an identity submatrix by a unitary transformation $G' = G \cdot U$ where $G$ is the gadget-matrix mentioned in the paper. Thus, $S' = U ^{-1}S$ is an adequate basis for $G'$ where $S$ is the basis from the paper.
Next, we let $\bar{A} =  \hat{A} \xleftarrow{$} \mathbb{Z}_q^{n \times n}$ and $R \xleftarrow{} D$ be random and then we obtain a "tuple" $\left[ \bar{A} \ | \ 0 \right] T^{-1} = \left[ \bar{A} | -\bar{A}R  \right]$ or the parity-check matrix
$A = \left[ \hat{A} \ | \ G' - \hat{A}R \right]$. But in this case I don't how to use this as an instance of decision-LWE.


texts: What key length has to be send to a recipient when using a stream cipher?

texts:
I was being argued that stream cipher's key that is the length of the message must be sent to the destination for them to be able to decrypt the message.

My point is: don't you only have to send the seed of the PRG let's say the 128 bits key for RC4 128 and then the destination can recreate the full length key from the 128 bits you sent them. Am I correct or wrong?


texts: Do the elliptic curves over prime fields must always contain prime number of elements (prime order)?

texts: I have gone through one example where i saw a curve defined over some prime number containing non-prime order.


texts: What is the order of the Identity point on prime order elliptic curve groups?

texts:
I'm trying to understand how the identity point is represented in a group of prime order.
What I think is correct:
If the group has even order, then the identity point is in the group, because the identity point has order 2.
If the group has prime order, like elliptic curves such as secp256 then the identity point can still be represented as a group, but is the point at infinity. If the point could not be represented in the group, then it would not be a group.
I do not believe I completely understand the second point. What order is the identity point if it is in the group?


texts: A private key with multiple public keys?

texts:
I'm trying to design a wallet, where any number of public keys can be handed out. Say Alice hands out the public keys to receive messages. She doesn't want others to be able to link all of the public keys to the same person. They should each look random, so that giving out N public keys causes a bystander to believe that there are N different people.

I know that this can be done by having a master private key $p_0$, and generate future private keys with something like $p_{i+1} = \text{Hash}(p_i, p_0)$. However, in order to decrypt the message, Alice would have to try every single private key. I'm doing this in a browser and JS Tests with ECC appear to show that it's a bit slow for a UI once you have a dozen or so keys, but doable if Alice can wait a second (Though not ideal). If you're trying to decrypt dozens of messages at a time, this quickly becomes impossible with too many private keys. And at least in my case, I will have to try to decrypt many messages.

What I really want, is to simply have one private key, and any number of desired public keys. Most cryptosystems have specific key-pairs. And while you can simply concatenate a group's Public Keys to get N Private Keys : 1 Public Key (Decryption requiring every individual), there doesn't appear to be well-known algorithm for 1 Private Key : N Public Keys.

The examples mentioned here did not help, because they are all too slow if decryption requires an ECC multiplication.

==

QA Format: I expected to find a solution on this SE, since it didn't seem like a complicated question, but couldn't. Anyway, I'm posing it here to help others / for those who are interested since I thought it was fairly neat.


texts: Encryption with 2 symmetric keys and decryption with one key

texts:
Here is my use case:
I need to keep encrypted data in Hadoop. The data is encrypted with symmetric key that is being changed every half a year.
When data is retrieved it should be decrypted.

Lets say that data from 1/1/19 until 6/30/19 is encrypted with key1, and data from 7/1/19 until 12/31/19 is encrypted with key2.
The issue is that if I retrieve data from 5/30/19 to 7/30/19 I need to decrypt half of the data with key1 and half of the data with key2.

So I am looking for a solution that, for any query with a year time range, will enable to decrypt with a single key.

One solution I was thinking of is to encrypt the data with 2 keys (key1 AND key2) and decrypt it with any of the keys (key1 OR key2). Is is possible?


texts: Advantages of making streamcipher stream depend on plaintext?

texts:
Most descriptions that explain how streamciphers work (like the one on Wikipedia), tend to describe a model that boils down to a simple “$ciphertext = plaintext \oplus stream$”, where the stream is determined by a nonce and a key, while the plaintext and ciphertext do not affect the stream at all.

On the other hand, streamcipher designs like Helix* seem to ignore the usual approach as their stream depends on the plaintext… reasoning that this approach adds authentication.

My personal feel is, that the dependence on plaintext has a good chance to introduce additional attack vectors (chosen plaintext attacks etc.).  Looking at the potential downsides, it’s a bit unclear to me if I’m missing something. Maybe there are other reasons or arguments – besides the authentication aspect – which might support the idea of ignoring the regular streamcipher model, and I’m not seeing them.

Is there anything else to be gained by making the stream depend on the plaintext? If, what are the other potential advantages (besides gaining authentication) of making the stream depend on the plaintext, compared to the more frequently used “$ciphertext = plaintext \oplus stream$” approach?

* “Helix: Fast Encryption and Authentication in a Single Cryptographic Primitive” by Ferguson, Whiting, Schneier, Kelsey, Lucks, Kohno

Nota Bene: In his “Salsa20 Design” paper on page 4, Bernstein asks an alike question – ”Should the stream be independent of the plaintext?” – and argues against it. But he merely argues about the authentication part of things and nothing else… which doesn’t really help when trying to learn about the potential benefits such a construction might have besides the debated authentication aspect.


texts: Is AES-CTR or ChaCha20 vulnerable to a time-memory trade off?

texts:
Is AES-CTR or ChaCha20 vulnerable to a time-memory trade-off attack?

According to this paper it seems to be, which would put AES-CTR at a clearly breakable $2^{64}$ security level (for AES-128-CTR).  Since AES-128-CTR is not considered breakable something is wrong with this statement and I would like to know what.


texts: Why in the Fiat-Shamir heuristc for proving the knowledge of a discrete logarithm an hard to invert function has to be used to create the challenge?

texts:
Consider this example from Camenisch, J., & Stadler, M. (1997). Proof systems for general statements about discrete logarithms. Technical Report/ETH Zurich, Department of Computer Science, 260..

If the function $\mathcal{H}$ was easy to invert, how a dishonest prover (a prover who does not know $x$) could exploit it to create a valid proof anyway?
Wouldn't it be hard anyway to find $c,r$ such that the equation $c = \mathcal{H}(g,y,t) = \mathcal{H}(g,y,t') = \mathcal{H}(g,y,g^ry^c)$ is satisfied?
If $\mathcal{H}$ was easy to invert, I could choose $c$ and get the corresponding $t$ (instead of choosing $v$ and compute $t$ and $c$), but I believe it would be still hard to find $r$ such that the previous equation is satisfied.
In particular, in order to get $v$ from $t$ I should be able to compute discrete logarithms and in order to compute $r=v-cx$ I still miss $x$. Another approach may be finding another $r$ satisfying the previous equation, but this is hard and it seems not related with how hard it is to invert $\mathcal{H}$.
Could you help me to clarify this?


texts: Practical examples of Threshold Secret Sharing?

texts:
Threshold secret sharing is pretty cool, but unlike, say, public-key cryptography, I haven't really heard about it "in the wild". It appears to be confined to discussions of theoretical scenarios, as I have not found any real-world software that claims to use it "in anger".

So, are there practical examples of threshold secret sharing in commercial, or at least publicly-available, systems?


texts:
I currently implement the AES(128,192,256)(ECB,CBC). Does the type of padding affect security?
I just want to fill the blocks with null bytes.