texts: What is the best way of deterministically choosing N of M, given 32 bytes of sha256?

texts:
I have a list of M=10,000..100,000 items and 32 bytes of sha256 H.
I want to choose N=10..100 items (without order).
Is there an efficient way to do this?
Or should I use something like (sha256hmac(n, H) & 0xFFFFFFFFFFFFFFFF) % N and skip duplicates.  (Where n is 0..N-1.)


texts: Are there any good examples of Contemporary Mechanical Cryptography?

texts: Are there secure mechanical cryptosystems in use today? Not necessarily alphabetic either, ie digital but mechanical?


texts: Comparing elliptic curves over prime fields against EC over binary fields

texts: In which scenarios we go for prime fields or binary fields? Please indicate why we would choose one over the other.


texts: Prove I know a value v in a set s.t. K = H(v)

texts:
Is it possible to prove that I know a value v in a finite set, such that the hash of the value v is K.

Where v is private and K is public


texts:
During the heydays of rotor machines, the internal rotor wiring was always a closely guarded secret. Even fully cleared repair staff was not allowed to do anything that could reveal it.

As the wiring seems to be considered part of the algorithm 1 and not some form of long time key, would it be even possible to design a secure rotor machine that fully follows Kerckhoffs's principle?

I've found conflicting reports on this. On the other hand, there are still unbroken Enigma-encrypted messages, even though the details of the Enigma are known nowadays.


texts: Standard format to store text in LSB steganography?

texts:
I am trying to understand how text is stored in images in LSB.

If we consider a 24 bit image, we have 3 values per pixel (RGB). So we can store 3 bits in a pixel. So how do we store 'A' or any other character in this situation? Do we store 6 bits in 2 consecutive pixels and then last 2 bits in RG of next pixel and then start storing the first bit of next character from B of the same pixel?

Also, is there a standard for this? E.g. should we start from the first pixel always? If not, is there a way to guess by looking at the pixel values from where the data is stored?


texts:
I'm learning about client puzzles for DoS (Denial of Services) Protection, and I came across this question.

  For each request, the server sends the client a freshly generated random challenge r and and a difficulty parameter n, and the client has to produce a solution s such that HMAC(s) with key r ends in n zero bits."

What is the expected number of HMAC computations for the client to compute the solution, and the server to check the solution?

I know that the server only needs to compute 1 HMAC, as it has s, r and n. So it would just take the clients solution s, and compute the required HMAC, and see if it has the required number of zero bits at the end.

How would I calculate the answer for the client? I assume the client has to brute force it, so he would keep calculating an HMAC until he gets the required n zero bits at the end. How do I do this computation?


texts: How can I generate a deterministic evenly distributed random number in a blockchain

texts:
Here's the hypothetical. There's a blockchain, which for the sake of simplicity, is modelled around Bitcoin and proof-of-work.

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

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

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

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

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


texts: How does AES introduce confusion and diffusion?

texts: I know that in AES the shift-rows and mix-columns operations introduce diffusion, but I don't understand how they create diffusion. Also, I know the add-round-key operation creates confusion, but I don't understand how it creates confusion by simply XORing the round key with the columns of the state matrix.


texts: Uniqueness of representation of $y$ to the bases $g$ and $h$

texts:
Let $G$ be a cyclic group of order $n$, with $n$ an RSA modulus.
Let $g$ be a random element generating $G$, and $h$ another element which discrete logarithm to the base $g$ is unknown.

Given an element $y \in G$, a representation of $y$ to the bases $g$ and $h$ is a pair $(x_1, x_2)$ such that

$$y = g^{x_1} h^{x_2}.$$

This definition can of course be extended to tuples of arbitrary length, but I am mostly concerned with the case of two bases. This concept is useful, e.g., in the proof/signature of knowledge of representation.

My question is: is such a representation unique?

That is, is there a pair $(x_1', x_2') \neq (x_1, x_2) : y = g^{x_1'} h^{x_2'}$ ? Why/why not?


texts: ECC - complex multiplication and key agreement

texts:
I'd like to ask three questions - 2 of them regard CM method. The last is regarding the ECC domain parameters generation on the fly, see https://eprint.iacr.org/2015/647.pdf

What role has discriminant $D$? When generating new curve, what I should choose as $D$? I saw $D=1$, but other source says is should be bigger number, so I dont know...
The same as 1), but what is class-number explanation for dummies?
In the source I provided, they discuss on the fly generation of parameters. I understand that every end-point generate new elliptic curve group with CM method for just one DH key agreement, but I dont understand how this end-point can communicate with other party. If both parties want to communicate, they need to have same ell. curve group, but how they can have same group if every of them randomly generates their own group...?

Thanks for any comment.
Daniel


texts:
How long would it take on average to perform a timing attack on HMAC over brute forcing a 32bit tag if the hash is good?

For example, let's take the hash: 79b7cdc3 to calculate the first byte you have to try:

00 000000
01 000000
02 000000
.........   n^256
FE 000000
FF 000000

total number of guesses and thus 79 would be the 79th guess.

So would the probability of guessing the first byte be, n^256 ?

Or am I going about this wrong?


texts: I am currently trying to understand this Ring LWE article and I have a question. I don't understand how to apply Lemma 5.11 in order to get the worst case to average case reduction in Lemma 5.12, as long as Lemma 5.11 works for subsets of $\mathbb{R}^n$.


texts: Security of CBC-MAC fixed length with zero padding

texts:
I see everywhere that fixed length CBC-MAC should be more or less secure against forgery. But is it really ?

Could you forge a message assuming by example that you use CBC-MAC with let's say always 100 blocks (if it is less than 100 you pad with 0 until it reaches 100 block, so you can authenticate message from 0 to 100*block length bits) if you have access to an oracle?

You don't know the key(it is fixed), the IV is fixed to 0 and the Oracle only returns the MAC.


texts: What are linear and non-linear elements in cryptography?

texts:
I was reading this answer, How secure is XOR for encryption, and it stated that XOR's aren't good for securing messages as they are linear in Nature. And therefore should be paired with some non-linear elements like Substitution box to provide strength to the encryption.

My question is, what are linear/Non-linear elements, in context of cryptography? And what are advantages and disadvantages of each over the other.


texts: Can the passphrase of a PGP key be deduced from an old backup?

texts:
Let's assume that Bob, at some point in time, has created a PGP (key length and other parameters are not relevant at this point).  For some reason, he has chosen a very poor passphrase, for instance lemon.  Some time later, Bob realises his poor choice and decides to change his passphrase to something much more secure, for instance There is no doubt that a longer passphrase is more secure than a single word.

There's the catch:  At some point before the passphrase was changed, the private key somehow leaked (e.g. due to a not appropriately secured backup scheme or some other mishap).  Either way, Eve now has Bob's private key, but not its passphrase.  Given the poor choice of the original passphrase, this will just be a matter of time, so for the sake of the discussion let's assume that Eve eventually manages to deduce the passphrase in some way.  She thus has both the private key and its passphrase and will be able to decrypt it.

The key itself of course is compromised at this point, this is without question.  Eve is certainly able to decrypt her (barely protected) copy of Bob's private key, even if Bob's copy is now encrypted in a different manner (read: new passphrase).  So I guess this corresponds to a known plaintext attack on the private key.  Will Eve be able to deduce Bob's /new/ passphrase (and thus possibly other keys where he used the same passphrase) in this scenario?


texts:
I got asked this question and I didn't know what to answer.

  How do you test the security of your cipher?

What comes to my mind now would be to test it with famous attacks: padding attacks, exhaustive searches by modifying the input and expecting the output, timing attack…

Any idea?


texts:
Good evening,

I'm about to write my own quadratic sieve implementation in C using GMP library for large numbers. I'm facing an issue while attempting to do the last factorization step for the number: (I try to validate an example from a lecture)

$$
\begin{equation}
     n = 9788111 (3571*2741)
  \end{equation}
$$

My book tells me how to calculate a solution. This congruence will only lead to a primitive solution:

$$
\begin{equation}
     3131^2*3174^2*3481^2 \equiv  (2*5^3*7*11^3*43)^2 = 100157750^2
  \end{equation}
$$

$$
\begin{equation}
gcd(9788111, 3131*3174*3481-100157750) = 9788111
\end{equation}
$$

My current implementation looks like this and it's always giving correct solutions for primitive factors.

n = 9788111

size_x = 1
size_y = 1
for smooth_nr in sieved_nrs:
    size_x *= smooth_nr
    size_x %= n  // cut off

    size_y *= smooth_nr * smooth_nr - n  // equation x^2 - n // can't reduce

size_y = sqrt(size_y)
size_y = size_y % N

gcd(n, size_x - size_y)  // will yield a solution

But now when it comes to non-primitive solutions this algorithm will fail. For example one factor is:

$$
\begin{equation}
 3129^2 * 3313^2 * 3449^2 * 4426^2*4651^2 \equiv (2^2*3*5*7^2*11*17*23^2*31^2*47)^2 = 13136082114540^2
  \end{equation}
$$

$$
\begin{equation}
gcd(9788111, 3129*3313*3449*4426*4651 - 13136082114540) = 2741
  \end{equation}
$$

The problem right now is that the implementation will not work only for both congruences that will lead to factors. I've tried it manually several times and the square root was always wrong, using python it returned a floating point value.

So my question is: How can I modify the factorization step in order to yield the correct solution? Can you see any mistakes made here?

Thank you very much!


texts:
The definition of Public Key Encryption(PKE) say that:

  A PKE scheme is a triple of probabilistic polynomial time algorithm (PPT) (Gen,Enc,Dec).

The definition of PPT say:

  In complexity theory, PP is the class of decision problems solvable by a probabilistic Turing machine in polynomial time, with an error probability of less than 1/2 for all instances.

Let "Find a pair key $(pk,sk)$ (public and private key)" be the problem related with the first algorithm (Gen). In the McEliece scheme, what is a example of error of any instance of the algorithm Gen? Which will be a response "No" and What is a difference between the response "No" and the error response of the algorithm Gen?


texts: What is difference between Cryptographic Transformation, Encryption and Hash?

texts:
I read in a book that: let $f(K,R)$ is cryptographic transformation of $R$ using $K$, $K\{R\}$ means $R$ is encrypted using $K$ and $h\{R\}$ is the hash of $R$ and then the example follows.

I want to know what is difference between cryptographic transformation of $R$ and encryption of $R$ using the same key? Aren't they same thing?


texts: Is a continuous stream of encrypted data embedded in garbage more or less secure than only encrypting the data?

texts:
Consider a communication channel that needs to be secure (Encryption can not use full "volume" encryption, since future messages are not known). Would it be better to

