texts: Did NIST verify “post-quantum” claims in the SHA3 proposal papers?

texts:
I have been reading Bernstein’s “Quantum attacks against Blue Midnight Wish, ECHO, Fugue, Grøstl, Hamsi, JH, Keccak, Shabal, SHAvite-3, SIMD, and Skein” paper from 2010…

  This document disproves the claims of preimage resistance for Blue Midnight Wish,
  ECHO, Fugue, Grøstl, Hamsi, JH, Keccak, Shabal, SHAvite-3, SIMD, and Skein. Specifically, this document presents attacks finding preimages in each of these hash functions using time much, much, much smaller than $2^{224}$: specifically, using only about $2^{112}$ simple operations. The exponent gap is so large that it cannot be explained by the difference between “224 bits” and “approximately 224 bits.”

(emphasis mine)

The most interesting points are …

  This is, in particular, a claim of $2^{224}$ preimage resistance for 224-bit Keccak. There is no warning regarding the impact of quantum computers: Keccak claims “preimage resistance,” not merely pre-quantum preimage resistance.

and

  Each attack uses approximately $2^{112}$ iterations, disproving the $2^{224}$ preimage-resistance claims for each of these functions. The exact complexity of each iteration, and the required number of qubits, varies somewhat from function to function, but is on a far smaller scale than the $2^{112}$ complexity gap.

This contradicts some of the expectations I had after NIST validated and chose Keccak as the winning SHA3 proposal. Also, it somewhat underlines the correctness of my suspicions related the incorrect “post-quantum sufficient” claims in the Keccak papers. (You might remember my older question where I already suspected another post-quantum claim of Keccak to be incorrect: What exactly is the base for the KECCAK (SHA3) claim that a security strength of 256 bits is “post-quantum sufficient”?)

As a result, I've got two related, yet somewhat different questions:

As it stands, Bernstein showed Grover’s algorithm could successfully enable pre-image attacks on SHA3 candidates (including Keccak, the SHA3 finalist) and as far as I learned from the different replies here at Crypto.SE: if it's broken, it's broken… no matter how theoretical or far-fetched the break is, a break is a clear warning sign. Even when I would ignore that, the question remains if the claims of those SHA3 papers can be trusted at all. I mean, I did quite some research but I frequently noticed that claims can not be verified; especially in relation to Keccak. (See my question and answer: Is it possible to actually verify a “sponge function” security claim?)

Are there any papers that I should know about which contradict the findings of Bernstein’s paper?
For the benefit of the doubt, I won't start contemplating if NIST might have been influenced during their SHA3 quest or not, because similar crypto-news has been raving the press too much already. Yet, I wonder why Bernstein’s findings seem to have been ignored and I would like to understand why NIST chose to ignore the fact that most SHA3 proposals might suffer from quantum-attacks.

Did NIST actually validate any of the proposals for post-quantum security (and related claims in papers) at all, or was quantum computing simply ignored during their SHA3 security assessments? And if quantum was ignored, what was the motivation to do so?

(Maybe you can point me to references confirming NIST did or did not validate post-quantum aspects… I couldn't find any.)


texts: Is AES-256 over AES-128 weakening the original encryption?

texts:
When transfering data using TLS the browser and server agree the cipher suite to be used - so for example this could be chosen as AES-128 and is (probably) outside of my control. If I separately encrypt a file using AES-256 and then Alice downloads this via her browser (using AES 128) have I still effectively got AES-256 security?

My reasoning goes like this: even if the AES-128 encryption on the TLS link was broken by Eve then all she would get is the AES-256 encrypted file and she would then have to break that encryption to see the plaintext.

Of course the AES-256 key is sent to Alice over a separate channel.


texts: Maximum length in bits of the product n=pq

texts:
If p and q are two 1024-bit prime numbers, would the maximum length in bits of product $n=pq$ be ${1024}^2$ or $2^{1024}$?

I think it is ${1048576}={1024}^2$?

Also, would the least significant bit of $n$ be a $0$ or a $1$? I am assuming it would be $0$? Any explanation of what determines significance would be great


texts: Are there any practical examples of breaking a system using linear attacks?

texts: I've read some papers about linear cryptanalysis. But since I am going to give a lecture about it I am looking for an example of breaking a system using this attack. Is there such an example available?


texts:
In a mental poker game I am designing as an learning exercise, (One used in example is a 3 card flash with no desk cards) suppose I have a set of cards and other person also has a set of cards. each card is mapped to a prime order (EC)DH group element. We both know other persons cards raised to some power. That is if my opponent has cards c1, c2 and c3, I know c1z1, c2z2 and c3z3, with z1, z2 and z3 being known only to my opponent. The mapping (which card maps to which group element is publicly known) and what my opponent knows is the discrete logarithm of the numbers I know he has base a valid card. Of course this is exactly what my opponent knows about my card too. Now is there any way to find out who won without revealing the cards or any other information about my cards (like whether the doubles or sequences exist), as in zero knowledge proof.
EDIT:
Just realized that it is called Pohlig-Hellman cipher. I assume others know what I am trying to do with this to shuffle cards. I guessshould be we can create a EC version of it too. While I understand that it is not IND-CPA, I don't think that it much of a problem in this game.
I looked at security problems with PH cipher but almost all of them has to do with the fact that it can distinguish plain texts based on whether or not they are QR modulo p in group ℤp* and they are malleable. Actually, I need to use this malleability. This malleability is what allows players in my game to produce a proof that they have not cheated, I realized that the proof will be too damn long tho). But the game I am designing uses no Quadratic non-residue, the group is a $q$ order subgroup of quadratic residues as we often use for Diffie-hellman and (large prime subgroup as we normally use in EC versions), the card to group element mapping must be pseudo random and different in each game, agreed to by each player. My another question is are there any other security risks associated with it?


texts: How to prove to a third-party that a given response came from a specific domain?

texts: Suppose I've got a response from a website using https. Is it possible to store the certificate and keys exchange to prove to a third-party that the response came from that domain?


texts: Pohlig-Hellman Algorithm: Adding up the solution via CRT

texts:
I have a question about the Pohlig-Hellman Algorithm for the discrete log problem. I understand the concept, but doing the exact calculations I get confused at one point; to illustrate, let's look at the equation $2^x=3$ in the group $(\mathbb{Z}/29\mathbb{Z})^*$.

If my calculations are correct, we get that $x \equiv 1$ in a subgroup of order 4 and $x \equiv 5$ in a subgroup of order 7. Using the isomorphism $((\mathbb{Z}/29\mathbb{Z})^*, \cdot) \cong (\mathbb{Z}/28\mathbb{Z}, +)$, we get the equations $$x \equiv 1 \mod 4 \\ x \equiv 5 \mod 7$$ which is then pasted together using the Chinese Remainder Theorem to get $x \equiv 5 \mod 28$.

Now here is where I am confused: The results x=1 and x=5 are derived using calculations in $((\mathbb{Z}/29\mathbb{Z})^*, \cdot)$. Why can we just 'transfer' the very same numbers to the respective subgroups of $(\mathbb{Z}/28\mathbb{Z}, +)$, when we do not know the image of these elements under the isomorphism? Is it just because we are technically already in the group $(\mathbb{Z}/28\mathbb{Z}, +)$ when we are dealing with the exponents? Or am I missing something more crucial here?

Thank you in advance for any kind of advice.


texts: Is every bytestring a valid Ed25519 private key?

texts:
In other words, is it a bad idea to simply do this?

signingkey = crypto_random_bytes();
verifykey = Ed25519.verifykey_from_signingkey(signingkey);

Are there weak keys that standard libraries protect you from?


texts: If A and B are co-primes, does Ax mod B (where x, any positive int) gives {0,1,2,....,B-1}?

texts: If $A$ and $B$ are co-primes (i.e. $\gcd(A,B)=1$), does $A\cdot x \bmod B$ (where $x\in \mathbb N$) give as result an element of $\{0,1,2,....,B-1\}$ ?


texts: Quantum Secure Signing Algorithm with a 256 bit signature & key. Am I missing anything? Can I remove tradeoff?

texts:
So I was looking at Lamport signatures and trying to figure out if there is a way to reduce the key size and signature. I stumbled across something that is tiny (125 times smaller signatures and 500 times smaller public key) and almost as secure but it has a catch.

So, I realized that Lamport Signatures get their security from requiring the user to pre-commit to 512 different values, you then show half your secret keys to sign. The security comes from the fact that an attacker only has odds of any randomly picked number being the correct signature of roughly 1/2^256

What if instead, you started with a random 512 bit number A, hashed A getting 512 bit B, then hashed it again to get 512 bit C. Now you use C as your public key. And when you want to sign a message, like Lamport signatures, if a bit is 0, then you pull a bit from A, if 1 then pull a bit from B. The difference being that with Lamport you need an entire hash not just a bit(little bit more secure.. but not worth the space, double the key in my system and you probably have more security).

Then catch is that you now need to reveal A, which can be used to calculate B and C. This proves that you did indeed use those hashes to sign. The problem is that you've just revealed your private key and anyone else can sign on your behalf. So the only way this works is if you use two phases: commit phase where you hand over the signature and message. Then a verifying phase where you send over your private key to verify that it was indeed you signing it.

In most cases, multiphases is fine. After all, Lamport is essentially multiphase.. send public key, send signature.

Using a long hash chain you could come up with a many-use private key where you just pop off the last hash (which is actually three hashes) to use it.

Am I missing anything? Any thoughts on how to remove the commit phase or construct something that gets similar security uses a similar idea?

Still not going to work for my cryptocurrency since I can't have multi-phase signatures but might help some people out there or help with brainstorming a shorter public key & signature scheme that would work.


texts: Subverting the key generation step in RSA public key cryptography

texts:
I am interested in the ways an RSA key generation implementation can or cannot be subverted so that the subverter has an advantage, but the owner of the key, and the people who interact with the owner, are left unaware that something is going on. I assume that the owner of the key does not have the ability to detect subtle bugs in the key-generation implementation, but that the key will be used for encryption and decryption with standard implementations outside the subverter's control.

My first idea was that a subverted primality test might accept, instead of rejecting, numbers of the form P1*P2 where P1 is a fixed prime known only to the subverter, and P2 a random prime. The owner of the key would end up with a modulus of the form P1*P2*Q, which the rest of the world would not necessarily be able to distinguish from a semiprime number. However, according to this answer, the owner of the key may find themselves unable to crack their own public key, that is, to read messages intended for them. I understand the linked answer to mean that the prime decomposition of the modulus is necessary to read encrypted messages, and in effect, the owner of the key would not have this decomposition. The owner of the key would only have P1*P2 on the one hand and Q on the other hand.
Another idea would be that the prime generation implementation might be subverted in a way such that there exist a million primes P1,P2, …, P1000000 that the implementation is more likely to generate than the others (say, each has probability 1/2000000 to be generated each time). This would, in effect, amount to a private Mining your Ps and your Qs attack(*), reserved for the subverter (who would know the values of P1, …, P1000000) but, as long as the subverted implementation remained in moderate use, unlikely to be detected by anyone else (owner of the key and rest of the world).