only transmit encrypted messages and remain silent the rest of the time (therefore letting eavesdroppers know when a message is passed),
or sending encrypted pseudo-random data (or almost-meaningful garbage messages) during the remaining time - yielding a continuously encrypted stream which on the one hand hides the information of message transmission times, but otherwise adds the risk of a Known-plaintext attack should the garbage-generator (or the way separating actual message) be predicted.

Does the answer also depend on whether the messages shall be secure "forever" or if it is sufficient to maintain secrecy for a limited amount of time?


texts: How to decide whether to use digital signature (RSA) or HMAC

texts:
I found multiple posts regarding the differences between HMAC and RSA. Why should I prefer one or the other?

These are some examples:

HMAC SHA256 vs RSA SHA256 - which one to use

What are the different use cases between an HMAC and digital signature?

I am designing an SSO (single sign on) scheme to enable registration from one entity to a third party.

From my perspective HMAC should be used as we only want to check that the first entity is a known one. Furthermore HMAC can be faster than RSA (openssl speed hmac rsa gives 1 magnitude difference).

On the other hand, would it be better to use digital signatures to avoid risk case either of the two sides of the system is breached?

I have tried to look on many other schemes for similar use cases and it seems like almost everyone uses HMAC-SHA256. I am not sure if this risk is something should be considered as I couldn't find any crypto notes regarding this matter.


texts: What does it mean when two encrypted files, encrypted with the same method but with different keys, when xor'd together, produce a repeating pattern?

texts:
Let's say I have fileA and fileB, both encrypted somehow, but in the same method with different keys.
If I xor them together, they will make a repeating pattern of 32 bytes length.
What does that say about the repeating pattern, the encryption pattern, and the likelihood of the unencrypted files to be identical?
Is there any way to extract the keys used to encrypt them?

Is there a way, other than to open up Ollydbg and try to reverse engineer the decryption procedure?
The program contacts a server, sends a certain unique code, and the server replies back with an md5 hash.  Then the server sends back the encrypted file, which is easily decrypted by the program.  I want to reverse engineer this program and encryption method.
This is not a homework question, this is a real situation that is tormenting me.
The decrypted plaintext is either Lua source or Lua VM bytecode, with a small possibility of being XML.
Edit:  I now realize that the repeating sequence is probably two different MD5 hashes XOR'd with each other.  Is there a method to analyze and try to extract the individual MD5 hashes?


texts: Unable to determine plaintext from ciphertext

texts:
Given the letter-number cipher: a=00, b=01, c=02, etc., encrypt the word 'hi' and decrypt its ciphertext using RSA. The public key is (5,35) and the private key is (29,35).

I know that 'hi' is represented numerically as 0708, and encrypting it using  (0708^5)mod35 gives 8 as the answer. My instructor then said that I have to pad the result with 3 leading zeroes to get a four digit value (0008) which represents the ciphertext 'ai'.

I find it hard to decrypt it, as (0008^29)mod35 gives 8 as the answer, and I don't see how I can manipulate this result to get a value that gives me the original plaintext.

Can you please point out where I went wrong or what I'm failing to understand?


texts: Stream slicing operation in block cipher and side-channel attack

texts:
My symmetric block cipher works kind of like a stream cipher, but it works on $128$-bit blocks. It generates a $128$-bit block in every round. And at the end of the round, I have to slice it into two blocks and add them together. I mean after each round we take first $a$ bits and second $b$ bits of $128$-bit block and then compute $b+a$. $a$ is equal to $0$ to $127$, it is computed from the key schedule and should be indistinguishable from random. But such slicing can be attacked by the side-channel attack. Attacker can find $a_{0}$, $a_{1}$, $a_{2}$ and so on for every round.
But my cipher works like a stream cipher. That means it computes bit by bit in steps and then combines them into a block. Normally I'm making $128$-bit block with this, for $i$ in the range $0-127$:
$ct=0$
$ct=ct+bitv$
$bitv$ is a bit value $0$ or $1$ and it comes from cipher function. We are just making some binary string/block here. My idea is to not slicing block in the end but first compute first $a$ bits like a string for $i$ in the range $0-a$, where $a$ is some indistinguishable from a random number from the key schedule:

$a=a+btiv$

and then compute the rest of the string for $i$ in range $a+1-127$ as:

$ct = ct + bitv + a$

Anyway, we still have to make for example two loops "for". First for $i$ in range $0-a$ and second in range $a+1-127$ inside the round. Is it possible to attack it by the side-channel attack? Can the attacker detect when the first loop will end and the second will start and then find $a$?


texts: How secure would a hash function be which appends an extra block of 16 zeroed out bytes to the end of the message and then AES-encrypts it with a well-known password (say the first 128 bits of pi) using cipher-block-chaining and then XORs all the encrypted blocks together?


texts: Does lagrange interpolation work with points in an elliptic curve?

texts:
Defining the lagrange interpolation for $x=0$ as $\mathcal{L} = \sum_{i=1}^{t+1} y_{i} \cdot l_{i}$ with $l_{i}$ as the lagrange basis polynomials. Does this hold if we apply the elliptic curve generator for each share $y_{i} \times G \rightarrow Y_{i}$ ?

Defining the elliptic curve version as $\mathcal{L}_{G} = \sum_{i=1}^{t+1} Y_{i} \times l_{i}$
Using a set of shares for the secret $\alpha$ as $S_{\alpha} = \{i \in [1, t + 1] : (i, y_{i})\}$ and elliptic curve point shares as $P_{\alpha} = \{i \in [1, t + 1] : (i, y_{i} \times G)\}$

I expect $\mathcal{L}(S_{\alpha}) \times G = \mathcal{L}_{G}(P_{\alpha}) = \alpha \times G$ to be the same, as also any homomorphic properties to hold.

As far as I know, I haven't seen anyone formulating this or use it in practice in any existing implementation. But the math seems correct. I just don't want to start implementing it without being sure that it works.


texts: How to calculate the key size of my cryptographic system

texts:
I have a 'for fun' project, which is a pure software based redesign of the Enigma I.  I'd like to compute the key length of my design, but I need some help with that.

I have a write-up here (see section 1), but in summary:

Conceptually it's a rotor based system, that can take any number of rotors (i.e. as set by the operator).
Rotor components: stator (input/output), N number of rotors, stator (input/output). Unlike Enigma I, it has no reflector and data can be enciphered in either direction.
Rotor supports 94 unique characters (A-Z, a-z, 0-9 and some special characters).

I've attempted to map out all the variables that I think contribute to the key size:

In summary for those unable to see the image clearly:

Rotors of 94 characters
T - Total possible rotors (permutations of 94): 1.08736615665674E+146
A - rotors available for selection by the operator.  Theoretically T, but practically I have an initial implementation that uses 1147 unique rotors.
N - the number of rotors selected by the operator.  Unlike Enigma I there's no strict limit, and there's the further complication that you can use multiple instances of the same rotor (whether or not that enhances its cryptographic strength, I'm not sure).
O - the order in which the selected rotors can be arranged (including instances of repeated rotors).  I believe the calculation for Enigma I would be 26! × (26! - 1) × (26! - 2) - which takes into account the non-reuse of rotors, which doesn't apply in this case.
R - starting position for rotor Rotation.
D - direction of rotation (forwards or reverse).
F - flow direction through the rotors (left-to-right or right-to-left).

Do you agree those variables all contribute to the key size (they seem to me to all be variables the operator can set, and therefore part of the key)?

Can you give me a hand to compute the key size, or point me in the right direction? I'm afraid math isn't really a strong point of mine.

Update (Re comments to Huberts answer)

Enigma I has a specific number of rotors, which reflects translates both into the key size and the size of the cryptographic problem attackers face.  Calculus doesn't place a limit on the number of rotors used, which I think means that from an attacker's point of view you'd need to consider how many rotors might be being used (i.e.e a range).  Where as, key size is a specific measurement of how big a specific key is.

Update (April 2018)

Project complete.  Info available in the link below, including access to download (win10 only) and user guide.

https://morphological.wordpress.com/projects/enigma-x/


texts: How many operations per key for partial character matching?

texts:
Given a substitution cipher having a key with n alphanumeric characters, if an attacker knows p characters in the key, how many operations per key are required by his computer to compare a permutation with the known characters (and return it if it matches)?

Example:

key is 5 characters that could be A-Z/0-9, so n = 5
attacker has [B * * 3 *], so p = 2


texts: Which is stronger: Threefish 1024-bit, SHACAL-2 512-bit, or AES-256?

texts:
I found some App in the Google Store, and there were features only for the PRO version: Threefish 1024-bit and  SHACAL-2 512-bit. Meantime, AES-256 was available in the free version of app.

So I concluded that the Threefish 1024-bit and SHACAL-2 512-bit algorithms are stronger, and I did a little research and discovered that AES-256 was invented in 2001, Threefish 1024 in 2008, and SHACAL-2 512 was also invented in 2001.

SHACAL-2 512 - I have read that this algorithm was something like "partly hacked for 50%" but for now considered as solid and unhackable.

Threefish 1024-bit - in the opinion of the authors who invented this algorithm it is more effective than AES. And it has a 2.9 security index, while AES has only a 1.7 security index (bigger is better).


texts:
What are the properties a cryptographically secure Elliptic Curve must have?
I have started to create a list and wanted to know if I forgot some important points, and if it is correct so far:

A curve $E$ over a finite field $\mathbb{F}_q$ with $\#E(\mathbb{F}_q)=h\cdot p$ is considered to be cryptographically secure if:

rigidity, as mentioned before the generation of the curve should be documented or random
$p>2^{200}$ so that the ECDLP is hard.
$p\not|(q^k -1)$, for $k<30$ to exclude the possibility of transfers (such as MOV or Frey-Rück)
$p\not=q$, as well to avoid MOV and Frey-Rück and the Anomalous curve Attack
$q$ should be a large prime
the cofactor $h$ should be very small to avoid the Pohlig-Hellman attack
$p$ should be a large prime so that the Pollard-Rho algorithm is inefficient
twist security, check that the twists of the elliptic curve are cryptographically secure as well
little plus: prime in efficient form (such as Merzenne-primes)
Complete addition- and multiplication- formulas to avoid side-channel attacks


texts: salsa20 is invertible, useless in CTR mode?

texts:
I'm reading the salsa20 spec (sorry for the newbie question, i'm really a newbie here). Every paragraph ends with : "this operation is invertible", I suppose the whole salsa20 algorithm is.

If I use salsa20 in bloc cipher CTR mode, this property does not seems mandatory to me, am I right?
As such, any cryptographically-robust hash function (one-way only) could be used for CTR encryption?
Isn't it easier to design a robust hash than a robust cipher?


texts: Content Key Encryption for Multi-User data access

texts:
I recently worked out a concept for a use-case, but I'm not sure if my approach is good enough.
So I would appreciate feedback and things to look out for, as I'm fairly new to this field.

A User can create, change, and access data on a server.
The user can also share it with other users so they have the same rights.
The data on the server needs to be encrypted

My approach:

If a user creates new data, it gets encrypted/decrypted by a new randomly generated symmetric key (AES-256) aka the Content Key of the new data.
For every user password+salt a public and private key (RSA) gets derived:

The password+salt is hashed with PBKDF2('sha256', password, salt, iterations=100000).
This hash is then used as a seed for a random function, to create the public and private RSA keys (1024 bit) for a user. I have written the key generation in python so e and d get calculated in a deterministic way.

For every user that should have access to specific data, the content key is encrypted with the user's public key and saved in the user table/DB.
When a user is logged in, the private key is derived. Then the content keys of a user can be decrypted with the users' private key.
With the decrypted content key, data can be decrypted, accessed.
As the encryption is dependent on user passwords, a strong password policy needs to be enforced.

For me, this approach makes perfect sense for this use-case, but I would love to hear feedback! I already implemented a prototype for this concept in Python  and it works as it should.
This is for a WebApp, so my thought is to handle all of the cryptographic server-side, as client-side code(JS) is too vulnerable for various attacks. Is this approach correct or is there an even better approach?


texts: 2DES vs. two-key triple encryption, with no decryption step

texts:
So studying double encryption (double DES) and understanding why it is subject to a meet-in-the-middle attack, I tried to see if the same attack could be applied to a triple encryption with only two different keys and no decryption operation. I.e.:

$$c=E_{k2}(E_{k1}(E_{k1}(m)))$$

where $c$ is the ciphertext, $m$ the plaintext and ${k_1,k_2}$ the two keys.

It seems the normal way is to have encryption-decryption-encryption with either 2 or 3 different keys. However, with only two keys and three sequential encryptions provide any more security than double DES? I guess you could still apply the meet-in-the-middle attack, since there are intermediary values to which you can apply the same attack, but I'm a bit confused to whether it adds more security than double DES?

I guess it would require $2^{56}$ additional operations to perform a meet-in-the-middle attack since there is an extra step compared to double DES?

Additional question:
Does it matter in which order you apply the keys? I.e. is there a difference between encrypting with $k_2-k_1-_1$ vs. $k_1-k_2-k_1$?

All keys in my question are of size 56-bits.


texts: Birthday-attack calculation in planning password salting strategy

texts:
The book Cryptography Engineering by Fergusun, Schneier, Kohno section 2.7.1 explains Birthday Attacks: "In general, if an element can take on N different values, then you can expect the first collision after choosing about sqrt(N) random elements." This is an approximation.

We are planning to upgrade the way we store password hashes and salts in our database. We need to allow for something on the order of 100 million salts, which is between 26 and 27 bits (two to the 26 or 27 power; I don't know how to format superscripts here). Taking the square that gets me to about 54 bits.

Seven bytes is 56 bits. Assuming that /dev/urandom is sufficiently random (evenly distributed and not predictable), do seven bytes of random salt meet the Birthday Attack criteria?

I realize this is not the only consideration in picking the salt. I'm trying to find out if I'm correctly applying the Birthday Attack theory.

EDIT: The final exercise at the end of the named book chapter asks the same question, which I can now answer confidently!


texts: XTS mode with the tweak key as the sole secret

texts:
The keyspace of XTS is $2^{512}$ due to its use of two distinct keys, and the most effective attack (a meet-in-the-middle attack) brings this down to $2^{384}$. This implies that knowledge of either the main key or the tweak key does not significantly reduce security. What confuses me is the idea that the scheme is still secure even if the main key is known and only the tweak key is kept secret. This idea I got from an answer to another question which notes that an attack revealing the main key but not the tweak key is not a fatal attack, leaving the scheme with a remaining $2^{256}$ keyspace. Looking at a diagram of XEX mode and trying to imagine how it would remain secure when $K_1$ is known, I could not think of any possible way it'd be true:

$K_1$ is the main key and $K_2$ is the tweak key.

XTS mode, sans ciphertext stealing, is defined as:

$$C_{ij} = E_{K_1}(P_{ij} \oplus (E_{K_2}(i) \otimes \alpha^j)) \oplus (E_{K_2}(i) \otimes \alpha^j)$$

Here, $i$ is the sector number and $j$ is the block number within the sector. For the purpose of this question, only one sector matters so $i$ can be considered a constant. Since this makes it such that $E_{K_2}(i)$ is a secret value that never changes, we can define $K^\prime = E_{K_2}(i)$, giving us:

$$C_{j} = E_{K_1}(P_{j} \oplus (K^\prime \otimes \alpha^j)) \oplus (K^\prime \otimes \alpha^j)$$

Because $K_1$ is not secret for our purposes, we can model $E_{K_1}$ as a public PRP $\pi$:

$$C_{j} = \pi(P_{j} \oplus (K^\prime \otimes \alpha^j)) \oplus (K^\prime \otimes \alpha^j)$$

If we simplify things and look at a single $j$, we can say $K^{\prime\prime} = K^\prime \otimes \alpha^j$. Now we have:

$$C = \pi(P \oplus K^{\prime\prime}) \oplus K^{\prime\prime}$$

This can't possibly provide data-at-rest security! It looks to me that knowledge of $K_1$ allows an attacker with a plaintext/ciphertext pair to easily derive $K_2$, which, according to the above-linked answer, is not true. Where is the error in my logic?


texts: Randomness of Decision Learning With Error Problem

texts:
I read the statement of the Decision Learning with error problem is:

distinguish between $(\vec a, \langle \vec a, \vec s \rangle + e)$ from uniformly random samples.

Can anyone explain what does it mean to distinguish $(\vec a, \langle \vec a, \vec s \rangle + e)$ from random samples?  Does it mean subjecting $(\vec a, \langle \vec a, \vec s \rangle + e)$ to some statistical test for randomness?
From what I understand a and e are both randomly sampled from a uniform distribution,  So why would $\langle \vec a, \vec s \rangle + e$ not look like random data?  Is it saying that $\langle \vec a, \vec s \rangle + e$ is a one-way hash function?


texts:
It seems that merkle hash tree (MHT) traversals have been discussed somewhat in the literature, but there does not appear to be much written on inserting, deleting, and updating leaves. Is this lack of material regarding updating MHT's possibly due to the fact that the data (e.g. one time signatures) hashed to form MHT leaves, get typically distributed prior to any possible updates, making it hard to recalculate the verification paths of already distributed leaves?

The trivial insert operation (see Fig 2 below) increases the height of the tree linear in the number of inserts requiring comparatively larger proofs for inserted items, but keeps re-hashing to $\log n$ hashes. The ideal insert operation (see Fig 3 below), keeps optimal height, but depending on where insertion occurs, can require a full tree re-hash.

So, given a merkle tree with the following properties:

$n$ ordered data items hashed only at the leaves, where $n=2^b$ and $b$ is a positive integer
height $h=\log n + 1$,

Is it possible to design efficient algorithms for insertion, deletion and updates of leaves, where

the number of re-hashing operations performed as a result of any operation is within a (smallish) constant factor of $\log n$,
the proofs for any data item remains within a (smallish) constant factor of $\log n + 1$
there are no orphans unless $n$ is odd, in which case the last item is an orphan
the data items remain ordered
the tree is kept as balanced as possible?

If so, what would these algorithms look like?

I am assuming the canonical binary tree flavor of MHT's but if other n-ary versions provide greater flexibility without increasing the proof size too much then I would appreciate reading about them as well.

Example diagrams of the problem are shown below, showing insertions of leaf 0 at the start. Nodes requiring recalculations are in blue.

Fig.1 Original Tree.

Fig. 2 Updated tree resulting from trivial insertion of leaf 0. Blue shaded nodes require re-hashing.

Fig. 3 Updated tree resulting from ideal insertion of leaf 0. Blue shaded nodes require re-hashing.

Please note this question has been updated to make it a little more precise and clearer, whilst preserving the essence of the original question.


texts: Ring Signature - paper/code difference in trying to solve inverse trapdoor function?

texts:
There is a paper on ring signatures and a python implementation of it here.
The Step 4 in the paper describes $y_s = v =C_k,_v(y_1, y_2, ... y_r)$ for all $1 \leq i \leq r$ where $i \neq s$. The next step is to find a unique $x_s$ for the signer's computed $y_s$. This is done by solving $x_s = g_s^{-1}(y_s)$
However, in the python example, to find the unique $x_s$:
s,u = [None]*self.n,random.randint(0,self.q)

s[z] = self.g(v^u,self.k[z].d,self.k[z].n)

It looks like it's generating a random integer $u$ as though $x_s$= $u$, then XOR'ing it with $y_s$ found in step 4, and then it applies the inverse trapdoor function $g^{-1}()$.
Why does the paper's implementation seem different from the one in the code?
That is, why $x_s = g^{-1}(y_s)$  or  $x_s = g^{-1}(y_s \oplus x_s)$ ?


texts: How to determine if ElGamal message was a quadratic residue?

texts:
Consider the following ElGamal encryption (using a generator of $\mathbb Z^*_p$):
Key gen:

find a big prime $p$ and $g$ a generator of $\mathbb Z^*_p$.
choose $a\in \mathbb Z_{p-1}$ randomly and calculate $A\leftarrow g^a \bmod p$
the private key is $(p,g,a)$ and the public key is $(p,g,A)$

Encryption:

choose $b\in \mathbb Z_{p-1}$ randomly and calculate $B\leftarrow g^b \bmod p$
calculate $k \leftarrow A^b \bmod p$ and $C \leftarrow m\cdot k \bmod p$
the ciphertext is $(B,C)$

How can Eve, which has the public key and can see one ciphertext $(B,C)$, determine with prob. at least $3/4$ that the message $m$ is a quadratic residue or not?
I know that with prob. $3/4$, $k$ is quadratic residue because $k=g^{a\,b}$ and $a$ or $b$ are even. I'm having trouble in determining the same thing about $m$.


texts: If we know the pre-shared key of an IPSec tunnel, can PFS help us to stay encrypted?

texts:
Or if the "attacker" has the pre-shared key, then PFS won't help?

Ex.: Heard something about China that it blocks IPSec and only allows it when you give them your pre-shared key, thus they can see the traffic, even if there is PFS implemented on the ex.: IPSec?


texts: Sextic twist of BN pairing parameters vs security

texts:
I've previously asked questions on BN pairing parameters. Here's one more.

In the BN construction, one is working in a subgroup of a curve over an extension field $\mathbf{F}_{p^{12}}$ for some prime $p$. Now, in the scheme I'm looking at, they suggest selecting parameters so that $p$ will end up being a $256$-bit prime. Hence, the total field size will be around $2^{3072}$. The article claims this scheme has security equivalent to RSA 3072-bits.

Now, one can optimize the BN implementation by doing some of the calculations on the  "sextic twist" since it turns out that there exists another curve over $\mathbf{F}_{p^2}$ which has a subgroup isomorphic to the subgroup of the original curve over the full field. I'm wondering, couldn't an attacker also use this to his advantage and to optimize his attack?

After all, the field now only has $p^2$ elements – so I'm wondering of the security really is still $p^{12}$ compared to RSA… or stated differently, why bother with such a high embedding degree when there's an isomorphic group over a much smaller field extension? Or is the attack that implies the equivalence to RSA 3072 bit not possible on the sextic twist, and that's why the full security is retained?


texts: Encrypted cerficiate signature for server certificate and intermediate certificate in packet capture

texts:
If we view the certificate chain using Firefox, we can see the certificate signature of "server certificate" and its "intermediate-CA" right after the "certificate signature algorithm" in the certificate field

In the packet capture, this is returned by the server:

1) server certificate, its public key, its certificate signature algorithm, and followed by some thing encrypted (I guess this is the certificate signature, no?)