(*) It occurs to me after having written the question that the subverter can keep its game preserve more private if the subverted implementation never pairs a prime from the list P1,P2, …, P1000000 with another prime from the list. This doesn't prevent them to be discovered one by one using the original “Mining your Ps and your Qs” attack, but at least they do not unravel all at the same time.

My question is: can 1. be made to work using, say, some sort of pseudoprime instead of a composite number to maliciously accept as prime? Is there a reason why 2. might not work in practice?

These are two questions but they are related in that they are relevant to the same purpose


texts: Signing the hash of a key with the same key

texts:
Given a private signature key sk and a public signature key SK, does revealing sk(H(SK)) (in addition to SK) make it more easy for an attacker to determine sk or to fake a signature that would appear to have been produced by sk? Is this scheme a bad idea - in other words, does it compromise the secuity of the signing algorithm? (It seems like this is analogous to key-dependent encryption, but for signatures, and with the interposition of a hash function in between).

If that matters, I'm using ECDSA signatures. Any pointers are appreciated.


texts: What is the purpose of having a one-way function also be a permutation on it's on domain?

texts: From a cryptographic sense, what value is added from setting the domain to be the image in the mapping?


texts: Is it possible to use the RSA algorithm, or a variant, for software licensing?

texts:
I'm almost a newbie about RSA encryption, so my question could it be banal.
I'm beginning to create a licensing system for my software.
I need to distribute a crypted license file to many customers.
I was thinking to use RSA public key to encrypt license file (with OAEP padding or PKCS#1 v1.5).
The software that will be licensed to customers will have inside the private key in order to be able to decrypt the license content.
Now the question is if can be possible to know the public key giving the encrypted file, the private key and the final plain text.
This because an hacker could know these data because are all inside the distributed software.

In other words I need a crypto algorithm that use two different keys.
One pw for encrypt the data, and another to decrypt the data.
And where will not be possible to obtain the encrypt password giving the decrypt password and crypted text.


texts:
My question is about proving that a function is negligible if it is ran polynomial number of times.

This my solution: By the definition of negligibility, we have $negl_1(n) < 1/p'(n)$ where $p'(n)$ is any polynomial. We multiply $p(n)$ both sides: $p(n)*negl_1(n) < p(n)/p'(n)$.

We let $p'(n)>>p(n)$. There is always a $p'(n)$ that satisfies this inequality. Thus, $negl_2(n) = p(n)*negl_1(n)$ is negligible.

Is my solution correct?


texts: Cryptographic hash function based on logistic map?

texts: Is there any secure cryptographic hash function based on the logistic map?


texts:
Is the concept of provably secure hash the same as entropy smoothing hash functions?

In the tutorial Sequences of Games: A Tool for Taming Complexity in Security Proofs V. Shoup shows us a proof of semantic security of a hashed ElGamal encryption.

In order to get that proof (pag. 9) he put the following condition: we need a family of keyed "hash" functions $\mathcal{H} := \{H_k\}_{k\in K}$ where each $H_k$ is a function mapping $G$ to $\{0,1\}^l$ ($l$ a positive integer and $G$ is a group) such that this family $\mathcal{H}$ is "entropy smoothing".

He tells us that "entropy smoothing" gives us some kind of guarantee that makes it hard to distinguish $(k,H_k(\delta))$ from $(k,h)$, where $k$ is a random element of $K$, $\delta$ is a random element of $G$, and $h$ is a random element of $\{0,1\}^l$.

The author said there are ways to construct entropy smoothing hash functions, but it's just a conjecture that ad-hoc hash functions own this property.


texts:
Assume we have a big S-box (i.e. $15*15$). We have truth table of it. (so $2^{15}$ output).
How can we find its degree without using Algebraic Normal Form of its Boolean functions.
Or with ANF, can you help me to write the algorithm of implementing.


texts: Cracking hashes: With vs without knowing the salts

texts:
Let's assume the following situation:

The attacker has extracted 1000 password hashes from a website (vuln.com) along with all their usernames and hashing algorithm (assume bcrypt). The only piece of information stopping them from cracking all the hashes is the missing passwords and salts. Assume the salts are all cryptographically random.

What would change if the attacker also has all the salts?

What are the differences between cracking the hashes with and without knowing the salts?


texts: What is the impact of different modes on pseudo randomness of AES?

texts: AES in CBC-MAC mode is proven to be good PRF . But is there any study done on other modes ? how good is ECB mode as PRF ?


texts: Does Mersenne Twister generate homogeneous numbers?

texts:
I have been assigned to generate 15000+ homogeneous and uniform random numbers for a work.

I have been searching if Mersenne Twister generate homogeneous distribution of numbers but I don't find nothing. I have found a lot of test and proprieties but I do not know if any of those proprieties/tests refers to the homogeneity.

Can you explain me if the algorithm generates homogeneous numbers, why and what are the proprieties involved in?

By homogeneity I think that I mean this.


texts: IND-CPA game with a state-dependent Encryption Function that is insecure once

texts:
in the context of another setting I was asked the following question.

Suppose the IND-CPA game is played with a symmetric encryption function $E$ that keeps a state of how many encryptions have already been requested by the adversary $A$ during the execution of the game. $E$ always outputs $E(m)=E'(m)$, where $E'$ is an IND-CPA secure encryption scheme, except for the $i$-th request, where $E(m)$ is insecure and trivially reveals the plaintext $m$ instead of invoking $E'$. $i$ is polynomially bounded in the security parameter and $A$ does not know how $i$ is determined (it could be probabilistic and depending on the previous executions of $E$).

Intuitively, I'd  say that $E$ is not IND-CPA secure. An Adversary $A$ that just guesses the polynomially bounded $i$ and poses any challenge after $i-1$ encryption requests during the pre-challenge phase would always win the game if he correctly guessed $i$, which happens with non-negligible probability as $i$ is polynomially bounded. However, when trying to do a formal proof of this, I struggle to state an explicit $A$ with a non-negligible advantage, as this $A$ needs a precise specification of the upper-bound of $i$.

I'd be thankful for further discussion and tips about how one could solve my issue.


texts: Straightforward method for hampering frequency analysis on deterministic encryption

texts:
I'm brainstorming some different ways of making deterministic encryption more secure. I want to use deterministic encryption to preserve searchability over the keywords in a document set. However, I know that frequency analysis is always a concern when preserving searchability in this way.

The strategy I came up with basically still does deterministic encryption (with SIV mode), except instead of just one IV I use ten different ones.* When I encrypt a keyword I choose a random number modulo ten and use that to index into the array of IVs. I then append the index to the ciphertext so it can be decrypted.

To search, you just encrypt the keyword with all ten possible IVs and make a big OR query with all ten ciphertexts.

I don't know a lot about frequency analysis, so I'm not sure how much (if any) additional security this provides compared to regular deterministic encryption. Anyone have any ideas?

My intuition is that for small document sets with relatively few keywords this does provide nontrivial protection against frequency analysis. But I also think the security might not scale to very large data sets.

*In practice the 'IV' here will be additional input to the first step of SIV.


texts: Could a strong round function be immune to slide attacks

texts:
An excerpt from the wikipedia article on slide attacks states:

  ...The only requirements for a slide attack to work on a cipher is that it can be broken down into multiple rounds of an identical F function. This probably means that it has a cyclic key schedule. The F function must be vulnerable to a known-plaintext attack...

and:

  ...Once a slid pair is identified, the cipher is broken because of the vulnerability to known-plaintext attacks. The key can easily be extracted from this pairing....

The statements:

  The next step is to collect 2^{n/2} plaintext-ciphertext pairs. Depending on the characteristics of the cipher fewer may suffice, but by the birthday paradox no more than 2^{n/2} should be needed.

lead me to think that even a truly random oracle would produce slid pairs, so it would appear that eliminating the existence of slid pairs is not a possibility.

My question is relatively simple. Suppose the round function of a cipher was resistant to known plaintext attack (i.e. known plaintext does not facilitate recovery of key information). Could such a cipher claim provable resistance to slide attacks? If not, what advantage would a slid pair offer an attacker?


texts:
I suppose this question addresses surjectivity and injectivity. We talk about collisions but did we prove yet rigidly that this function is not reversible?
EDIT: Accepting the answer based on Dirichlet Box Principle (if domain is bigger than codomain innevitably there will be collisions). I agree that for mappings
$h:\{0,1\}^*\rightarrow \{0,1\}^{256}$ the function is not injective and therefore not bijective


texts: Key recovery after AES-ECB encryption of two blocks with some known plaintext/ciphertext

texts:
I am analysing a small, bespoke end-to-end encryption service's source code, in particular their user registration process. I am finding some interesting things going on and I am wondering if there's some vulnerabilities here:

The client code generates a random Master Key for the user which is 128 bits. This is used to encrypt data on the service.
A password based key derivation function is run on the user's Password to produce a Password Derived Key of 128 bits. A salt is not used at all here.
The Password Derived Key is used to encrypt the user's Master Key with AES in ECB mode.
Some half-random Temporary Data is created of 128 bits. I am not sure what this Temporary Data is used for, I haven't seen it being used for anything in particular anywhere else in the code. Anyway, the first 32 bits are randomly generated, the second 32 bits are zero, the third 32 bits are zero, and the final 32 bits are randomly generated. The array as 32 bit words might look something like: [1502582904, 0, 0, 3153058828].
The same Password Derived Key is used to encrypt the Temporary Data with AES in ECB mode as well.
The encrypted Master Key and encrypted Temporary Data are concatenated together and sent to the server API to create the account on the server. The API then sends back to the user an email confirmation code that the user uses to confirm their email. The confirmation code is the Base64 encoding of this data concatenated (||) together:

"emailconfirmlink:" || some metadata || encrypted Master Key || encrypted Temporary Data

So the obvious vulnerability seems to be that they send the user's encrypted Master Key back to the user via email for no apparent reason instead of just randomly generating a token on the server side and expecting the user to return that in order to complete the email confirmation. That would allow anyone who can read internet traffic a chance at cracking many user passwords at once pretty easily as there is no salt in the key derivation process to prevent rainbow tables.

I am wondering about another vulnerability in that the Password Derived Key has encrypted the Master Key, but it has also been used to encrypt the Temporary Data as well. So we have:

AES-ECB(Password Derived Key, Master Key)
AES-ECB(Password Derived Key, Temporary Data)

We know AES-ECB is not good at encrypting multiple blocks under the same key. So it has encrypted two blocks now under the same key. Also the Temporary Data has 64 bits of known plaintext in the middle of the second block (all zeros). Also the attacker can see the AES-ECB ciphertext output of those 64 zero bits.

My questions are then:

With the encryption of the Temporary Data with 64 bits of plaintext known, does this allow an attacker to brute force the password and know when they got a plausible password because the decryption of the Temporary Data with AES and the derived key they are currently trying will result in 64 bits in the middle being zero which is statistically unlikely?
Can a cryptanalyst retrieve the full Password Derived Key more easily now that it has been used to encrypt multiple blocks in AES-ECB, some of which has known plaintext? How? And does this mean they could use that recovered Password Derived Key to decrypt the Master Key?
Can a cryptanalyst use the known encryption of the zero bits in the Temporary Data to recover the Master Key with less effort (perhaps using a known plaintext attack, differential cryptanalysis or two-time pad type recovery)?
What other cryptanalysis is possible if a cryptanalyst has access to this information?


texts: How can one detect if a hash function doesn't have a full image?

texts:
Suppose we have a hash function $H: \{0,1\}^* \mapsto \{0,1\}^n$, that doesn't get all the $n$ length

bitstrings as a value for any input, but is otherwise secure. Can that fact be detected?

For example, let $H$ be a secure $n$-bit hash function. You are given a black box function $F$ and told it's either $H$ or $H\hspace{-0.04 in}\circ \hspace{-0.04 in}H$, the latter of which lacks an expected ~37% ($1/e$) of the image when $n$ is large.

Can you determine which it is without knowing $H$? In a tractable time,

when $n$ is large enough for $H$ to have collision resistance?


texts: Security of receiving RSA-PSS computed mask in verification step

texts:
I'm trying to verify an RSA-PSS padding in an Ethereum smart contract
The code to compute the MGF step (i.e. calculating many SHA1 hashes) is very expensive in terms of computation costs (gas) on Ethereum.
How insecure would it be to receive the MGF calculation result as input, and just verify parts of it by calculating just a few hashes from the MGF step and verify they match the input?
For example lets say the mask to be computed requires concatenating 40 hashes in MGF
we calculate just x of them and verify they are in the mask received as input.
The rest of the verification steps will be done as usual


texts: Block ciphers as secure as AES but immune against cache timing attacks?

texts:
This is a question out of curiosity! I really don't know of any other block cipher that is as secure as AES that has a substitution permutation structure and can be used as an alternative to AES to protect implementations against cache timing attacks.

Searching Google, revealed other NIST finalists, but the best of them had a Feistel structure. There are also many others, but there is less confidence in them compared to to AES.

I am looking for a good block cipher that is similar in structure to AES with same level of security, and efficient to implement in software, for both small and large devices.


texts:
I am using python and libnacl, which is a libsodium wrapper, to develop an application where users can deposit encrypted data.

Alice uses libnacl.sealed.SealedBox(keyBob) to encrypt her message and uploads it to a database for Bob to download it.
Bob and Eve can read the database and observe there I a new entry. Neither Eve nor Bob cannot tell that the message was sent by Alice. Bob can decrypt the message and therefore knows that he is the recipient.

Eve also knows Bob's public key.
Can Eve tell that the message's recipient is Bob?

edit:
VincBreaker pointed me at the documentation of libsodium sealed box where you can find:

  ephemeral_pk ‖ box(m, recipient_pk, ephemeral_sk, nonce=blake2b(ephemeral_pk ‖ recipient_pk))

This tells some "ephemeral" public key is included in the sealed box.
What does "ephemeral" mean?
To be precise is there a way to link the ephemeral_pk to Bob's actual public key?


texts: Function to derive an integer from a given password

texts:
I need to get an int, derived by a given password, to feed it to a deterministic PRNG as a seed. The derived int should not give away any clues about the password.

How can I achieve this without getting too many collisions? (Because the integers are derived from a string that is much larger, I suspect that there will be many possible collisions, yet I want to minimize the chance of their occurrence.)

I have tried a few solutions and my current function strikes me as being too kludgy.

Here is the pseudocode of what I am doing right now:

password := getPasswordFromUser()
salt_len := 16
salt := getRandomBytes(salt_len)
// the password and salt is then put through a Key Derivation
// function. The key will be used for encryption.

// Here comes the part I have trouble with; to "randomize" the
// order in which the data will be stored, I am using a deterministic
// PRNG, which is seeded as follows:

// Create a long string that contains the password:
orderPasswd := password + "abcdefghijklmnopqrstuvwxyz" +
    "1234567890ABCDEFGHIJKLMNOPQRSTUVWXYZ.,;:#+!§$%&/()=?"
// Create a sha256 sum of this string, feed it to the
// deterministic PRNG as seed and shuffle the string:
orderPwHash := sha256sum(orderPasswd)
// derive an int from the hash by converting it
orderPwSeed := int64(binary.BigEndian.Uint64(orderPwHash))
// shuffle orderPasswd using the Fisher-Yates shuffle algorithm
orderPasswd = shuffle(orderPasswd, orderPwSeed)
// Put orderPasswd through the KDF, hash the key and shuffle
// the order with an integer derived from the hash:
orderKey := getKey(string(orderPasswd[salt_len:]),
            orderPasswd[:salt_len])
orderKeyHash := sha256sum(orderKey)

// convert that hash to an integer to finally get the seed
// that will be used to determine the order
orderSeed := int64(binary.BigEndian.Uint64(orderKeyHash))

// seed the PRNG with orderSeed... shuffle the order...

Edit:

I have accepted Ilmari Karonen's answer, because he put a lot of effort into it and it contains vital information for anyone trying to implement cryptography.

I have dismissed the idea of shuffling the message, as it would unnecessarily complicate my code and increase the likeliness of mistakes without adding to the security, which is especially bad in this context.

Because the message, once encrypted with AES256 and a key derived with scrypt set with N=65536 and p=2, will look like random noise, this ought to be sufficient.


texts: How did the power measurements translate to AES Key?

texts:
A side channel attack is described here.
I did not quite get , how the power measurements are used to get the
decryption key , can any body explain it?


texts: ECC How do the Curve, its number of bits of security and key size affect the maximum size of ciphertext?

texts:
First of all, excuse me if this question is too noobish.

I'm trying to understand how these things are relate: Curve type, its 'number of bits of security', size of the key and the maximum ciphertext size.

Comparing to RSA, I know, that size of the key directly affects the maximum size of ciphertext: it can never exceed the key size and in practice is even smaller than that.

Is this still holds for ECC?

If so, what's the limitations on the size of the key in terms of a specific Curve? Is it even possible to allocate keys of different sizes? Or, given that math is discrete, does each curve has a hard ceiling for a key size?

If on the other hand, the key size is unlimited, is it true that no matter how large it is, the effective hardness of encryption will never exceed the 'number of bits of security' of specific Curve? If so, does increase the key size only gives you a larger limit on the ciphertext size?


texts: In CBC mode I know that if i get a corrupted Ci* block than Pi and Pi+1 will be wrong during the decryption, but i believe that this happens only when Ci* is not envolved during the feedback stage at the encryption, my question is what happens if the corrupted block is a feedback at the encryption stage, will it have the same impact as before?


texts: Role of AND operation in Side Channel Security

texts:
I was going through a side channel protection. It seems in the 3-shares (Appendix A) or 4-shares (Appendix B) has some computations that grows with the number of AND operations.
My question: Is there any standard metric by which I can measure the cost for side channel protection (under a given requirement, such as 3-shares) for an Exclusive-OR operation and an AND operation? Something like, 'For 3-shares, the cost for an Exclusive-OR operation is 3 Gate Equivalents and that of an AND operation is 5 Gate Equivalents. This grows to respectively 6 and 12 for 4-shares'.


texts: Peikert's framework for attacks on R-LWE: What "reduction modulo q" means?

texts:
I am reading Peikert's paper [Pei16] about secure instantiating of R-LWE problem. In section 3.1, The author gives a new attack framework by using "reduction modulo an ideal divisor $\mathfrak{q}$ of the modulus $qR$".
I'm a little new to Algebraic number theory and so I did not understand this framework especially the following part:

"Let $\mathfrak{q} ⊆ R$ be an ideal divisor of $qR$, having norm $N(\mathfrak{q}) := |R/\mathfrak{q}|$, and let $ψ$ be a continuous error
distribution over $K_\mathbb{R}$. Given Ring-LWE samples
$(a_i, b_i = s · a_i + e_i) \in R_q × K_\mathbb{R}/qR$
where $a_i ← R_q$ and $e_i ← ψ$, we can reduce them modulo $\mathfrak{q}$ to obtain samples $(a'_i = a_i \mod \mathfrak{q} , b'_i = b_i \mod \mathfrak{q}) \in R/{\mathfrak{q}} × K_\mathbb{R}/\mathfrak{q}$"

What "reduction modulo $\mathfrak{q}$" means? Can anyone help clarify things for me? Giving an example would be perfect.


texts: There are a number of papers in the literature describing secure/fair coin flipping protocols. Unfortunately in my case, I am looking for coins that are epsilon-biased or epsilon-correlated. I am looking for a coin-flipping protocol that is guaranteed to output correlated and/or biased coins to parties for some pre-agreed levels of correlation or biasing or fail securely.


texts:
If I were to supply arbitrary values to an ECDSA recover function on secp256k1, is there some likelihood that the function would fail to return some value for the public key?

I am specifically trying to create signatures for an Ethereum transaction whereby the private key is unknown to me (single use transactions). Please assume that I will choose the values for the signature to optimise success (I.e., only enter sane values).

Edit: to clarify what I’m trying to achieve, see this post https://medium.com/@weka/how-to-send-ether-to-11-440-people-187e332566b7. In summary: create a transaction with some invented signature, do ecrecover on that signature to find it’s public key (and Ethereum address), fund that address with another transfer then finally submit the original transaction. Achieves a net result of sending a transaction from an address without knowing it’s private key. Not overwhelming useful, but interesting nonetheless.


texts: What packages do I need to import if I would like to run a ntruencrypt source code in Java?


texts: Indistinguishability Obfuscation : What are it's consequences on crypto?

texts: I was reading about the construction of IO using MIFE and compact FE . I am just curious to know what are the consequences if there exists an IO.


texts: What security flaw exists in MAC authentication scenario?

texts:
What security flaw exists (if any) in the solution of this non-encrypted authentication scenario?

An unencrypted message passes one-way from computer A to B. Its transmission is viewable by the public. The message does not need to be kept secret. Both A & B have already securely exchanged any needed keys. A and B keep their keys secret.

Goal:

B needs to authenticate that the message (10s to 1000s bytes) originated from A.
Prevent others from creating a message (other than a copy that A originated) that B would mistake for an authentic message.

Solution (MAC)

A appends a MAC to the message and sends it. B receives purported message and MAC.
B authenticates (or not) the message/MAC. MAC size: about 256 to 512 bits.

Looked over other Q&A, but authentication is so often tied with confidentiality that I failed to find posts that addressed authenticity without a secrecy requirement.

[Edit]

I selected the answer (1 of 2 good answers) that presented the original scenario’s biggest problem: Via comments, it came out that $B$ is really a set of clone $B$s and thus a MAC does not authenticate that the message came from $A$ as it could come from another $B$.  Thus warranting a Digital Signature.

The following points shift the nature of the question but do align with the realities of my particular situation.  There are mentioned here should additional answers wish to address the modifications - which I will review and likely up vote.  I should post a new more clarified question later.

A1. My 1st goal s/b “$B$ needs to authenticate that the message (10s to 1000s bytes) originated from $A$ or from another $B$.”  Thus a MAC appears still OK.

A2. Non-repudiation of a message is not needed.

A3. Each message is complete and is not part of a larger message set (ordering or selective blocking not an issue.)

A4. The size of the MAC (or alternatives) is limited.

Details: There is no wired network.  The messages & MAC are contained in RFID tags.  The message describes a product attached to an RFID tag.  These messages are generated by $A$ "the factory" and distributed, via public means, to various $B$s.  A given machine $B$ may alter the message either with the original MAC or with a new MAC unique to that $B$ machine - TBD.  The product need not move between the clone $B$s.  All this does not authenticate a valid product exists (the product and RFID tag could be separated or the RFID is spoofed). It does authenticate that a valid product’s message exists.


texts: Can I create a fixed length output from a fixed length input?

texts:
I use AES256 for various purposes in my app. However, the purpose I am now trying to achieve is the following:

Input is for example AU00000001 and I would like a hashed or encrypted output of this with the same length (10 characters). I need to keep the output as small as possible, to convert it into a simple (minimal dots) QR code. And I do need the ability to reverse that output back to the original input.

I've read a few posts around here but I can’t find what I am looking for. Can you give me a hint or maybe point me to some references?


texts: Problem with Chaum`s Untraceable Electronic Cash

texts:
For example according to protocol I need calculate this:

$b=F^{(1/h)} \bmod pq.$

Where $p$ and $q$ are prime numbers. I have $F$ and $h$. But how can I calculate $b$?

I tried to do this:

$\text{temp} = h^{-1} \bmod((p-1)*(q-1))$

and then

$b=F^{\text{temp}} \bmod pq$

But the problem is that

$h^{-1} \bmod((p-1)*(q-1))$

does not always exist, sometimes $\text{GCD}(h,(p-1)*(q-1))$ is not $1$.

Is it supposed to be like that or do I need to calculate it in a different way?


texts: Dividing a point by a specific number in elliptic curve


texts:
I'm trying to solve a question about one time pads but I'm not sure if my assumptions are correct.

I am to assume that I have a one time pad with perfect secrecy. This one time pad is used to encrypt a message of 7 bits in length (message space size is 2^7). This encryption yields a ciphertext of "0110011". What is the probability that the encrypted message was "1001001".

My understanding of one time pads is that if we assume the pad has perfect secrecy, then we can no nothing about the message given the ciphertext and thus we cannot determine the probability. Am I right in my assumption?


texts: CRC32 vs. low 32 bits of cryptographic hash

texts:
I was having a discussion with a colleague yesterday whose education and experience exceeded mine.  He said something yesterday that sounded incorrect to me intuitively, but I don't have the knowledge to contradict it.

He claimed that the only reason a secure cryptographic hash is better at detecting tampering or corruption is because it has more bits in the output (e.g. SHA-256 has a 256-bit output vs. CRC32's 32-bit output).  Right now, we're only talking about detecting corruption/tampering, not recovering data.

My intuition tells me that given the choice of CRC32 or SHA256 (and taking only the low 32 bits), the hash is going to be much more secure as far as detecting changed bits (particularly in the face of a malicious and intelligent attacker, but even due to corruption in "just the wrong way").

Can someone either tell me why I'm wrong & the 2 are essentially equivalent, or support my intuition with math and or proof/reasoning?


texts: Purpose of signing the signed prekey in X3DH?

texts:
I'm trying to understand the X3DH protocol used in Signal and many other end to end encrypted messaging apps. There are other questions on this site asking about why the signed prekey exists. I'm asking why the prekey need to be signed.
In section 3.3 of the specification, 4 (3 if the one-time prekey is missing) Diffie-Hellman exchanges are done. DH1 involves the identity key of one user, and DH2 involves the identity key of the other user. The SK is derived from these exchanges in addition to the other exchanges that do not involve identity keys. Notably, DH4 is computed without involving any identity key or signed key.
How does any security property of X3DH change if the signature on the signed prekey is not validated?


texts: Sorry if my question is trivial. My question is related to a post "Paillier Homomorphic encryption to calculate the means" where a member suggests Lagrange Gauss Reduction Algorithm for reducing a decrypted value to a rational number. How to use Lagrange Gauss Reduction Algorithm for reducing numbers? Here is the link to the original post: Paillier Homomorphic encryption to calculate the means.


texts: How big are the primes used in modern cryptography?

texts: I know that this depends on which techniques you're using, but roughly speaking, when modern cryptography makes use of so-called "large prime numbers", how large (in bits or digits) are these primes typically?


texts: Difference between "Signature Algorithm" and "Signature Hash Algorithm" in X.509

texts:
What's the difference between the "Signature Algorithm" and the "Signature Hash Algorithm" found in an X.509 certificate? Why does it need a "Signature Hash Algorithm"?

Edit:

I'm creating the X.509 cert with PHP 5.2. When I change the 'digest_alg' to 'md5', both properties of the Microsoft Cert Tool changes to md5. So, as mentioned in one answer below, it seems to be an issue/invention of the Microsoft Cert Tool.

Change to md5:

           $configs = array(
                            'config'             => 'test.cnf',
                            'digest_alg'         => 'md5',
                            'x509_extensions'    => 'v3_ca',
                            'req_extensions'     => 'v3_req',
                            'private_key_bits'   => 2048,
                            'private_key_type'   => OPENSSL_KEYTYPE_RSA,
                            'encrypt_key'        =>
                        );

Result:


texts:
AES and DES are block ciphers. Mathematically, its the mapping from plaintext space to ciphertext space using the keys i.e. $\{{0,1}\}^k$ x $\{{0,1}\}^l \longrightarrow \{{0,1}\}^l$

I know that these keys are random. What I want to know is how these are calculated in real world and is there any way to change these keys meaning that is it possible for me to use my own keys in these block ciphers?


texts: Same 64-bit preimage resistance security for SipHash and SHA-512/64?

texts:
If I have to chose a 64 bit preimage resistant hash function; will there be any difference in security between

SipHash and
SHA-512/64 (SHA-512 truncated to 64 bits)?

How long will it take an attacker to find a 64 bit preimage (e.g., minutes, weeks or years)?


texts: Encrypt with one cipher and decrypt with a different cipher?

texts:
I recently installed an android app called Secret Space Encryptor and think I found a serious flaw in it.

Let me explain: This app provides a variety of different ciphers to use and I used Threefish 1024 to encrypt a test message with "Your Key" as the key.

I then saved the ciphertext to a text file using the export function in the app. Then I changed the text encryption program in the app to use Blowfish 448 and imported the TF-1024 encrypted message into the app once more.

I then entered the "Your Key" test key and to my total surprise the message successfully decrypted! I encrypted a message with one cipher and then decrypted that same message with a totally different cipher!

Now this should be totally impossible right? If so then is there a deadly flaw in this app?


texts: Difference between a circuit and a normal function

texts: I've seen the word circuit used in many crypto contexts (for example, regarding FHE in this pdf). I've always thought of a circuit as another word for a program or function. But is there a difference - i.e., is there something that a standard function can do that a circuit can't?


texts: Did Merkle invent cryptographic hashing?

texts: Chapter II of Merkle's 1979 PhD thesis is titled "One Way Hash Functions." The chapter appears to be the first reference to cryptographic hashing. The chapter has no references. Is there an earlier reference that I am not aware of?


texts: What is a branch number in the PAEQ algorithm?

texts:
I'm reading an article about authenticated encryption algorithm - PAEQ.

It uses a permutation function AESQ, which has transormations from AES. And there is written about MegaSBoxes, which contain 4 rounds of AES transformation. So, there are 1 active MegaSBox in 4 rounds and 5 active MegaSBox in 8 rounds (because of branch number - 5).

So, the question is what is a branch number and why there are 5 MegaSBoxes, not 2?

More info in this paper (section 3.2.3, after lemma 3).


texts: How does a key wrapping like RFC 3394 secure my cryptographic keys?

texts:
So I'm messing around in the BouncyCastle library with the RFC 3394 AES Key Wrap engine and I'm trying to understand the benefit of it.

The problem I'm running into is how to store keys securely on a device like a phone or even a laptop or desktop. I need to wrap the keys so that anyone snooping around in memory can't just get those keys. RFC 3394 looks as though it's designed to help with that issue.

I can just do

$$ \bar k = \operatorname{wrap}_{k^*, IV}(k) $$

and store $\bar k$ instead of $k$, and use

$$ k = \operatorname{unwrap}_{k^*, IV}(\bar k)$$

to retrieve $k$ again when I need it.

I've written this code in C# to test it out. This seems to work okay, except for the fact that I'm trying to understand how this is more secure. At some point I have to store the key encryption key $k^*$ in memory, and it seems to me that any hacker who could get their hands on $k^*$ now has their hands on the encryption keys.

So how does this secure the encryption keys in memory?


texts: Many consecutive hashes to slow down brute force attack?

texts:
I've heard that hash algorithms like bcrypt are more secure because they take longer to complete, and therefore take much longer to brute force, without a noticeable delay for legitimate users. Would using a faster algorithm, such as SHA-256, multiple times, be secure? For example:

hash = "password"
for x in range(5000):
    hash = hashlib.sha256(hash).hexdigest

As it has to hash the data, then hash the hash, and so on, taking much longer than a single SHA-256 hash, wouldn't this accomplish the same thing?


texts: scientific research about what is more secure: biometric authentication vs regular

texts:
I've already posted this question on Stackoverflow, but got downvoted and told to post here instead. So here we go.

I am searching for citeable sources / papers that research about what is more secure in general: biometric authentication (something like touchID) in smartphones vs regular authentication (passwords, pincodes). I am looking for papers that actually come to a conclusion instead of answering the question with more questions. Surely this has to be measureable, since both are different types of authentication?

So far i googled on google scholar, but couldnt find any useful stuff. Any one else any idea?

Thanks!

Original post: https://stackoverflow.com/questions/42428372/scientific-research-about-what-is-more-secure-biometric-authentication-vs-regul


texts: OpenSSL block ciphers return length of the text as output of the encryption (envelope_seal()), and If I have to send the length over network, I append the length with the ciphertext as I can transmit only one field and envelope_open() needs the length of the ciphertext. Is there any other way that I can calculate the length of the ciphertext, which contains null terminated characters, on the receiving side?


texts: What is the size of a 1024-bit RSA cipher compared to its plaintext?

texts:
Let's assume we encrypt a 50000 bit plaintext with 1024-bit RSA and public exponent $e$ = 3: How big will its cipher be?
When we increase the exponent to let's say $e$ = 216 + 1 = 65537, how big will its cipher be then?


texts: How to forge a signature in a custom PMAC implementation

texts:
From a crypto challenge i have the following PMAC variant where the task is to forge a signature to fulfil a specific condition:

Preparation:
in the finite Field GF(2^128) with the polynomial x^128 + x^7 + x^2 + x + 1 as modulus we generate the PMAC-L constants like that:

L(0)=AES(0) -> standard AES-128 with a random fixed key K and the all 0 plaintext as input

L(i) = L(i-1) * 2  -> for i=1..257 the actual L is just the L before multiplied by 2 (decimal)

The MAC:

we have a fixed block of 4096 bytes, which is filled with all 0
we can copy an arbitrary text/bytes of up to 4095 bytes into that block for testing
the block is then split into 256 * 16 byte messages and processed like

S = 0

for i from 1..257 do S = S + AES(L[i] + M[i-1])  (+ means here addition in GF(2), xor otherwise)

final step: H = AES(S)

H is the 128 bit MAC then
we can do 511 queries to an oracle with that setup
no message padding is performed, just always processing all 256 16-byte  message blocks
the oracle gives us only the 16 byte MAC as result of those operations

The challenge:

we have to to fill that 4096 bytes bufffer in such a way that the resulting hash is the same as AES(0). Some fixed 27 chars text is copied into the start of the buffer before, the remaining space is at our disposal.

I cannot see any angle of attack for a forgery, cause the only access for results is the result after that last AES step H = AES(S). And the only input available are the message blocks.

i think its ok to assume we aim at

AES(0) === AES(S) which would result in the condition
S === 0 ?

if there would be any way to know the results of single hashes like
AES(L[i] + M[i-1]), one could construct a basis of a vector space, and
maybe construct an arbitrary value which cancels out the result to 0 in the end - but this information is not available

I would be very glad about ANY pointer in ANY direction - thanks

PS: please dont be harsh with me when i used some mathematical terms not in the correct way


texts:
From what I could find it relates input differences to output differences usually across multiple rounds.

But is it the entire probability distribution over all output differences for one input difference? Or is it the list of differences that produce the output difference with the highest probability?

What is the exact definition of differential trail?


texts: Crypto++: How to re-generate pseudo random integers in Crypto++

texts:
I'm using Crypto++ to implement my protocol to mask a value $y_i$ by a pseudo-random value $r_i$ such that $m_i=y_i \cdot r_i$. Since there are many $r_i$'s I want to generate them using PRNG and then only store the seed for the PRNG. With the seed any I can regenerate $r_i$, then compute $r^{-1}_i$ to remove $r_i$'s. But in crypto++ the seed (key) cannot be accessible.

So my question is: how can I use PRNG of crypto++ to accommodate the above technique?

Let $r_i  \stackrel{R} \leftarrow \mathbb{Z}_p$ and $y_i \in \mathbb{Z}_p$, where p is a prime number.


texts: Combining LFSRs for Stream Ciphers: Why do we need high non-linearity?

texts:
Linear Feedback Shift Registers (LFSRs) can be excellent (efficient, fast, and with good statistial properties) pseudo-random generators. Many stream ciphers are based on LFSRs and one of the possible designs of such stream ciphers is combining outputs of $m$ LFSRs as input of a boolean function $f:GF(2)^m\rightarrow GF(2)$. This last function has to be carefully selected.

My question is a rather elementary one. I understand that using one LFSR to produce the keystream is not appropriate as one can create the whole keystream by knowing a tiny fraction of it: if the tap positions of a length $n$ LFSR are known, one needs $n$ bits to determine the entire keystrem sequence, and if they are not known, one needs $2n$ bits (by using the Berlekamp-Massey algorithm to find out the tap positions). However, why do we need a non-linear combination of LFSRs (among all sorts of other requirements)? What would be the problem of getting a number of LFSRs with appropriate lengths and tap positions and XOR together their output to produce the keystream?


texts: Are there ready-to-use software that can try many decryption techniques on a ciphertext, with no information?

texts:
Let's say I receive a 1 MB encrypted file, but I get no information about the encryption method, and no password.

The only thing I can guess is that the person probably used a weak encryption method on a text file.

Are there ready-to-use software that will perform automatically a huge number of attacks on the ciphertext, from the simplest methods to the most complicated?

i.e. it would start with ROT13 / Vigenere, frequency analysis, etc., then Hill cipher or other easy-to-crack methods, then RC4 (I read in many places it is considered as weak, but I still don't know if one can easily break it if I don't give any other information than just the ciphertext), etc. and it would stop if some text is found (let's say at least 20% of the words are in a big dictionary)

(I can imagine such software would be used by intelligence agencies, etc. because it would speed up decryption.)


texts: How do I calculate CRC32 mathematically?

texts:
I want to calcuate the CRC32 algorithm using polynomials directly but I don't know how. I found the generating polynomial listed here https://en.wikipedia.org/wiki/Cyclic_redundancy_check. This corresponds to 0xedb88320 in the example code.

Can someone please define a mathematical specification that calculates the same result as this algorithm?


texts: I am trying to implement TLS v1.1 {3,1} but get alert 70 on hellomessage to goolge

texts:
I am trying to implement TLS on top of the winsock api's from windows. I am using port 443 and have created a socket. I have sent this message

in decimal.

22 3 1 0      112 1 0 0
108 3 1 48    227 142 116 0
1 4 9 1       25 4 17 0
17 4 25 16    9 4 1 0
1 4 9 16      25 4 17 0
17 14 25 16   0 0 68 192
10 192 20 0   136 0 135 0
57 0 56 192   15 192 5 0
132 0 53 192  7 192 9 192
17 192 19 0   69 0 68 0
51 0 50 192   12 192 14 192
2 192 4 0     65 0 4 0
5 0 47 192    8 192 18 0
22 0 19 192   13 192 3 254
255 0 10 10

The response is

21
3
1
0
2
2
70

This is the char* or string I am passing to winsock as the message, so that would imply this is my ciphertext simply with the null stream or block cipher which is the identity map of the plaintext fragment and with no MAC. As is the record state on the initial client hello message, the first step in the handshake. Perhaps I am getting the length wrong,

If the CipherSuite is TLS_NULL_WITH_NULL_NULL,
   encryption consists of the identity operation (i.e., the data is not
   encrypted, and the MAC size is zero, implying that no MAC is used).
   TLSCiphertext.length is TLSCompressed.length plus
   CipherSpec.hash_size.

I can not find the definition of CipherSpec.hash_size in the request for comments on TLS 1.1?

Also I have tried different versions to no prev ale. Perhaps someone can look through my encoding  below and see if there is a problem? Other then an encoding issue I can only suspect that google.com does not take TLS on port 443 but instead an http upgrade to TLS on port 80? https://tools.ietf.org/html/rfc2817


texts: What is the linear complexity of a modified LFSR sequence with a fixed length of zeroes inserted between every pair of successive terms

texts:
There was a deleted question that asked;

We know that if $n$ zeros are inserted between every pair of successive terms of the sequence in LFSR (variable changed $x$ to $x^n$) then linear complexity (shortest LFSR which produces the given seq) will be $n$ times the original one.
My question is that: in the new sequence what is the period (assume period of original one is $p$)

The period was easy to answer;
Let $m$ be a sequence output from $L$ bit maximal LFSR. Then we know that the period of the sequence $m$ is $2^L-1$
Let $m'$ be the modified sequence of $m$ such that for every two successive elements $n$ zeros are inserted. An example with $n=3$
   m  = 1   1   0   1   1   0   1
   m' = 1000100000001000100000001000

It is obvious that the period of $m'$ is $(2^L-1)\cdot n$. One can prove this with a counter-argument; if the period is smaller, then remove the added zeroes to find a smaller period for $m$.
What about the linear complexity?
I couldn't see a general rule for this; My was example already a counterexample for the multiple; run with SageMath code the online;
[1,1,0,1,1,0,1,1] has x^2 + x^1 + 1
[1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0] has x^8 + x^4 + 1

and for the $n=1$ case;
[1,1,0,1,1,0,1,1] has x^2 + x^1 + 1
[1,0,1,0,0,0,1,0,1,0,0,0,1,0] has x^4 + x^2 + 1

[1,1,0,1,1,1,1,1] has x^4 + x^3
[1,0,1,0,0,0,1,0,1,0,1,0,1,0] has x^7 + x^5

Is there a work or a result on the bounds of the Linear complexity of $m'$ related to $L$ and $n$?


texts: Is a Qualified Digital Certificate backward compatible with existing certificate code?

texts:
I'm trying to determine if our digital signature generation code will work without change using a European Qualified Digital Certificate in place of the RSA signing certificate that we normally use.

It seems like the structure of the qualified certificate is the same as any other signing certificate, but has special rules around how it is generated. If this is the case, then I suppose existing certificate handling code should continue to work. But I haven't found actual confirmation of this theory, and I don't have a QDC in hand to try it.

The code in question is a Windows-based C++ application using the Microsoft Cryptography API functions. I also asked the question with code example on stackoverflow.com.

Anybody have experience with this?


texts:
I've just studied about the error correction schemes and encryption.

First rule when using EDC/ECC is to first encrypt and then calculate them, and the major motivation we were told is that "EDC/ECC Then Encrypt causes KPA attacks on GSM protocols to be Ciphertext Only Attacks, because it adds much redundancy to the plaintext". source (slide #50)

However I couldn't find any example or explanation for that, so I'd appreciate any help regarding this.


texts: Using "Additional Authenticated Data" as a secondary key

texts:
In implementing a cipher in GCM or CCM mode, you are provided the option to add "Additional Authenticated Data" (AAD). This AAD is required for decrypting the cipher text, and seems to be used when data is crucially specific to a label.

EDIT: to clarify, an example of when it might be used that I have seen is if you want to encrypt the number of shares of a stock that has been purchased, but need to make sure that that number corresponds to the correct stock you would use an AAD containing the name of the stock.

What I am wondering is, could you use this AAD as a secondary key and simply keep it secret?

Thanks


texts:
I'm having trouble with a definition in the HQC Specification.
From page 25f., in section 2.5.5.:

What does it mean to duplicate a code? Is it repeating each bit, similar to a repetition code?
Further, I don't understand the type of the function $F$: $\mathbb{F}_2^7 \to 3, 1, -1, -3^7$.
Is this a typo, and it should map to $\{3, 1, -1, -3\}^7$ instead?
What do they mean by

where we started with transforming each block of three bits $x_1 x_2 x_3$ of the received vector in $(-1)^{x_1} + (-1)^{x_3} + (-1)^{x_3}$

?
Assuming this is the definition of $F$, I don't understand why $F$ takes 7 bits as input, instead of 3.
Should $F$ have the type $\mathbb{F}_2^3 \to \{3, 1, -1, -3\}$ instead? (Note the removed $\cdot^7$ and changed input space)
In section 2.5.7. they go through an example with multiplicity of 2 (instead of 3 like above):

Is this code equivalent to the concatenation of a repetition code and a Reed-Muller code? (where concatenation is what they define in def. 2.5.1.)
Thanks a lot in advance!


texts: Understanding certificates for public keys with subkey

texts:
I have a openpgp key with 3 subkeys:

> gpg --list-keys
<keyring-location>
-------------------------------
pub   rsa4096 2017-05-19 [SC] [expires: 2019-05-19]
      <key-id>
uid           [ultimate] <my-name> <my-email>
sub   rsa4096 2017-05-19 [E] [expires: 2019-05-19]
sub   rsa4096 2017-05-19 [S] [expires: 2019-05-19]
sub   rsa4096 2017-05-19 [A] [expires: 2019-05-19]

My goal: I want to create a certificate for my pulic key for authentication with strongswan.

Now when I export the key, I get:

> gpg  --armor --export <key-id>
-----BEGIN PGP PUBLIC KEY BLOCK-----
...
-----END PGP PUBLIC KEY BLOCK-----

My questions:

What is a public key block? Does it contain all my public keys?
How can I extract the public key of my authentication key so that I can create a certificate for it?
If I have a certificate, how can I check if it is for the authentication key?


texts: Standard parameters for Boneh–Lynn–Shacham signature?

texts:
The Boneh–Lynn–Shacham signature is (as far as I know) unrivaled in compactness, promising $b$-bit security for $2b$-bit signature (perhaps: asymptotically).

Are there standard parameters for BLS signature, (being?) defined by standard bodies, security authorities, or other recognized authority; or otherwise common/recommended?

In particular, is there something with a size recommendation, perhaps in ISO/IEC 15946-5: Information technology - Security techniques - Cryptographic techniques based on elliptic curves - Part 5: Elliptic curve generation?

What does the state of the art ([BD 2019] I guess) implies about the size of BLS signature for $b$-bit security, for practical $b$ like 128?

Some references (now dated except the last two) :

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

[BN 2005]: Paulo S. L. M. Barreto, Michael Naehrig, Pairing-Friendly Elliptic Curves of Prime Order, in proceedings of SAC 2005; slides.

[SSS 2006]: Mike Scott, Hovav Shacham, Terence Spies, P1363 presentation of 2006/10.

[NNS 2010]: Michael Naehrig, Ruben Niederhagen, Peter Schwabe, New software speed records for cryptographic pairings, in proceedings of Latincrypt 2010; software linked at referring page.

[ABLR 2013]: Diego F. Aranha, Paulo S. L. M. Barreto, Patrick Longa, Jefferson E. Ricardini, The Realm of the Pairings, in proceedings of SAC2013, with slides (reporting actual use since 2002).

[KB 2016]: Taechan Kim, Razvan Barbulescu, Extended Tower Number Field Sieve: A New Complexity for the Medium Prime Case, [KB16] in proceedings of Crypto 2016, originally [K 2015] of October 2015 and [B 2015] of November 2015.

[BD 2019]: Razvan Barbulescu, Sylvain  Duquesne, Updating key size estimations for pairings, in Journal of Cryptology, October 2019


texts: How close is homomorphic encryption to handling regular expressions?

texts:
Is there any reasonable homomorphic encryption protocol that supports some meaningful fragment of regular languages/expressions and/or edit distance bounds?

I'm suspicious that homomorphic encryption never handles this sort of "insert bounded amount of arbitrary garbage", but maybe a subset of regular expressions with various bounds, or perhaps up to some bonded edit distance.

This question came up in a discussion about CryptDB.


texts: Does brute force attack use the program that created the ciphertext?

texts:
I've read several articles about brute force cryptanalytic attacks, but none explicitly say what algorithm is being run for each attempt, nor what criteria is used to declare an attempt a success or a failure. If one is to try every possible every possible key value, what is one feeding those keys into? A brute force attack on a block of ciphertext implies that the cryptanalyst treats the cipher as a black box. Does the cryptanalyst have the block box and are they able to drive the black box?

Say, for example, that someone uses a GUI application that takes a file and a password as input and produces an encrypted file as output. The intended use would be for the receiver to use the encrypted file and the password to get the cleartext file as output. Is this same GUI application somehow driven by the cryptanalyst's brute force application to try every possible password? Most GUI programs are not fast enough to run billions of times in a reasonable period. Add to that the fact that most encryption is compute-intensive and can be made slower to prevent such an attack.


texts: Is it possible to crack AES 128 key if one can use the key to encrypt arbitrary data block?

texts:
I know for now practically it is impossible to crack AES 128 key by brute-force attack.

But is it still true if one has the key and can repeatedly use it to encrypt or decrypt arbitrary data block? In another word, given any clear text A, they can get the cipher encrypted with that key.

Is there a term referring to this kind of crack which is 'crack key with the ability to encrypt arbitrary data block by the key'?

Thanks


texts: Gennaro multi trapdoor commitment scheme

texts: In the Scheme Based on the SDH Assumption (page 11 of the paper https://link.springer.com/content/pdf/10.1007%2F978-3-540-28628-8_14.pdf), how does the commitment get revealed with the master trapdoor x?


texts: Key derivation functions (KDF): What are? Main purposes? How can they be used?

texts: What are KDFs? What are their main purposes? How they can be used, in other words, what's their drill in a cryptography scheme?


texts: NIST elliptic curves behaving anamolous in OPENSSL benchmark

texts:
I tried to collect some benchmarks on NIST elliptic curves using charm library. The charm library is just a wrapper over OPENSSL. I experimented with prime192v1 (P-192), secp224r1 (P-224), prime256v1 (P-256), secp384r1 (P-384) and secp521r1 (P-521) curves. I calculated the time required to

(1) sample one group element,

(2) multiply 2 random group elements and

(3) exponentiate a group element with a random value in range [1, order of group].

Here's my code.

from charm.toolbox.ecgroup import ECGroup, G, ZR
from charm.toolbox.eccurve import prime192v1, secp224r1, prime256v1, secp384r1, secp521r1
from time import time
group = ECGroup(secp521r1)
count = 10000

g = []
a = []
t = time()
for i in range(count):
    g.append(group.random(G))
print("Random in G ", time()- t)

for i in range(count):
    a.append(group.random(ZR))
t = time()
for i in range(count):
    g[i]**a[i]
print("Exp in G ", time() - t)

t = time()
for i in range(count):
    g[i]*g[i-1]
print("Mul in G ", time() - t)

Here are the results. The benchmarks have many anamolies that I could not explain. For P-224 curve, it took unreasonably long time for sampling random element. For P-224 curve, if it takes 2.27microseconds for multiplication, then it should take at least 224*2.27microseconds (roughly 0.5ms) for exponentiation. But exponentiation is much faster. Exponentiation is unreasonably faster even for P-256 and P-521 curves as well. Can anyone please explain why this is the case?


texts: New to cryptology, studying key exchange

texts:
I'm just getting an overview of some of the concepts in key exchanging at the moment, and I'm a bit disoriented on a few topics, namely key stretching, key derivation functions and perfect forward secrecy.

Regarding key stretching, I understand the idea is to make it more difficult to brute-force a password, but the materials I'm reading come a bit short on any kind of technical explanation.  The wikipedia article makes it sound like all it does is feed a plain text passphrase through a hashing algorithm.  If that's so, why differentiate between hashing and key stretching?  Does a salt count as a method of key stretching?  What are other methods?

About key derivation function, I understand the whole thing that there is a master key and session keys are derived from that.  But what is the specific application of key derivation?  Is it closer to key agreement (Diffie-Hellman) or key exchange (PKI)?  Can you cite a real-world example where I might encounter key derivation? (For instance, I know that if I wanted to secure a tunnel through IPSec, I might use IKE, which means I'd be dealing with Diffie-Hellman, which is key agreement.)

I think I'm pretty well grounded on Perfect Forward Secrecy; it's basically the diametric opposite of key derivation.  But I'm hazy on the difference between Forward Secrecy and Perfect Forward Secrecy.  What exactly changes the situation from FS to PFS?

I know these must be very basic questions for this forum, but I'm just getting my feet wet in the world of cryptology.


texts: Extra attributes in a certificate signing request

texts:
When creating a certificate signing request, there is a part where openssl says "Please enter the following extra attributes to be sent with your certificate request". One of these is a challenge password.

Under what circumstances will this password be needed?


texts: Security of (cryptographic) padding compared to other methods for blockcompletion for block ciphers

texts:
As said in the heading, I want to know how the security of different padding methods, e.g. ANSI X.923, ISO 10126 and PKCS7, is compared to other methods to reach the needed block size, like ciphertext stealing or residual block termination. And what is about the counter mode of operation?

I heard that oracle attacks are possible if padding was applied, but have the other methods also disadvantages (except a higher complexity)? Or are there any possible ways for the problem that I forgot, that are more recommended?


texts: Small roots of bivariate modular linear equation?

texts:
Say I have a simple affine relationship between two variables $x$ and $y$ in a field $\mathbb{F}_p$ ($p$ is a large security parameter): $ax + by + c = 0$

What algorithm would be appropriate to find all roots $(x,y)$ such that $x < X$ and $y < Y$ for some small $X, Y$ compared to $p$?

Every algorithm I find seems like overkill, dealing with systems of several equations, higher degree or more variables. Would Coppersmith method still be the best here? LLL can be used to find one root but I don't see how to find the other ones.


texts: OTP Scheme where only one party can generate the OTP, but both parties can verify it's validity

texts:
As far as I understand, OTP usually works on a superficial layer by having two parties both know of a key and then authenticate each other by sharing a hash of the key and some sort of counter (e.g. currentTime mod someNumber) with each other. In theory, this means both parties can verify each other, as both have the capabilty to generate a OTP and both have the the capability to verify the integrity OTP given to them.

I'm looking for an OTP scheme between two parties where both parties can verify the validity of an OTP, but only one party can generate it. To my understanding, this would not work with the logic described above. Does such a protocol already exist? If not, is such a system even mathematically realizable?


texts: The aftermath and considerations of the new record of 30750-Bit Binary Field Discrete Logarithm - 2020

texts:
Granger et al. recently published a paper about breaking a record for discrete logarithm on the Binary field

Computation of a 30 750-Bit Binary Field Discrete Logarithm, Robert Granger and Thorsten Kleinjung and Arjen K. Lenstra and Benjamin Wesolowski and Jens Zumbragel, August 2020

They computed the discrete log of $\mathbb{F}_{2^{30750}}$ on 2900 core year of single-core of Intel Xeon Ivy Bridge processor running at 2.6 GHz. The previous record was $\mathbb{F}_{2^{9234}}$ and required 45 core years.

Discrete Logarithms in $\operatorname{GF} (2^{9234})$,  Robert Granger, Thorsten Kleinjung, and Jens Zumbrägel. 2014.

The field $\mathbb{F}_{2^{30750}}$ is extended as $\mathbb{F}_2: \mathbb{F}_{2^{20}}:\mathbb{F}_{2^{30750}}$
To find the discrete logarithm, they select the target element $h_\pi$ by using the digits of $\pi$, as not to be "cooked up", see nothing-up-my-sleeve number
Questions:

What is the aftermath of this work for Cryptography? (DLog is not restricted to Cryptography)

The binary extension field is not a nothing-up-my-sleeve number. They choose $30750 = 3 \cdot 10 \cdot (2^{10}+1)$, i.e it is in the form $\mathbb{F}_{q^3(q+1)}$ so that they can use the twisted Kummer extension. It is mentioned in this case it is much easier than other extensions of the same order of magnitude. It is clear that not every extension can be a Kummer extension.

How much easier?
On what magnitude do the non Kummar extensions safer?

The group order of the extension is $N:= 2^{30750}− 1$ and it has 58 prime factors up to 135-bit size.

Is a binary extension field with fewer prime factors safe?
Is one with a large factor is still safe?

What is the fixed characteristic (mentioned on page 3)?
It turns out that fixed characteristic is used for the computational complexity calculations. A nice explanation is given in here;
Let $\le C2^pk^r$ be the cost of an algorithm, over a field of characteristic $p$ and size $k$ for some constants $C,r$. We say that it is polynomial for fields of fixed characteristic but exponential in the characteristic.


texts: I've begun a course in crypto on coursera and the first homework was writing a vigenere(xor) cracker. It works, which was a rush :) but it makes one core assumption, one has encrypted a natural language text that the script can use frequency analysis on. Therefore doesn't work if one encrypted an image or a compressed file. How does one do it if frequency analysis isn't an option?


texts: Are MAC algorithms and digital signatures secure from quantum computers? If not, why?

texts:
I understand that asymmetric encryption is fundamentally deemed useless under Shor's Algorithm, and understand that symmetric encryption is somewhat quantum-resistant as long as the key-length is equal or above 192-bits.
MACs are symmetric cryptographic primitives, however, I have heard that they may be insecure due to the key exchange.


texts: Secret sharing between a very large number of participants

texts:
What can be a method for sharing a secret between a large number of participants?

With Shamir's Secret Sharing (k,n), n can be arbitrarily large, but increasing k increases the complexity of the keys generation.

Is there an algorithm that can realistically generate keys for value of k between 1,000 and 1,000,000?


texts: Regain 3DES ECB key, assuming I have both encrypted and decrypted text

texts: Let's assume I've encrypted some text with some 24-byte key using 3DES in ECB mode. Is it possible to regain the key if I have both encrypted and decrypted text? (Excluding bruteforce.)


texts: Outsourcing arbitrary computations securely

texts:
Consider the following scheme. Alice wants Bob to make some computations for her, but she doesn't want to reveal the data on which he's going to do it. So, she encrypts the data, sends them to Bob, he makes some (Turing-complete) computations on them, and sends an encrypted answer. For example (C++-like pseudocode)

// Alice: range of numbers (ideally, 2^32 for int's)
const int max = 117
// Alice: ready some inputs
int a = 3, b = 5;
// Alice: ready some random keys
int ra = rand() % max, rb = rand() % max;
// Alice: encrypt inputs
int ea = (a + ra) % max, eb = (b + rb) % max;
// Bob: compute sum of inputs
int er = (ea + eb) % max;
// Alice: decrypt result
int r = (er - ra - rb + 2 * max) % max;
// Alice: yeah, it was 8!
cout << r << endl;

Mention that neither Bob has access to inputs and outputs, nor there are some unencrypted data used in process. Though, such a scheme has several drawbacks:

Obviously, we shouldn't use modulo of rand that simply, because in current implementation it prefers some results over others.
The data are not that much encrypted, because their distribution didn't change.
To compute some arbitrary function Alice and Bob should send the data for each operation, while ideally there should be only two: Alice sends inputs, Bob responds with outputs. Possibly, this could be solved by sending a seed for PRNG, generating "salt" for single steps of computation.

Such kind of computations must have already been studied somewhere, though I don't know, how they're called. Could you suggest some good keywords and sources to start with?


texts: Calculate private key from public key and r

texts:
I watched this video where somebody finds bitcoin wallet private keys using only the "sigR" value and the public key using a python script named "formula".
How does this work and does converting the values to decimal help somehow?


texts: Building index for Bloom filter using cryptographic hash functions

texts:
I want to apply this secure index scheme for my Bloom filter, i.e. to use secret keys to insert items into the filter. In the paper to insert a word $w$ to the Bloom filter, they use a set of $r$ keys $\{k_1,...,k_r\}$ and calculate $r$ values $h_1 = h(w,k_1), h_2(w,k_2),...,h_r = h(w,k_r)$ as the bit positions. Actually I don't quite understand how the bits are really obtained from the hash values, let's say my filter has 1024 bits, should I use $h_r \% 1024$? And now since I want to reduce the computation, I use only 1 key $k$ and divided the value $h(w,k)$ to $r$ chunks of 10 bits. The value of each chunk will serve as 1 index. Will this scheme make my bits less uniformly distributed?
EDIT: added more information


texts: Eavesdropping experiment with private key

texts:
I am extremely new to cryptography, still trying to learn basics. I got stuck in the following example of an eavesdropping experiment with a private key.

$$\begin{array} {|r|r r r|r|}
\hline
C & & & & A \\
\hline
k & \leftarrow & Gen(1^{n}) & & \ \\
b & \leftarrow & {0, 1} & \leftarrow [m_0,m_1] \leftarrow & input 1^{n} \\
c & \leftarrow & Enck (m_b) & \rightarrow [c] \rightarrow & output b_0 \\
\hline
\end{array}$$

$A$ succeeds, if $b = b_0$.

Could someone give a basic of what is going on here and point to some resources where I can get the hang of these things?


texts: Can Base64 be seen as a way of encryption if we use different index table?

texts:
As we know, the index table (which maps bytes in [0, 63] to characters) of Base64 encoding is public, so everyone can decode Base64 strings from others.

But what if we use a shuffled index table and keep it secret? Can we see Base64 with this new table as some sort of safe encryption, and the shuffled table as cipher?


texts: Using a single Ed25519 key for encryption and signature

texts:
The libsodium documentation contains a function crypto_sign_ed25519_pk_to_curve25519 that converts an Ed25519 key into a Curve25519 one, so it can be used for both key exchange/encryption and signing:

"Ed25519 keys can be converted to Curve25519 keys, so that the same key pair can be used both for authenticated encryption (crypto_box) and for signatures (crypto_sign)."

The same page ends "Notes: If you can afford it, using distinct keys for signing and for encryption is still highly recommended."

My question is whether reusing an Ed25519 keypair for both uses has been proven secure anywhere, for example in the sense of Joint Security of Encryption and Signature or a similar paper?

The two constructions seem to be:

EdDSA signature (i.e. "Schnorr signature done properly")
Ephemeral DH key exchange using a one-time keypair on the sender side and the recipient's public key (mapped to Curve25519).

Both involve a one-time ephemeral keypair and a hash function, I'm fine with the random oracle model (so we can assume the EdDSA nonce, which is actually a function of the key and message, is really random) and one can get domain separation by including a separation tag in the key exchange, i.e. when Alice wants to send a file to Bob whose public key is Q, she picks a pair (r, r.P) and sets the key as k = H(r.Q, "this is a key not a signature") or something similar.

Intuitively this should be fine in the random oracle model; has someone actually (dis)proved it though?


texts: Looking for a group where multiplicative inverse is hard but calculating multiple pairwise inverses is easy

texts:
I have an equation that comes up in trying to do an Attribute Based Encryption scheme, where users have certificates that sign off on attributes that are also watermarked.  I perform a division to ensure that all attributes came from the same certificate.  Each user will have a different $w_x^{-1}$ (unwatermark), but only the CA knows $w_x$ (the watermark)

$$(f0_a * (a * z * w_x) + f0_b * (b * z * w_x)) \times w_x^{-1} = (f0_a * a + f0_b * b) * z$$

Nothing necessarily commutes.  Only the CA can calculate a $w$.  But for every user, they have a different $x$.  I think this rules out RSA because $w_x$ and $w_y$ would have a different RSA modulus.  But I want every user to calculate the same value $(f0_a * a + f0_b * b) * z$ in the end.  That would basically be an AES key for a case of two "signed" expressions (a and b are signed by CA via multiplication by z).

The question is... if not RSA, then what system?  My understanding is that the value would not come out the same for $w_x$ vs $w_y$ even though algebraically, it cancels out.

Or maybe something more subtle... like use RSA to generate $w_x$ and $w_x^{-1}$, and just use the modulus on that multiplication; and a different fixed modulus for the other times operators.

Is there insight on what group would be appropriate for this?

If its commutative multiplication, I think that's ok here (but not required).  But if the user were able to calculate $w_x$ from $w_x^{-1}$, then this scheme falls down.  Same for being able to extract $z$, which is the CA's signing secret.


texts: Correctness of ideal protocol of MPC in presence of malicious adversary

texts:
In presence of malicious adversaries in ideal protocol of Multi Party Computation, how can honest parties get the correct output?
i.e., corrupted parties modify their inputs and give to the trusted party. Trusted Party computes the function by taking honest party inputs and modified inputs of corrupted parties which results in a wrong output.


texts: Retrieve value of private key after encryption with the public key

texts: Is there a way to find an RSA private key after it is encrypted with the corresponding public key? Does there exist an algorithm to recover the private key in this special case?


texts: How does GHASH used in GCM behave as a universal hashing function?

texts:
As per my understanding, a Universal Hash Function isn't a cryptographic hash function & it's output isn't uniformly distributed. However, this is still secure because it's actually a family of functions & one or more of the random inputs to the function decides which function is actually picked from the family of functions & this is what makes it secure.
However, these are the Parameters to GHASH
$GHASH(H, A, C)$ where
$H = E(K, 0^w)$
$K$ is the encryption key & it's fixed, so a new one isn't picked every time, which means $H$ is also fixed.
$A$ is the Additional Authenticated Data
$C$ is the Ciphertext
So how exactly is this a universal hashing function - what is the family & how exactly are we randomly choosing from the family?


texts: Are there security issues with discrete logarithm keys not being uniformly distributed?

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

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

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


texts: Factoring large $N$ given oracle to find square roots modulo $N$

texts:
When $p$ and $q$ are distinct odd primes and $N = pq$, the points in $\mathbb Z_N^\ast$ have either
  zero or four square roots. A quarter of the points have four square roots; the rest have no square
  root. The four square roots of $x\in\mathbb Z_N^\ast$ will look like $\pm a$, $\pm b$. (Of course, $-a$ means $N-a$ since
  we’re working modulo $N$.) Suppose that I give you an efficient deterministic algorithm $S$ that, on
  input $x$ that has square roots, finds some square root of $x$. (If $x$ does not have a square root, it returns
  $\bot$.)

  Use $S$ to make an efficient probabilistic algorithm $F$ that factors $N$. [Hint: If you can find two
  square roots of a number, call them $a$ and $b$, which are not of the form $a \equiv \pm b \pmod N$, then you
  can factor $N$. Show how.] Note: You only get to call $S$ as a black-box, so you don’t know a priori
  which of the square roots it will find.

I am having trouble understanding this homework question, could someone please guide me or give a hint on how to proceed? What I have come up with till now is,
first call algorithm $S$ on some number to find a square root $a$. Call it repeatedly until I get $b$ which is not of the form $a \equiv \pm b \pmod N$. Repeat this for all points.
I am still stuck on how I use this to factor $N$ though.


texts:
Assumes that we have 3 signature algorithms, $S^A$ with key pair $(sk^A,pk^A)$, $S^B$ with key pair $(sk^B,pk^B)$,$S^C$ with key pair $(sk^C,pk^C)$. We denote by $\epsilon$, $\epsilon'$ and $\epsilon''$ the advantages for breaking $S^A$, $S^B$ and $S^C$ respectively, in the sense of weak unforgeability.

I have a composed signature algorithm which works as follows : First we sign a message with $S^A$, then the result is signed with $S^B$, and finally the result of $S^B$ is signed with $S^C$. An adversary can plays to the game in which he can make queries to a composed signing oracle for the signature of messages of his choices.
At the end, the adversay has to find a composed signature for a message which was never queried at the oracle.

Is the adversary advantage bounded by $\epsilon+\epsilon'+\epsilon''+\epsilon \epsilon'+\epsilon \epsilon''+\epsilon' \epsilon''+\epsilon \epsilon'\epsilon''$ ?

I try to construct the proof.. This could be a nice example for me to understand well provable security.

Thank you.


texts: Authenticated Encryption Sheme with Random Access and proven security?

texts:
I am searching for an authenticated encryption sheme with random access and a good performance.
The exact requirements are:
Data to protect: data = data_block_0 || ... || data_block_n
Every data_block has a size of n bytes, 512 for example and the complete data can have a size of many gigabytes.
I search for an authenticated encrypted sheme, which makes it possible to change a data block and update a authentication tag with a good performace.
All authenticated encryption shemes I found (e.g. AEGIS, AES-GCM, Deoxys) uses a chain from data_block_0 to data_block_n to compute the authentication tag. In consequence if I change block_i, I must re computate all blocks with j>i.
A simple approach to realize integrity of the data:
mac_i = MAC(K, blocknumber || block_i || block_length in bytes)
enc_mac_i = Enc(K, mac_i, IV = blocknumber)
mac = Enc( K, enc_mac_0 xor ... xor enc_mac_n xor mac(k, complete length), IV)
This example should demonstrate the requirement, which I need. This approach has many weaknesses.
If I change block_i I must remove the old enc_mac_i from the complete mac with xor and add the new mac with xor. This is possible with a good performance.
Knows anybody an authenticated encrypted sheme, that fullfills this requirment with proven security?


texts:
$A$ sends $B$ the encryption $E_{pkA}(m)$.
$B$ computes $R=xE_{pkA}(m) + y$ and sends $R$ back to $A$, but tells him nothing about the parameters $x$ and $y$.
$A$ performs $D_{pkA}(R)$ and recovers the value $xm+y$.

Is this protocol possible using the Paillier cryptosystem?


texts: Can we get the msg when we know tag and key in Poly1305

texts:
Assume $tag[i]=\operatorname{MAC}(key[i],msg)$

Now we know:

$tag[0],tag[1],\ldots,tag[n]$
$key[0],key[1],\ldots,key[n]$

Can we get the $msg$ from this?

Or can we get the $tag$ of this $msg$ using a known key?


texts: What is a size of mac_length and mac_key_length for TLS cipher suites HMAC using SHA384 and SHA512?

texts:
i failed to find explicit definition of hash output size and mac_key_size for hmac based on SHA384 and SHA512.
RFC5246 specifies:

but defines only


texts: How is the MJH double-block-length hash function constructed?

texts:
I'm looking for information on the MJH double-block-length hash function, but the best free source I could find is the diagram on page 18 of Efficient hashing using the AES Instruction Set (submitted to the ECRYPT II Hash Workshop 2011).

Is source code available for this function? What are the standard symbols used (M, V, Z) when describing hash functions?


texts: RLWE decision to search: probability that oracle work on all automorphic images

texts:
After watching this talk https://www.youtube.com/watch?v=Eg_pyyeT_Qc&feature=plcp, I tried to formalize the presented search-to-decision reduction for Ring LWE, but got stuck at one point.

I understand how we can construct an algorithm that finds the k-th coefficient of the secret (in "Chinese remainder representation", so really $s(\zeta^k)$ with a root of unity $\zeta^k$) for a given k. To do that, we use an oracle that can distinguish between real RLWE samples and uniform ones. As far as I know, this "distinguishing" means that $Pr[O(f, fs + e)] - Pr[O(f, U)]$ is non-negligible, where $f, U, s$ are uniformly distributed random variables on $R_q$. But this would mean, that the oracle and therefore our algorithm* is only guaranteed to find $s(\zeta^k)$ for a non-negligible fraction of all inputs. Using the average-to-worst case reduction, we can make it work for all $s$, but not necessarily for all $f$, so our algorithm may only work on samples $(f, fs + e)$ where $f$ is in some not-too-small set $S$.

My question is now: Is my understanding so far correct, and if it is, how can the automorphism idea (to find the other coefficients) work? If $\sigma$ is a field automorphism that can preserves the error distribution, we know that $(\sigma(f), \sigma(fs + e))$ is also a valid RLWE sample, but it is not guaranteed that the algorithm will work correctly on this sample (it only has to work on a non-negligible fraction of all $f$s). Since $(\sigma(f), \sigma(fs + e))$ and $(f, fs + e)$ are not independent either, the algorithm does not have to work with relatively high probability.

In other words: Why is it impossible, that the assumed oracle distinguishes real RLWE samples $(f, fs+e)$ and uniform samples perfectly for half the $f$ and accepts with probability $0.5$ in the other cases* in such a way that for every $f$ there are automorphisms $\sigma$ (preserving the error distribution) so that the oracle does not work on $(\sigma(f), \sigma(fs + e))$?

I also had a look at this paper (I think the proof has been published there originally) http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.400.7900&rep=rep1&type=pdf, but I did not find details on this question.

(*of course, the oracle is not invoked on $(f, fs + e)$ but rather on $(f + v, fs + e + vk)$, but this should not fundamentally change things)

If my problem is unclear or not formal enough, please tell me. I did not include my complete current proof part as this question is already quite long.


texts: A proposal for randomization of Niederreiter cryptosystem

texts:
The Niederreiter cryptosystem is a public key cryptosystem using Goppa code. Unfortunately it it is insecure unless it is a binary code. So I thought I could insert random linear codes into randomly selected columns of the public key in the parity check matrix $H'=SHP$ and $H'\,^t$ to make it random. Here $H'$ is byte error correcting code.

This proposal based on q-array syndrome decoding problem. It is another approach to randomization for a Niederreiter public key.

Unless an attacker knows in which column the Goppa code is located, the attacker will (need to) decode by information set decoding.

Is this scheme insecure?

There is no firm belief, but it is based on the assumption that it is difficult to distinguish between a column of randomized Goppa codes and a column of random linear codes. I can not yet think of a way to prove that.


texts: How can we verify if a function is indeed a one way function?

texts:
How do we show that the addition function f (x, y) = x + y (where |x| = |y| and
x and y are interpreted as natural numbers) is not one-way?

I can see that the idea is to find any pair x and y which add up to x+y. But how do we ensure that the lengths are same i.e. |x| = |y| ?


texts: AUTHENTICATE MERKLE TREE: In the passage below how is A able to confirm YB in the public file only knowing R, log2 intermediate values, and YB itself?

texts:
"If A wishes to confirm B's public
enciphering key, then A need only know
the first half of the public file,
(which is where YB appears) and H(second
half of public file) which is only 100
bits long. A can compute H(public file)
knowing only this information, and yet A
only knew half the entries in the public
file.
In a similar fashion, A does not
really need to know all of the first
half of the public file, for
H(first half of public file) =
F( H(first quarter of public file),
H(second quarter of public file)
All A needs to know is the first quarter
of the public file (which has YB), and
H(second quarter of public file).
By applying this concept recursively,
A can confirm YB in the public file
knowing only R, log 2 n intermediate
values, and YB itself. The information
needed to authenticate YB, given that R
has already been authenticated, lies
along the path from R to YB and will be
called the authentication path.


texts: Can two people with different one time pads securely exchange a message like this?

texts:
Alice has a message, generates a one time pad, encrypts her message and sends it to Bob. Bob generates his own one time pad, encrypts the message again, and sends it back to Alice. Alice then decrypts this message using her one time pad, sends it back to Bob who then decrypts it the last time using his one time pad.

The only problems I see with this technique:

It is vulnerable to a man in the middle attack.
It requires sending the message back and forth twice between sender and recipient.
It doesn't scale well if you want to use it to communicate with multiple people.
Requires a way of generating cryptographically secure random numbers.

Does this method of encryption have a name?

If we ignore the fact that it's vulnerable to a man in the middle attack, is this method of encryption information-theoretically secure?

Why isn't this method used widely, i.e. which of the above listed problems or other problems makes this method infeasible for production use?


texts: security parameter in lattice cryptography

texts: In paper Lattice Signatures Without Trapdoors(Lyubashevsky2012), $n$ is the security parameter,  why the authors set $n$ as 512 but not 80/100/112 to get 80-bit security/100-bit/112-bit security?