2) intermediate CA certificate, its public key, its certificate signature algorithm, and followed by some thing encrypted. (I guess this is the certificate signature too, no? )

My question, which key is used to encrypt the certificate signature of "server certificate" and "intermediate CA"?

If server private key is used to encrypt certificate signature for both server certificate and intermediate CA, then server's public key can be used to decrypt and view their certificate signature

If intermediate CA used its own private key to encrypt the certificate signature, then must use the intermediate CA public key to decrypt and view its certificate signature - however, the server will not have the private key of the intermediate CA, then how can this happen? Unless when configuring the certificate chaining in the server, the imported intermediate CA already has the certificate signature encrypted?

Appreciate if someone can shed some light.


texts: Number message limits of Galois/Counter Mode (GCM) per key

texts:
In
https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-38d.pdf
page 27,
it is said that

...the total number of blocks of plaintext and AAD that are protected by
invocations of the authenticated encryption function during the
lifetime of the key should be limited. A reasonable limit for most
applications would be $2^{64}$...

I could not find any reason for this. What will happen if I encrypt more than $2^{64}$ messages with the following settings

The same key is used
The tag length is 128-bit
IV length is 96-bit
Unique IV is chosen for each message
Each message has less than 2^32 blocks

What is the attack? What is the security level of my setting...


texts: How is a NAND gate constructed from just addition and (mixed) multiplication in a FHE circuit?

texts: From what I've read I know that FHE requires "circuits" to construct functions and gates to operate on the FHE encrypted data. I've also read that these circuits are constructed from just addition, multiplication, and mixed multiplication. How does this work? How, only using those operations, can we construct a NAND gate for example?


texts:
I have a webserver which only supports TLS 1.0 and I am not sure about something: Which is the better cipher in this group when aiming for the best security?

TLS_ECDHE_ECDSA_WITH_AES_256_CBC_SHA (0xc00a)
TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA (0xc014)
TLS_ECDHE_ECDSA_WITH_AES_128_CBC_SHA (0xc009)
TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA (0xc013)
TLS_ECDHE_ECDSA_WITH_RC4_128_SHA (0xc007)
TLS_ECDHE_RSA_WITH_RC4_128_SHA (0xc011)
TLS_ECDHE_ECDSA_WITH_3DES_EDE_CBC_SHA (0xc008)
TLS_ECDHE_RSA_WITH_3DES_EDE_CBC_SHA (0xc012)

I chose only ciphers with ECDHE for Perfect Forward Secrecy. Speed is not very important, for me secure is more important.

These ciphers are used in my Java application for retrieving data from a HTTPS website. My doubt was due to the fact that the CBC Ciphers are vulnerable to BEAST Attacks.


texts: Is a singular LUKS volume with different passwords that unlock different filesystems possible?

texts:
So it's hard to make sense out of the title. Let me elaborate:

In LUKS, you can have multiple passwords that unlock the same volume (due to their "unified key setup" where they have a single master key). But I was wondering if you could have a single LUKS volume with, say, 2 passwords. The first password unlocks your secret data that you don't want your adversary to get. The second password unlocks pseudo-secret data (I.E. something like pornography, which would reasonably want to be hidden, but is not actually what you're trying to hide). This way, if your adversary found the 2nd password, then they'd think "Oh well this is embarrassing, but it's not what I'm looking for" and move on, being completely ignorant to the "shadow volume" of password #1 that really contains the secret data.

The only cryptographic protocol I've seen that exhibits this feature is steganography, specifically the program steghide. With steghide, you can splice secret data into a picture with one password, then also splice another, different piece of secret data into the same picture with a different password. Both pieces of data are accessible and not corrupted if you use the right passwords.

This is what I'm looking for. Is LUKS capable of doing this? If not, what is the closest thing that I could do to imitate this (aside from LUKS nuking, that's not what I'm looking for)?


texts: Number of words in binary linear code starting with zero and unit

texts:
Is it true that in a binary linear code number of words, which start with zero, is always at least as much as words, which start with 1?

I have no idea how to prove or disprove it. Can you give me a hint how to start, please?


texts: I was reading the HORS One-Time-Signature scheme by Reyzin & Rezyin, but I could not understand how they derived their security equation $(rk⁄t)^k$. I understand that the total number of balls is $t$, and each time a signer signs his message, he reveals $k$ different balls. The attacker at this point and after one signatures, he knows $k$ elements (balls). After $r$ signatures, the attacker at most knows $rk$ out of $t$ elements. Then, why it was raised to power of $k$? and why is the security log of this equation?


texts: How to prove that work is done without actually knowing the payload

texts:
Is there a way for an algorithm to run securely on one end, whilst the other end is able to be notified and also verify that it has run and done the work without knowing what the actual payload is?

For example, $A$ provides an algorithm that adds $1$ to any number.

$B$ takes this algorithm and performs it $N$ number of times. $A$ can then verify that $B$ has performed it $N$-times without knowing what $N$ is.


texts:
In some cases (such as XML or JSON files), the bytes being encrypted have very specific semantic requirements, such that a random byte sequence will be rejected with very high probability.

In such circumstances, is it possible to do without an authentication tag, and reject forged messages at a subsequent stage?  This obviously requires that the cipher mode of operation meets certain requirements about non-malleability; to my knowledge XTS mode qualifies.


texts: Non-commutitive and nonassociative algebraic structures in cryptography

texts:
Are there any cryptographic algorithms or primitives that have been developed and studied that make use of non-commutative or non-associative algebraic structures such as quaternion integers or octonion integers? It seems to me that many of these structures can preserve the things that make them useful to cryptography (the trapdoor nature of multiplication for example) while removing some of the tools used to attack it (symmetries exploited in commutativity and associativity).
There are several structures that are non-commutative and non-associative that have many features of unique factorization domains, such as Hurwitz quaternions and the 'Cayley' integers studied by Conway and Smith; It wouldn't surprise me to learn there are other structures that have similar properties that are close enough to the integers we're familiar with yet with broken symmetries that make them more resistant to cryptanalytic attacks.
The most obvious utility I can think of is using quaternion or octonion based unique factorization domains in RSA, but many cryptographic systems that use objects like integers I can see being extended to alternative structures. The downside I can see is that some hidden congruence relations that could be exploited don't exist in the integers. Are there cryptosystems that use such alternatives to the integers?


texts: Is it possible to decide the base of a discrete logarithm?

texts: Given $R$, a prime $p$ and two bases $g_1$ and $g_2$, is it possible to decide if $R = g_1^r$ mod $p$ or $R = g_2^r$ mod $p$ without knowing $r$?


texts: Why this example about pseudorandom generators is performed like that?

texts:
Suppose Alice wishes to authenticate herself to Bob, by proving she knows a secret that they share. With pseudorandom number generators (PRNGs) they could proceed as follows.

They both seed a PRNG with the shared secret $s$.
Bob picks sends Alice some random number $i \in \mathbb{N}$.
Alice proves she knows the share secret by responding with the $i$-th random number generated by the PRNG.

I am wondering why Bob sends a random number $i$ instead of just $1$. Then Alice just sends $G(s)$ (where $G(\cdot)$ is the PRNG) to Bob. Only Alice and Bob should have access to the secret $s$, and hence this should also work. In the above example, Alice and Bob should both have to compute $G(s)$ $i$ times, making it much more inefficient.
Which is the difference between what I am proposing and the original example? Aren't them both equally secure?


texts: Index calculus over elliptic curve over function field

texts:
According to my understanding there are some pretty solid seeming roadblocks to carrying out an index calculus on an elliptic curve over a finite field. The general strategy is to take points over $E(\mathbb{F}_p)$, lift them to points over $E(\mathbb{Q})$, and then hope that the curve over $\mathbb{Q}$ has high rank. The two major obstructions seem to be

It is very hard to find elliptic curves over $\mathbb{Q}$ with high ranks, and
It is highly unlikely to find a reasonable factor basis - that is, a collection of points on the curve with a bounded height.

This approach assumes that we lift the problem to one over the rationals $\mathbb{Q}$. I was wondering if anyone has any idea whether such an algorithm could be carried out by lifting the curve to an elliptic surface, i.e. an elliptic curve over the function field $\mathbb{F}_p(T)$ of some curve? At the very least we seem to know more about how the ranks of these things behave better than in the number field case.

I am not sure what I am asking even makes sense, so an explanation of its nonsense is welcome as well.


texts: AES Encryption With PBKDF2 KDF in pycrypto

texts: I am a bit new to encryption and I've seen a lot of recommendations to use a KDF for encryption and decryption. I'm a bit confused since I've been trying to encrypt the data using PBKDF2 algorithm and salt is generated using get_random_bytes, but when I try to decrypt the data I try to derive a new key using a new salt, this throws off my decryption. When I make the salt something constant for example b'salt' decryption works as expected but if I try to regenerate the salt and then regenerate the key the decryption doesn't work. My question is, should I be using the same salt for key derivation for encryption and decryption? Also if encryption happens on a server and decryption happens on the client, doesn't sending the salt over the network make using a KDF pointless? Where am I going wrong?


texts: Are software solutions such as FHE, PHE, Garbled Circuits used in practice?

texts: Is Fully Homomorphic Encryption or Partially Homomorphic Encryption or Garbled Circuits used in practice? Or is an alternative used instead (I don't mean encryption just for storage here)?


texts:
I try to understand how Complexity of an LSFR calculated.

For example I have a bit sequence 110101 and it's profile 1 1 2 2 3 3.

Is there any easy way in order to produce the profile?


texts:
In the RSA algorithm, if an attacker wants to get $d$, the attacker does this simply by encrypting random messages $m < N$.

If the attacker ﬁnds a message $m_1$ that the attacker can not encrypt since $\gcd(N ,m_1) \neq 1$, does this help the attacker in any way in any way?

I don't know why the $\gcd(m,N)$ has to be $1$. What happens if $\gcd(m,N) \neq 1$?


texts: Is it true for Java that the transformation mode and padding is ignored when using RSA?

texts:
Consider GregS's comment to this question (more specific to bouncycastle's provider implementation):

https://stackoverflow.com/questions/11717646/bouncycastle-rsa-key-size-and-padding

  The mode, ECB in this case, is ignored for RSA.Use PKCSPadding. The
  max amount of data you can encrypt is the size of the modulus in bytes
  minus 11.

I've read several articles that seem to state similar views, including this one:

http://armoredbarista.blogspot.com/2012/09/rsaecb-how-block-operation-modes-and.html

Although that article appears to make the case that it is only ignored when the data exceeds the size of the moduli.

Basically I have a small amount of data to encrypt (a username and password), a private key with a 2048 bit key length, and I'm using the RSA/ECB/PKCS1Padding cipher transformation for encryption. Is this considered "textbook" or "plain" RSA in Java?

I believe I am using a secure approach for our needs, but I need to be sure.


texts: What are sources for the performance difference in asymmetric and symmetric encryption?

texts:
I see the claim (which I'm not doubting) that encrypting data using asymmetric algorithms is slower than symmetric algorithms.

But I never see citation on these claims, not here, on wikipedia or even in papers.

It seems in academic papers RSA and the like are for signatures and are never considered when comparing encryption algorithms.

Is there a more comprehensive review I'm missing?


texts:
As we can generate a permuted sequence using KEY in KSA (Key Scheduling Algo) of RC4. Is there any way to check the randomness of the permuted sequence?
Let say I created 100 different permuted sequences of range 256 {0,1,,2,...255} using 100 different keys. Now, I need to check either all 100 sequences have any relation with each other or they are random.
The NIST statistical test suit is for bit-stream not for integers as far as I know. Please, correct me if I am wrong.

EDITED:
Let say I have a sequence: {1,2,3,4,5,6,7,8,9,10}
I use KSA to get the permuted version as:
Let say key="pass123" it gives -> {3,7,2,9,1,4,6,10,8,5}
Let say another key="test123" gives -> {9,2,6,1,5,8,3,10,7,4}
and similarly another key gives another such sequence and so on...
Now I need to check either there are some relations between the generated seemingly random sequences or not. And also I need another algo which can generate such like random sequences.
Hopefully the query is much clear now!!


texts: Why do a pair of interactive machines have a common input?

texts:
I know that an interactive proof system $(P,V)$ is a pair of interactive machines for a language $L$ if $V$ is polynomial-time and the following two conditions hold:

1) Completeness: For every $x \in L$,
$$\Pr [\langle P,V \rangle (x) = 1] \geq \frac{2}{3}$$

2) Soundness: For every $x \not\in L$ and every interactive machine $B$,
$$\Pr [\langle B,V \rangle (x) = 1] \leq \frac{1}{3}$$

Actually, in an interactive proof system $(P,V)$ for language $L$, $P$ proves the fact whether $x \in L$ to $V$.

However, for a general pair of interactive machines, what is the meaning of the common input? Can we construct a system $\langle A,B \rangle$ such that $A$ wants to send $x$ to $B$ and prove that $x$ is not malicious before sending it. Or can we construct other communication systems instead of a proof system?


texts: What is 'order' in More Modular Exponential (MODP) Diffie-Hellman groups?

texts:
I am investigating on source code of a program called hostapd. And I am looking into Diffii-Hellman part of it.

/* RFC 3526, 3. Group 14 - 2048 Bit MODP
 * Generator: 2
 * Prime: 2^2048 - 2^1984 - 1 + 2^64 * { [2^1918 pi] + 124476 }
 */
static const u8 dh_group14_generator[1] = { 0x02 };
static const u8 dh_group14_prime[256] = {
  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
  ...
}; /* too long */
static const u8 dh_group14_order[256] = {
  0x7F, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
  ...
}; /* too long */

I understand that dh_group14_generator is a generator and dh_group14_prime is a prime for 2048 bit MODP from RFC 3526.

However, I can't find any clue of dh_group14_order. What does it stand for?


texts: Schnorr groups allowing fast modular reduction, vs GNFS

texts:
I'm looking for Schnorr groups allowing fast modular reduction. Say, using the notation in DSA, with 256-bit prime $q$ and 3072-bit prime $p$, and $p\equiv1\pmod q$.
Are there standards, RFC, or other references about this?
I'm considering choosing $p$ with all bits at $1$, except for a relatively short segment not too far from the top bits. That allows very fast Montgomery modular reduction, which can next to halve the computational effort compared to arbitrary $p$. Would that make GNFS faster, by allowing selection of a better polynomial?
Any reason not to use $g=2^{(p-1)/q}$, which seems a most natural generator?
A rather extreme example of what I have in mind:
$$\begin{align}
q&=2^{256}-2^{194}-1\\
p&=2^{3072}-1\\&\quad-2^{2745}\,\mathtt{2219c36803ffffff6352c900000000006008ef007fffffffbcc79fd201_h}\\
\end{align}$$
q=fffffffffffffffbffffffffffffffffffffffffffffffffffffffffffffffff
p=fffffffffffffffffe000000443386d007fffffec6a5920000000000c011de00ffffffff798f3fa401ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff

where $q$ is the smallest $256$-bit prime with a single $0$ bit; $2745$ is chosen to minimize the bit size of the $230$-bit constant defining $p$, happens to put that term in the high-order bits of $p$, and (due to the special form of $q$) also creates long sequences of $0$ and $1$ in that segment of $p$.
Update: Daniel Shiu's answer shows that indeed, the above allows a sizable speedup of GNFS. Let's forget about it. What about taking $p=2^{3072}-1-c\,2^{3072-\ell}$ where $c$ is a $\ell-1$-bit nothing-up-my-sleeves constant, and some larger $\ell>230$? Up to $\ell$ about $1024$ (one third the bit size of $p$), we still save most of the modular reduction effort.


texts: Please punch holes in this authentication scheme

texts:
Folks, I am undertaking a crypto course in Uni. Our professor asked us to try and design some authentication schemes which are resistant to active attacks. This was just a in class exercise to get us interested in the topic. It did the trick, I have been trying to come up with something using what we have learned so far.

Here is a authentication scheme I developed :

Please punch holes through it and tell me what attacks are these vulnerable to?

P.S - Notation explanation : Ka+(Rb) denotes the encrypted text that was generated by encrypting the nonce generated by Bob using Alice's public key. This text is decrypted by Alice using her private key Ka- and gets Rb. Alice then encrypts Rb with her private key and sends it to bob. Who then uses Alice's public key to decrypt the message and get text. If this text is same as Rb then alice Has been authenticated to Bob

Similarly Ka-(Rb) denotes encrypted text obtained by encrypting nonce generated by Bob using alice's private key

P.P.S - Before you guys suggest Man-In_middle attack : Here is why I think it wont work :


texts: How well does breaking multiple DH key exchanges over the same group scale?

texts:
Suppose you are running a server with the Diffie-Hellman parameters (so the group G and generator g) generated once. There are many connections made to the server, all using TLS with an DHE cipher suite.

Now, assume an adversary captures all connections and is able to break one key exchange (find the master key). How much harder would it be for that adversary to break 2, 3, ... $n$ of the key exchanges instead?

Of course this will depend on the attack against DH that is used. In a naive brute force attack the adversary starts generating $g^0, g^1, g^2, \dots$ until they find either the exponent used by the server or the exponent used by the client.

Something like:

a := g
e := 1
while e < n:
    a := a ∙ g in the group G
    e := e + 1
    if a == client_key or a == server_key:
        return e

This contains one modular multiplication step (multiply previous value by $g$) and two comparisons. I would expect the comparisons to be very cheap compared to the multiplications, therefore doing this for 2 key exchanges instead of one should only have a small impact on the time required.

Does the same apply to other attacks on DH?

Background:

I think it's a common misconception that to compromise $n$ connections without forward-secrecy, an adversary only needs to break one key and with forward-secrecy and attacker would need to break $n$ keys, and therefore would need to spend $n$ times as much resources to do so. Forward-secrecy only implies that adversaries can't “cheat” the math by stealing the key, it doesn't necessarily mean that breaking multiple key exchanges is more difficult than breaking one.


texts: Security Proof, Sequence of games and birthday paradox

texts:
The sequence of games security proof approach is very confusing. For example, I am trying to understand it in the following paper
https://www.dropbox.com/s/dhsgsognxviwacv/Provably%20Secure%20Authenticated%20Key%20Agreement%20Scheme%20for%20Smart%20Grid.pdf?dl=0
I understand there are two entities in the game, a challenger and an adversary. At the end of the game, the challenger flips a coin. If b=0, the challenger outputs the session key; otherwise, it outputs a random number with the same length. The adversary wins the game if he can guess whether the challenger's output is the session key or random number. I also understand the oracle query represents an actual attack. For example, if the adversary queries a Corrupt(U) oracle, it means that the adversary was able to access the long-term key of the instance U.
However,

what is actually the job of the simulator?
what is the difference between the transcript and an adversary query.
why in this particular paper, in game GM_3, they care about collision between the transcript and hash quires?

I would really appreciate if someone can help me.


texts: Why is symmetric lightweight crypto only about block ciphers and not about stream ciphers?

texts:
Why is symmetric lightweight cryptography only about block ciphers and not about stream ciphers?
AFAIK stream cipher implementations cost at least three times less than block cipher ones?


texts: How to construct a set in which the elements in $\mathbb{Z}[x]/(x^n+1)$ and their differences are invertible and with coefficients in $\{-1,0,1\}$?

texts:
I know that in IACR - Better Zero-Knowledge Proofs for Lattice Encryption
and Their Application to Group Signatures it constructs such a challenge set: {$ x^i $}. But the inverse of the difference of the elements in it should multiply $2$, which is not good enough. How to construct a good set (say, just exactly fits the requirement)?


texts: Can multi-encrypted file be decrypted with one password only?

texts:
Let's say I have a single file I want to encrypt with AES and I encrypt it twice (first encrypt the unencrypted file, then encrypt the encrypted file again). The first time I use password 'ABC', the second time I use 'DEF'. So in theory the attacker would have to decrypt it first by providing 'ABC' as password which would result in still encrypted garbage data - so they would provide 'DEF' and then they succeed. I wonder, though, if they may decrypt my file with only one password - perhaps there exists a password that is neither 'ABC' nor 'DEF' that successfully decrypts the file and they accidentally succeed with this password when bruteforcing.

In other words:

ABC -> DEF -> plain file

XYZ (exists or not?) -> plain file

Does the existence of 'XYZ' depends on the algorithm(s) used and will it always/never/sometimes exist?


texts:
I hope somebody can help me understand the design criterias for AES. Therefore, I would be really thankful if somebody could explain "non-linearity" in this context.

A criteria for the s-box in AES is non-linearity, where the maximum input-output correlation amplitude must be as small as possible. Why is a look-up table non-linear?

The maximum difference propagation probability must be as small as possible. This means to get closer to a uniform distribution?

MixColumns offers linearity - because it is a function which transforms values in a deterministic way?


texts: Magic Number to calculate number of rounds for M-R in FIPS 186-4

texts:
In Fips 186-4, there is an algorithm in Appendix F (at page 117 in my copy of the 2013 version) to calculate the number of rounds of the Miller-Rabin primality test to random bases.

Does anybody know where the magic number 2.00743 comes from or do I really have to work through the paper Average Case Error Estimates for the Strong Probable Prime Test by I. Damgard et. al


texts:
I have read about block ciphers, but I do not understand the topic completely.

Is a block cipher a way to send data or a way to encrypt data?

How is the data divided into multiply blocks before it is sent? Is the data partitioned before the encryption process or afterwards?

How long are the blocks? Can I choose any block size?


texts: Simplicity and precision in cryptography papers

texts:
I know a PhD student who recently had his paper on applied cryptography rejected because one the reviewers claimed that it was "the solution was too simple and the notation used was more than necessary". It was accepted by the second reviewer. However, both the student's supervisors thought it was a very well-written paper worthy of being accepted at the journal it was submitted to.

I have always thought that especially in cryptography, schemes should be easy to understand and use, and their unbreakability should rely on a given primitive rather than the complexity of the scheme. It should be noted that the reviewer that rejected it admitted the scheme was sound, applicable to a current area of interest, solved a problem in the area, and advanced knowledge in the area as well.

So why is it that with cryptography, where it makes sense to make schemes easy to understand (but built correctly around a primitive that is hard to break) and at the same time described precisely enough to analyse accurately, that people want something more complicated instead?


texts:
My limitation in my security protocol is that I want my RNG as CSPRNG and I also want it to be super fast.
If I use Salsa20 or ChaCha or AES counter mode, I don't get the desired speed. I want my PRNG to work at the speed of 100 Gbps or more.
Morever, I need to be cryptographically secured.
Any suggestions regarding that? Do there exist such CSPRNG that can give me output stream at the speed of 100Gbps or above? Or in other words that can provide bit streams with a speed of 10^-11 bits per sec?
P.S: I don't care about the system requiremt, the platform could be FPGA, GPU etc, I just need some numbers to compare with and to know that with any kind of feasible platform (not super computers) can I achieve the target of 100Gbps in any of the CSPRNG?


texts: How can I benchmark RSA operations on my computer? I want to know about 4096-bit long keys on general computers. How many encryptions and decryptions are possible per second? All benchmarks I found only show 1024- and 2048-bit keys.


texts: Can root and intermediate CAs use different asymmetric ciphers and key sizes?

texts: For example, could a root CA use RSA-4096, one intermediate CA use RSA-2048, and another use ECDSA-256 (DH19)?


texts: Security requirements for EC Diffie Hellman implementation

texts:
I'm working on a crypto library to be used in a firmware product.
Beside other things we need key agreement based on Diffie Hellman.

Since resources are very limited we use a crypto accelerator on the MCU for which a low level library exists, allowing beside other things to make elementary calculations on elliptic curves over $GF(p)$ and $GF(2^p)$.

Now I tried Diffie Hellman and tested the results against various test vectors. It works fine.

But, of course, I know that this self-made approach can be dangerous, when the detailed implementation is open for attacks, whatsoever kind of.

So the question: What requirements must be considered additionally to plain algorithms in order to make the outcome a "secure" solution?

To make a statement to the answers below:

1) We must use P-256 (it's not a choice)

2) What do you mean with large private multiplier? In my implemantation the private key is taken randomly between $ 1 \ldots 2^{256}$ (32 Bytes) and then reduced to modulo group order. Is this acceptable?

3) I use a hardware RNG (TRNG).

4) We must use KDF specified within NIST 800-56A Rev2

5) The other side is authenticated by ECDSA based on a certifcate

6)

  side channel resistance is a hairy issue

I have to larn about what this is

7)

  If you only have the really basic operations: make sure your scalar
  multiplication is constant-time.

Why is this required?


texts: Given just the hash of a file, can I verify that the file contains a specific data block?

texts:
Imagine I only have the hash of a file which we can call hash(file). Then a user sends me a data block (or section) of the same file, which we can call section1(file). Is there a way to verify that such section belongs to the file, given only the hash of it?

I was thinking of constructing a Merkle tree. So the hash(file) would actually by the Merkle root. However, to verify that a section belongs to the file I would need the entire Merkle tree (not just a single hash).

Any thoughts about proving that a file contains a specific data block? It doesn't matter which hashing methodology I use as long as I can verify it with little information.


texts:
What is meant by a 'tag' with regards to transmitting a MAC?

Are there multiple meanings within cryptography?

Update - take this for example:

$Bob \to Alice \Rightarrow m\ ||\ h(m, ``secretTag")$


texts:
I have a question regarding the theoretic definition of Pseudorandom Generators. In Katz & Lindell's textbook (2nd edition), Definition 3.14 (p. 62), it is defined as follows:

DEFINITION 3.14. Let $\ell$ be a polynomial and let $G$ be a deterministic polynomial-time algorithms such that for any $n$ and any input $ \in \{0,1\}^n$, the result $G(s)$ is a string of length $\ell(n)$. We say that $G$ is a pseudorandom generator if the following conditions hold:

(Expansion:) For every $n$ it holds that $\ell(n) > n$.
(Pseudorandomness:) For any PPT algorithm $D$, there is a negligible function $\mathsf{negl}$ such that $$\bigg|\mathrm{Pr}\big[D(G(s)) = 1\big] - \mathrm{Pr}\big[D(r) = 1\big]\bigg| ≤ \mathsf{negl}(n)$$ where thre first probability is taken over uniform choice of $s \in \{0,1\}^n$ and the randomness of $D$, and the second probability is taken over uniform choice of $r \in \{0,1\}^{\ell(n)}$ and the randomness of $D$.

My Question: Why is Expansion necessary? I mainly don't understand why it is not defined as $l(n) \geq n$, therefore why is $l(n) = n$ not included?


texts: How to compare performances of lattice-based and pairing-based IBE schemes

texts:
I try to compare the performances (cost of Enc, Dec, ... size of keys, ciphertexts, ...) of IBE schemes using lattices (LWE hardness assumption) or pairing (Diffie-Hellman hardness assumption).

I've observed that performances of lattice-based schemes are often expressed in terms of $n$ (the dimension of the lattice) whereas pairing problems use the bit size $|G|$ of the elements of the underlying group(s) $G$ (and the cost of basic operations such as exponentiation or pairing).

Are these 2 quantities "equivalent"? For instance, is it relevant to say:

keys of length $O(n)$ (in a lattice scheme) and $O(|G|)$ (in a pairing scheme) will have roughly the same size in practice
encryption of cost $O(n^2)$ (in a lattice scheme) is quicker than $O(|G|^3)$ (in a pairing scheme)
...


texts: Combining a keystream generator with a block cipher

texts:
I understand that:

A stream cipher's security is diluted if the same key is used more than once. This is fixed by using an additional initialization vector in the keystream's computation.
A block cipher run in the most simple way, electronic codebook mode, has negligible security due to pattern preservation. This is avoided by using cipher-block chaining or another mode of operation.

Consider that using a keystream generator like in stream ciphers to produce a string of keys for encipher individual blocks of a message with a block cipher:

Does not fall prey to the problems that reusing a key plagues stream ciphers with because of the avalanche effect present in block ciphers.
Does away with the need to use more complicated modes of operations in a block cipher due to each block being encrypted with a different key.

Is this analysis correct? Are there implementations like this that are already out there?


texts: Proof of the Diffie-Hellman Key Exchange

texts:
Could someone please provide the math proof;
$$ ((g^a)\bmod p)^b \bmod p = ((g^b)\bmod p)^a \bmod p $$


texts: Decrypting a vigenere cipher with a reused one-time pad

texts:
I understand that when a plaintext is encrypted with a key of the same length, it is referred to as a one-time pad. Now when this key is reused to encrypt another plaintext, there is potential for decryption of the original ciphertexts.

Following on from the question asked here, Taking advantage of one-time pad key reuse?, the ciphertexts there were retrieved via a Vernam cipher:-

$ciphertext = plaintext \oplus key$

which gave rise to the following relationship between the two:-

$ciphertext_1 \oplus ciphertext_2 = plaintext_1 \oplus plaintext_2$

If instead of a Vernam cipher the encryption is carried out via a Vigenere cipher, where I have two plaintexts and a key, all three of which are the same length - is it possible to draw any relationships like the one above, from the resulting ciphertexts, when I do not know what the plaintexts and key were?


texts: Roots of polynomial in Shamir secret sharing

texts:
I need to know whether one can obtain any roots of the polynomial in Shamir secret sharing if he possesses less than threshold shares.

For instance in (t,n) if he has t-1 shares can he obtain any roots of the original polynomial?

** Here we assume that the polynomial has some roots.


texts: Cryptographic random numbers for key generation

texts:
I am trying to understand how a cryptographic library works (for example, one that provides assymetric encryption such as RSA), but I'm running into a few problems about the key-generation. There are a lot of questions regarding the generation of random primes, but I'm interested in the generation of a random number. There seem to be some official guidelines by the government (for example, NIST FIPS 186-4 (PDF) is referred to in a couple of other answers to questions about random prime generation) for the generation of keys for certain protocols, but they are not an easy read and I don't think they answer my questions.

I think I understand the basic principles:
Entropy is gathered by the operating system or a daemon to provided a small amount of unpredictable data that is used as a seed for a cryptographically secure pseudo-random number generator (CSPRNG). The CSPRNG generates the random numbers that are used to generate random primes (either a probable or provable prime).

What is a good CSPRNG? I couldn't find the algorithm that OpenSSL uses (it's very well possible that there are multiple). Wikipedia lists a bunch, but doesn't provide sufficient information on implementation and performance.

Also, are there any additional constraints on the prime or prime pair that is generated? I vaguely remember reading something about prime products of a certain form that are no good for use in cryptographic keys (because they are easy to factor with some tricks).


texts: Simply using password as a third "private key" for PAKE

texts:
I'm reading through the development of PAKE protocols, starting with EKE and SPEKE, their potential pitfalls, and what motivates their protocol choices. And I've been wondering, what is wrong with the following (very simple) modification to classic DH to make that PAKE:

Let Alice and Bob have a shared secret s = hash(password). Alice and Bob pick private keys a, b. Starting with DH, Alice and Bob compute their public keys as

$A = g^{as}\mod p$

$B = g^{bs}\mod p$

After they exchange public keys, they can calculate their shared key as
$K = g^{abs}\mod p$

What is wrong with this simple scheme? I'm guessing it somehow allows an offline dictionary attack on s. I know s has no low entropy, but I'm still not seeing how.


texts: Is this hand cipher any more secure than the Vigenère cipher?

texts:
I know that inventing one's one crypto always sucks, but the problem is that hand ciphers are usually

very insecure
very slow.

This is an attempt to make a relatively secure, keyable, and modular multi-round cipher by hand.

In each round of encryption the following two steps are done:

The text is permuted by concatenating the reverse of the even-numbered characters to the odd-numbered characters. This is equivalent to writing the first char in the first place, the second in the last place, the third in the second place, the fourth in the second-to-last place, etc and is very fast to do by hand, and can be mentally reversed simply by "zig-zagging" the eyes when reading. (12345 -> 13542)

   T H I S X I S X S E C R E T
=> T I X S S C E T R E X I S H

The text is then added$\mod 26$ by repeating a series of numbers, i.e. the key. The numbers are from 0 to 10 so that they are easy to write underneath the letters and also because encryption can be done in head without memorizing, say, X is the 24th number of the alphabet. I'm especially concerned whether limiting this to numbers from 0 to 10 rather than from 0 to 25 seriously cripples security. (Obviously the digits of $\pi$ is a bad choice for a key but this is just an example)

   T I X S S C E T R E X I S H
   3 1 4 1 5 9 2 6 5 3 5 8 9 7
=> W J A T X J G Z W H C Q B O

This encryption process is continued for 5 to 10 rounds. The reason for the permutation phase is to break patterns that weaken the Vignère cipher.

I have observed the weakness that the first letter is never permuted to another place; thus known-plaintext attacks can easily trivially find the first number of the keystream given the number of rounds. Other than that I haven't found any very serious flaws.

Does this cipher system have any mathematical advantage over older (but slower to compute!) ones such as Vigenère or Playfair?


texts: Is it required to use a random IV for AES-CBC with random key per message?

texts:
I'm developing a program to encrypt and decrypt a file with AES-256/CBC in Java. And I want it to be safe enough. In my case, I generated random AES key for each file to encrypt and decrypt them.

My question is if it is necessary to generate a random IV for encrypt/decrypt or it is already secure enough with a random AES key and fixed IV.


texts: I was reading this paper https://eprint.iacr.org/2014/816.pdf "Bootstratpping in less than one second" but I didn't understand it throughly. What's the point to build a cheap NAND gate ? Maybe to build cheaper AND and OR gates based on this NAND gate and then follow the approach of Regev's type cryptosystems? Or maybe to use the technique from this paper and build your own cheap AND and OR gates ?


texts: How do we arrive to the equation for solving D in RSA?

texts: We have been shown that DE is congruent to 1 mod phi(n). How do we arrive to the real equation for figuring out d that is d = e^-1 mod phi(n). I want to know the entire process. I am just curious, spending the night studying the workings of the RSA.


texts: What is the canonical way of creating Merkle tree branches?

texts:
I'm currently looking into creating some compact Merkle tree branches to prove that a given hash was included in a given Merkle root. My initial thought was to list the leaf, the Merkle root and all of the hashes that the given leaf was combined with to make the Merkle root.

So in this example:

I would state

Leaf:  12c5
Root:  2f9c
Nodes: [d187, a8b5, 1328, d063]

However, since the order of nodes matter for creating the Merkle root, I would also need to list whether the node was on the left or right side.

I'm wondering if is there a canonical way of listing this information to create the Merkle branches?


texts: A one way Function provably reversible at N applications with the same seed?

texts:
I'm looking for a function that is generally one way from some secret $F(s, A) \rightarrow Y$, where $A$ is known, $Y$ is produced (also known), and $s$ is kept secret. But whose repeated application results in the function being reversible (to determine $s$) at some step $F_n$.

Edit: $A[1,2 \dots n]$ is a set of numbers not known in advance (prior to each successive application of $F$), but of a particular type, say the first 16 bytes of a SHA-256.

It is essential that it can be proven that the function is not reversible at $n-1$ (or that the work necessary to reverse at $n-1$ is very high) and sufficiently easy to reverse at $n$ ($n+1$ etc.), and that this is provable for any s belonging to a certain group.

$F(s, A_1) \rightarrow Y_1\\
F(s, A_2) \rightarrow Y_2 \\
\dots \\
F(s, A_3) \rightarrow Y_n$

Would greatly appreciate a pointer in the right direction (what functions to look at, or even some reading on the subject), thanks.


texts: Resynchronizing brute-force attack against stream ciphers

texts:
There is a stream cipher without any known cryptographic weaknesses. The attacker knows parts of the key so she can reduce the key-space to a size that can be practically brute-forced.

However the attacker only accesses some (continuous) parts of the ciphertext and she doesn't know how many bits she missed (the attacker is out of sync). She does know the general structure of the underlying plaintext and can check if a part of the keystream decrypts a partial ciphertext correctly. The attacker can also match known ciphertext-plaintext pairs, so parts of the keystream is also known to her.

There are no encrypting or decrypting oracles to use.

My understanding is that the attacker should generate a (theoretically) infinite long keystream and check if any parts match the ciphertext parts for every key candidate. This is of course impractical even for a couple of possible keys.

Is there a practical strategy for the attacker to brute-force the correct key and "synchronize" with the cipher stream?

What kind of cryptographic weakness of the cipher would make the task easier?

EDITED: Added some clarifications based on the comments of @fgrieu.


texts: how many blocks are encrypted at a time in DES Algorithm?

texts: I know that block ciphers encrypts data in the shape of specified blocks and DES also belong to block cipher family. I totally understand the procedure of DES, but I am confused that is DES take all the blocks of 64 bits of any plaint text and apply the process to all of blocks at a time or it encrypts first blocks then 2nd and 3rd and so on.. can anyone explain it Please??


texts: How does DES decryption work? Is it the same as encryption or the reverse?

texts: If DES decryption is the same as encryption done in reverse order, then how can the reversed S-Box convert 4 bits into 6 bits?


texts:
Is OCB as secure as GCM or CCM ?

Since OCB design is quite different from GCM and CCM, I was wondering if the security properties of these latters are satisfied by OCB, as well.


texts: Why are twofish or other algorithms not NIST approved, are they still safe?

texts:
NIST has a total of 3 approved block ciphers on their website: AES, TDES and skipjack.

I get why those are on there (though personally I find TDES a bit iffy) but from my understanding Twofish and Serpent are also good enough to make the list. so why aren't they there? are they too weak? have they been broken to an extend where they are no longer safe to use?

EXTRA:

I'm really interested in knowing why some ciphers are recommended and others aren't. I'm looking for an algorithm to use my self, to do this I want to make a selection of a few algorithms which are safe to use so I have a reason to fall back on when i'm asked why i chose for that specific cipher other than the standard excuse because it's AES (or NIST approved)

Are there credible sources I could quote for other algorithms (such as Twofish) which shows they are still reliable?


texts: What does Set Membership actually prove?

texts:
While going through this paper, I came across the idea of Set Membership proofs. The proof allows a prover to prove that a value is contained in some set. The point where I am confused is, all the elements of the set are known to the prover. All three steps of the proof generation can be run by anyone including the prover. Moreover, it seems that the prover can prove the membership of some value he/wants without revealing the value itself.  How does the existence of some such value help him further?

The ring signing protocol is given below. The signer/prover S is sending a membership proof to the user U trying to convince him that S is using a public key which belongs to the ring R consisting of public keys of all ring members. Point of confusion is that, the ring R is public and known to both S and U. If all the elements (i.e. the public keys) of the set (i.e. the ring R) are known to both (i.e. S and U), then what is S trying to achieve by the set membership proof?


texts: MitM with regard to unauthenticated clients

texts:
I'm trying to understand how man-in-the-middle attacks are prevented during key exchanges, and am confused by this Wikipedia statement:

Use of mutual authentication, in which both the server and the client
validate the other's communication, covers both ends of a MITM attack,
though the default behavior of most connections is to only
authenticate the server.

Is that saying the client authenticates it is really receiving from the server, but the server doesn't care who is sending?  Doesn't that mean the server might be talking to an eavesdropper who inserted himself in the middle and the eavesdropper can't decrypt server responses (which are simply forwarded to the client) but can pretend to be the client and see what the client is sending?


texts: On sub-linear ring signatures and transaction sizes

texts:
I've been reading Noether's paper on Triptych and its extension Arcturus, alongside a few others exploring sub-linear ring signature schemes.
I only have one question. Each paper (RingCT3.0 and its update, Triptych, Arcturus) states that the signature size scales logarithmically to the anonymity set. But what about the transaction size? I.e., does the anonymity set need to be included in the transaction? Doesn't this make it still scale linearly with the anonymity set size?
Any and all clarifications, corrections, etc. are appreciated.


texts: I read that the S-boxes introduce the much needed nonlinear behavior to DES. Can someone give me a lay mans explanation of why the effect of the S-boxes is said to be non-linear?


texts:
I realise there are homomorphic signatures for short messages, for instance with RSA encryption we have a signature scheme where $S(m_1 m_2) = S(m_1)S(m_2)$.

I would like to know if there's a signature scheme where the messages may be linear additive combinations of the basis vectors $(v_1, \dots, v_n)$ and where, if $v$ is in the subspace spanned by the basis vectors $(v_1, \dots, v_m)$ and the signatures $S(v_1), \dots, S(v_m)$ are known, it is possible to construct $S(v)$ from them.


texts: Using NIST constructions based on Keccak like cSHAKE128 for other sponges

texts:
NIST defines a lot of interesting applications of sponges in FIPS 202 and NIST SP 800-185 like the XOF cSHAKE128 or the MAC scheme KMAC.

All this schemes come with a security guarantee and are explicitly based on a sponge using Keccak as its permutation.

This leads me to two questions:

Do these constructions really rely on Keccak (apart from minor technical details like the padding length) or can they be adapted to different sponges without loosing security (assuming the alternative sponge function used is secure enough, of course)?
Are there any papers or standards published, which propose similar constructions which are not dependent on a single sponge instance?


texts: Is it okay to send an encrypted key using XSalsa20-Poly1305, and send subsequent messages using ChaCha20-Poly1305?

texts:
I am looking at a cryptographic protocol in a somewhat unusual environment: the communicating parties can share arbitrarily long secret keys over a secure channel.

If forward secrecy is not required, it seems that one can simply encrypt/authenticate a (random) 256-bit key using the 256-bit shared secret, and then start sending messages encrypted using ChaCha20-Poly1305 (or AES-GCM).  This seems to be trivially secure assuming that the underlying ciphers are secure (Proof: The attacker cannot forge or reorder messages after the first without breaking the AEAD or knowing its key -- but to obtain the key the attacker would need to break XSalsa20-Poly1305 or the CSPRNG used, or the 192-bit nonce of XSalsa20-Poly1305 would need to be reused, or the shared secret would need to be leaked.  The AEAD and XSalsa20-Poly1305 are both widely believed secure, the shared secret must be assumed secret, and the probability of a 192-bit nonce collision is negligible).  A counter starts at 0 each time, serving as both message sequence number (to prevent reordering) and nonce.

TLS-PSK is designed for this, but it is extremely complex.  This seems much simpler.


texts: What is this called: encrypt $X$ with key $E$, decrypt $X$ with key $D$?

texts:
I am a software developer interested in developing an application with cryptography. I can explain what I want to accomplish, but I do not know the technical terms for the cryptographic functions I am seeking.  Many Google searches have not helped me. Could someone please help me with the proper cryptographic terms for what I am seeking, so I know what to search for in my research?

Here is what I am looking for:

Encrypt large amounts of data quickly with key $E$.
Encryption is currently unbreakable and is expected to remain so as far as is
known.
The encrypted data cannot be decrypted with key $E$.
The encrypted data can only be decrypted with key $D$.
Key $E$ is created by passing key $D$ into an algorithm/function.
It is preferred that key $D$ can be less than 20 characters and can be
typed from what is visible on the keys of an ordinary computer
keyboard. (AKA...a password)

Thank you!


texts: size of group points and parameters in pairing based cryptography

texts:
$$e:G_1\times G_1\rightarrow G_2$$
In symmetric pairing-based cryptography with groups$(G_1,G_2)$ of prime order $q$ and   $a,b \in Z_q$Will the size of random generator $P$ from$ G_1$ and $a$ be same? I think it is different. I don't know why.


texts: Decryption that is easy for humans and hard/impossible for computers

texts:
Is there any research into digital cyphers that are easy for humans to decrypt, but hard for computers?

One example is Captchas, though those are being increasingly broken by computers.  However, Captchas are not quite what I have in mind.  Captchas depend on human domain expertise, which could theoretically be captured algorithmically and then cracked pretty easily with computers.

What I am looking for are cyphers that humans can easily decrypt, but are provably computationally hard or impossible.  The encryption process has to also be performed algorithmically.

The scenario this encryption scheme would work in is the following:

The encrypted message is made available for offline processing.
Within a relatively short time the human can derive the message.
An algorithm will either find the message impossible to derive, or at least impossible in practice.


texts:
I'm trying to hash two unique strings together to create a hash. The most obvious way would be simply to concatenate the two and run a hash function on it:

hash = sha256(strA + strB)

But I was wondering if this is how most people do it, and if there is a "standard" way of doing something like this in a most secure way.


texts:
What is the difference between H(M) and H3(M, s, IDA)?

I am aware of Hash function with a Message and a Key, but there are three parameters in:

H3(M, s, IDA).

Here M is the message, s is the key, and IDA is the identity of user A.
I meant that how to implement secure hash H3(M,s,IDA)


texts: Message authentication vs entity authentication

texts:
Does message authentication authenticate the entity?

If the answer is "No", because message authentications like MAC work with the shared symmetric key, then my second question is:

  Does a message authentication using an asymmetric key like the digital
  signature enable both entity and message authentication?

If the answer is yes:

  Is it arguable to say that message authentication using asymmetric key
  provides both entity and message authentication?


texts: Is choosing $1$ as a public exponent valid in RSA?

texts: I know it will not encrypt anything. But is $1$ valid as a public exponent in an RSA public key?


texts:
I am studying for an exam right now.  And I wanted to make sure I got this point correct.

AES is not a Feistel cipher because the operations in AES are not invertible.

Is the above statement correct? If not, why isn't it a Feistel cipher?


texts: Block cipher not resistant to collisions

texts:
If we have the following block cipher, $E(k,m)$,  which is a permutation, why is $f_2 (x,y)$ not collision resistant?

$$f_2(x, y) = E(x, x \oplus y)$$


texts: "Order" in cryptographic terms for generators

texts:
Frequently I have seen people use the term order in cryptography (the group theoretic one). I have a mathematical background and order (say for prime modulus $p$) is defined as the smallest integer such that

$$a^r \equiv 1 \pmod p$$

So a generator (something which has the max possible order i.e order is $\phi(p)=p-1$) will have order (p-1). In case of a composite group, the generator should have an order $=\phi(N)$.

How is it that frequently I read in Crypto literature that people say generator has order N?

For example: The first answer at: When do we need composite order groups for bilinear maps and when prime order?

Am I missing some details or is my understanding incorrect?


texts: Why only one secret value with Shamir's secret sharing?

texts:
Shamir's Secret Sharing works by sharing data points on a curve, whereby when you have the required number of data points, you can find the function of the curve and find out the secret, which is effectively f(0).

In the polynomial form of the function, the constant (the coefficient of $x^0$) is the secret information.

Could you treat the coefficients of the other powers of $x$ as secret values as well?

If so, are they just as secure / secret? Or is there some subtlety going on where you need fewer values to get the other coefficients?

It seems that if you had a cubic curve that you could have 4 secrets $S_i$, instead of 3 random numbers and one secret:

$$f(x) = S_1x^3 + S_2x^2+S_3x+S_4$$


texts:
It seems all these options are correct to me

  fingerprint of the provided input.
  A one-way deterministic hash function.
  symmetric hash function
  A hash function that generates a digest.

Anyone identify the wrong option and why?


texts: How are Zhang-Safavi-Susilo signatures short?

texts:
ZSS signatures have been introduced by Fangguo Zhang, Reihaneh Safavi-Naini, and Willy Susilo: An Efficient Signature Scheme from Bilinear Pairings and Its Applications, in proceedings of PKC 2004.
Standardization at IETF was attempted with ZSS Short Signature Scheme for Supersingular and BN Curves [*].

The example given in appendix C.1 for supersingular curves has 2048-bit signature for 128-bit security (256-bit hash); appendix C.2 for Barreto-Naerhig curves has about 1012-bit signature for 112-bit security (about 224-bit hash).
This is a lot more than 512-bit signature of DSA or ECDSA of FIPS186-4, or Ed25519, at comparable conjectured security level.

In what sense, or compared to what, can ZSS signatures be qualified as short?

[*] My guess is that this draft merges ZSS Short Signature Scheme and ZSS Short Signature Scheme for BN Curves.


texts: What does DH(IPKa, IPKb) notation mean? Diffie-Hellman confusion

texts:
I'm trying to implement X3DH (extended triple Diffie-Hellman) in a network of mine.
The way I understand it, a bundle (IPKb,SPKb,OTKb) is retrieved by Alice from Bob, through the server, and
using her own public keys IPKa and EPKa she calculates:
DH(IPKa,SPKb)
and some others.
What I do not understand is: what are these public parameters used for in DH? Isn't Diffie-Hellman constructed with private keys, and 2 pre-determined public numbers? Should I treat these 2 keys as those pre-determined numbers?
Also, Diffie-Hellman requires key exchanges and communications between Alice and Bob; why can't Bob compute the key at the same time as Alice? Why does Alice need to return a bundle of her own IPK and EPK for Bob to do the calculations from scratch? I'm confused.
Sorry for the naive question but I can't seem to find an explanation on what these passed keys are supposed to be doing anywhere.


texts: Make AES more secure by randomising the blocks in an encrypted file

texts:
I am developing a software with hybrid encryption (RSA-4096 and AES-256-CBC).
The iv and key of an AES encrypted file will be RSA encrypted end exchanged through a different way than the encrypted file. Thats ok for me to this point.

I am thinking about where it is most easy to break the encryption of my own files and always come to the point where a key and iv guessing would take ages but is theoretically easy. It just takes time with the computing power we have today.

In my application the transfer of the encrypted file will not be possible if there are bits lost in any case.

Version 1:
Since CBC is always based on the the pre block, why do I not just change the order of the blocks in the file and write a map together with the key and iv into the RSA part? Is this a stupid idea?

Version 2:
Why do I not just replace a random character in each AES block with its "value" + 1 or so and write into my RSA a map of the chawed characters?

In my opinion in Version 1 the "guessing power" would be the "AES blockcount"*"time for a single file" and after that the order would sill be wrong. I have no idea what effort it would take to get the right order...

In the second Version it would be even to hard for me to calculate. It could be any bit in a block with a wrong value and a guessing of iv and key per block.

Does that make sense? Who knows about the computing power we will have in a few years. And I also don't want people to read the files in a few years ;-)


texts:
I'm writing a multi-tenant application that interacts with a couple of different APIs on behalf of each customer. Obviously, we need to store private keys for these various different APIs in the database so that we can connect to them. Goes without saying, I need to encrypt those.

I wanted to use a separate encryption key for each tenant on the system (I'm using openssl_encrypt with AES-256-CBC). To accomplish this, I have a separate "crypto" database. The tenant_keys table contains the following columns:

A tenant_hash, which is a has of a random value stored in the tenant's settings table, used for lookup
A tenant_key, which is the tenant's unique encryption key.
A key_timestamp that I'll use in the future to periodically rekey tenants

The obvious weakness is that if the database were stolen, the attacker would have all of the keys. To combat this, I've generated a "master key" that is stored as a text file on the server. This master key is then used to encrypt all of the various tenant keys. So, when a session is first initiated and the tenant is looked up, the tenant's key is decrypted and stored in the session. So, here are my questions:

Is there a better way to secure each tenant key (perhaps some sort of key server, but building an entire CA  hierarchy and such seems like overkill vs protecting the master_key file with good chmod settings)?
Is there a safer way to store the tenant's key ephemerally without needing to do a round of decryption (costs CPU time) each time we need to use it, besides in the PHP session? The PHP sessions will ultimately be stored in some sort of shared storage (probably redis) as the environment will be clustered.