texts: Cryptographically linkable random tokens

texts:
Are there any algorithms/protocols that let you produce a specific length of random tokens/bits in such a way that you can cryptographically determine which 2 or more tokens/bitstrings where produced using the same seed/key. Is it possible at all?

For example, if I produce these random bits: 12432, 15693, with key A and 57322, 57483 with key B. I want a third party who gets 12432 and 15693 to be able to determine they were both produced under the same key.

I thought of digital signatures as the obvious solution. However digital signatures will be to long for my requirement. I would like the token to be between 10-20 bits long, any pointers will be greatly appreciated.

Requirements:

The third party should be able to verify the tokens are valid.
Ideally, the third party should be unable to forge tokens.
Tokens must be unique to a single key.


texts: How to model a miniature elliptic curve?

texts:
For educational purposes I would need to work on an elliptic curve that has a small field, but holds the safety futures of a real curve. Is that possible to have such a curve!?

For example for the curve of secp256k1, is that possible to find small $P$, $N$ and $G$ so that the mini curve does still have safety features of the real curve? By safety features I mean those features that come from the difficulty of solving the discrete logarithm problem. Of course I know that a curve with a small field is vulnerable through brute-force attacks.

To do so, first I read about properties of the prime $P$. It seems that it is a SAFE prime which is equal to $3 \bmod 4$. If I search for a small prime with the same two properties am I getting the correct mini curve?

How are $G$ and $N$ decided then?

I need a curve that lets me do point manipulations (adding, doubling, halving,...)  with plotable easy-to-work-with integers, not those 78-digits of secp256k1.


texts: How to break a columnar transposition cipher?

texts:
I'm currently studying for a cryptography exam. I've been given ciphertext that has been encrypted by a columnar transposition cipher. I've been given no shift key length or key word, the only thing I know is that only 2 columns have been shifted.

How can I determine the key? Or better yet, is there another way to decipher the ciphertext?


texts:
I know how standard HMAC(key,msg) function works, and I want to write a Delphi port of HMAC class that implements Update function. The problem is that I don't understand how this Update function works (for example of Update function, see SSL definition here: https://www.openssl.org/docs/crypto/hmac.html).

If I understand this correctly, these two pieces of pseudocode should return the same HMAC (e.g. Result1 = Result2):

Code 1:
HMAC.Init;
HMAC.Update('key','abc');
HMAC.Update('key','def');
Result1 = HMAC.Digest;

Code 2:
HMAC.Init;
HMAC.Update('key','abcdef');
Result2 = HMAC.Digest;

I have found Python implementation here: https://hg.python.org/cpython/file/2.7/Lib/hmac.py but I have no knowledge of Python (I am Delphi programmer) and I don't undesrtand it. Could somebody explain it to me, or, possible provide an example of pseudocode/Delphi?

EDIT:
Probably I should have given some more details about the  reason I have asked this question. Basically, I need to calculate HMAC(key,msg) where msg is a content of a stream/file, which can be big - and therefore its contents can't be passed to HMAC function at once. Therefore I need to read blocks of the stream and continuously update the HMAC message, so that after whole stream/file was processed, HMAC digest contains HMAC of the whole stream.


texts: How to count Gate Equivalent (GE) of Sbox used in block Cipher. For example how much area does the Sbox of Block Cipher Prince take? And How is it calculated?


texts: Detecting revoked keys long after a document is signed

texts:
Scenario: A document is signed with a compromised private key, with a long-term time stamp. The normal expiration date of the key pair is D. The rightful owner of the key pair discovers the compromise 15 days after the fraudulent signature is executed, and has the key revoked.
The evil-doer waits until after the normal expiration date, and presents the document as if it were genuine. As I understand it, CAs remove expired keys from certificate revocation lists and Online Certificate Status Protocol. So a person checking the key sees a key that was valid at the time of the signature, and expired in the normal course of events.
Have I got this scenario right?
Would it make any difference if the certificate had been revoked before the signature was executed?


texts: why a group used in cipher based on DLP must be Abelian group?

texts:
I can't understand it because $(g^x)^y=(g^y)^x$ in nonabelian group too.

thank you very much for read my question


texts: Does knowing common prefixes help crack blowfish?

texts:
I have strings that are if the form:

 {static data}{changing data}

The beginning static data part is around 20 characters and is common to all strings. The last part is around 5 characters and is different for each string.

The string is encrypted using blowfish (from xjava.security.Cipher) with a fixed initialization vector and a fixed key. Can the fact that the beginning data is unchanging be used as an effective exploit to help break the encryption?

[Edit] Updated to use correct terminology and add a little more information.


texts: How is the identitiy of a subject in a Public Key Certificate verified by the Certificate Authority (CA)?

texts:
A general digital certificate issued by a CA might contain information about the individual/organization to whom the certificate belongs. As an example, consider this sample scenario:

This PKC contains identifying information of the individual to whom is this certificate is issued, i.e. the Name (Mario Rossi), Organization (Wikimedia), and so on. For a more concrete example, here is an excerpt of the PKC data issued to Wikimedia, containing info about their company name, address and domain:
...
Subject: C=US, ST=California, L=San Francisco, O=Wikimedia Foundation, Inc., CN=*.wikipedia.orgSubject
...

My question is what are the standards used by the CA to ensure that these claimed details about the Subject's name, address, domain, etc are genuine and not being falsely claimed by forger? Additionally, what kind of subject-related-data, in addition to names, addresses, etc., can be expected to be verfied by the CA?


texts: Confidentiality then Integrity with different keys

texts:
Can anyone describe how we can do what is said in the below sentence which is in Mark Stamp crypto slides (PPTX) on slide number 101 :

  Can do a little better - about 1.5 “encryptions”

The whole slide is as follow :

  Confidentiality and Integrity

  Encrypt with one key, MAC with another key
  Why not use the same key?

  Send last encrypted block (MAC) twice?
  This cannot add any security!

  Using different keys to encrypt and compute MAC works, even if keys    are related

  But, twice as much work as encryption alone
  Can do a little better - about 1.5 "encryptions"

  Confidentiality and integrity with same work as one encryption is a    research topic


texts: Is correlation in vector distributions "dangerous"?

texts:
Consider the two vector distributions $\xi,\chi$ described below, each one outputting integer vectors of length $n$ with coefficients in $\{0,\dots,n\}$.

Distribution $\xi$ samples each coefficient $v_i$ following a distribution $\alpha_i\sim Binomial(n,p)$ and outputs $\mathbf{v}=(v_1,\dots,v_{n})$. The $\alpha_i$'s are pairwise independent.
Distribution $\chi$ samples each coefficient $w_i$ following a distribution $\beta_i\sim Binomial(n,p)$ and outputs $\mathbf{w}=(w_1,\dots,w_{n})$. The $\beta_j$'s are dependent: for each $a\neq b$, we have
$$\operatorname{Corr}(\beta_a,\beta_b)=r>0,$$

where $\operatorname{Corr}=\operatorname{Cov}(\beta_a,\beta_b)/\sigma_a\sigma_b$ is the Pearson correlation coefficient.

I know both distributions are distinguishable, but how many samples do we need to actually distinguish them?

Let's say that the use of distribution $\xi$ is secure in a protocol. Is the use of $\chi$ less secure ? I.e., does correlation helps the attacker? The answer depends maybe on the attack, but is there a general result or fact that will help me understand to what extent is correlation dangerous?


texts: What are the major flaws and limitations of this hash-based stream cipher design?

texts:
K is a 224-bit key.
C is a 32-bit counter; it is publicly known. the same value is never used twice.
plaintext has arbitrary length (up to 64kB).
H is a cryptographic hash function that returns len(plaintext) bits.
^ is the bitwise XOR.
+ is the concatenation.

Encryption:

ciphertext = plaintext  ^ H(K + C)

Decryption:

plaintext  = ciphertext ^ H(K + C)

Are there any fundamental flaws?
Would it make sense to use a longer key?
Under what circumstances would doing H(C + K + C) instead of H(K + C) make the algorithm more secure?
I intend to use Skein, which comes in three flavors of internal state sizes: 256, 512 and 1024 bits. How does the internal state size limit the strength of the whole system? Would it make any sense to use the 512/1024 bit variants, even though len(K+C) = 256?
Is there anything particular about Skein that would make it unsuitable for the job?

edit: Thinking about it, len(K) > internal state size seems pointless. To break the encryption,  an attacker would just need to find a K that produces the same internal state as the real K.


texts: Calculating entropy within xkcd 936: Password Strength

texts:
When I calculate entropy for the xkcd Password Strength (comic 936) I don't get nearly the amount of entropy stated in the comic.

So why doesn't the the first password "Tr0ub4dor&3" have an entropy of around 50 bits? And why doesn't the passphrase sentence "correcthorsebatterystaple" represent over 100 bits of entropy?


texts: Is there a contingency plan in the event of a catastrophic attack on AES?

texts:
NIST selected Rijndael in 2000 to be AES. In a paper from the Serpent authors, they mention that there was the possibility of choosing a second cipher as a backup in the case of any severe breaks:

  I believe that there should be only one standard. NIST should decide on one standard in order to ensure that the standard is accepted and adopted as soon as possible. However, NIST can publish the choice of a backup cipher which will replace the standard in case it is broken or in case other circumstances (such as intellectual property problems) will prevent it from being used by the public.

NIST has not done this, according to section 2.4 of a report from NIST. Is there any process in place in the event that a severe cryptanalytic attack against AES is discovered? Imagine it's 2029 and a new paper comes out showing that all 14 rounds can be broken with a complexity of $2^{50}$ and a negligible amount of known plaintext. Would there be any official steps taken by NIST, for example changing the standard to use more rounds? Would one of the other AES candidates be chosen as AES2?

I don't believe that there will be a major break in the cipher without prior cryptanalysis showing it to be gradually weaker and weaker, so I highly doubt the total break, if one is ever discovered, will come as a surprise. However, I am still curious to know if there is an official policy on the matter.


texts: Bijective function with unknown reciprocal function

texts:
I have a use case where I need to build a unique identifier for my users with the email address and the "family member number". However, the two personal informations used to build the identifier must be hidden. I thought using a hash function for that but there is a risk of collision (the identifier is not guaranteed to be unique).
Should I still use a hashing function for that, or should I use some kind of bijective function with unknown reciprocal, if such kind of function exists?


texts:
Boxcryptor uses various CSPRNGs and apparently hashes the output using PBKDF2 to derive the final key. Even though the choice of PBKDF2 is probably not semantically correct (PBKDF2 is intended for passwords), I wonder if this iterative hardening actually makes sense.

Let's suppose the CSPRNG is backdoored/buggy/broken/etc (we have already seen that in the past), and for 128-bit output, you just get let's say 64 bits of entropy (the rest is supposedly predictable by an adversary). So the adversary has to work 264, which he can brute-force. But now the app does:

key = PBKDF2(csprng_output, salt, 1000000)

Not sure where the salt comes from (since they don't trust the CSPRNG, I guess it's fixed??), but does this make sense? Adversary still has to guess 264 obviously, but each guess takes a lot of work. After all, that's exactly why we use PBKDF2 on passwords to be secure despite their low entropy.


texts: Random Self-reducibility in Discrete Log

texts:
I understand what Random Self-reducibility means and how it is used in the Discrete Log. What is not clear is

how does it show that DL is hard in the average case.

The probability of success of an imperfect DL black box is $p(n)$ (for an $n$-bit string, and $p$ is a polynomial). So, in order to get a correct DL for an input $y$ is $1/p(n)$.

Does this mean that finding the DL of a single $y$ can be done in polynomial time? (just run the algorithm $n*poly(n)$ which is still a polynomial!)

Afterward, in a lecture the professor, went over describing that the probability of succeeding every time is $$\left(1-\frac{1}{p(n)}\right)^np(n)$$ and that this is less than $e^{-n}$.

How did they reach this conclusion?
If the conclusion is correct, does this mean that the machine is successful every time with negligible probability (so finding a DL of every is negligible?)


texts:
Let's say we have a set of ordered elements $D=[x_1,x_2,x_3,x_4,x_5]$. We apply a random permutation on them with a $PRP=P_k: P_k(D)=D'=[x_3,x_2,x_5,x_1,x_4]$

My question is: can the owner of the key $k$ recover a single position of the original element without having to recompute all the permutations? Is there an inverse $PRP, PRP'_K$ such that:

$PRP'_K(3)=x_3, PRP'_K(2)=x_2$ and so on and so forth or given the result of the permutation and the key to recover the original element of this positions:$PRP'_K(x_3)=x_1, PRP'_K(x_2)=x_2$ ? without keeping either $D$ or $D'$


texts: Numerical Algebraic geometry in the finite fields

texts:
Does the numerical algebraic geometry method work in the finite fields?
I am working on this method to find a solution for a low-degree proximity testing problem.

Would you please guide me how they work in the finite fields?

  Clarification: Consider the $d$ low-degree proximity testing problem for Reed Solomon codes (RPT). Informally, we can define it as below:

The RPT problem assumes a verifier has oracle access to $f$ (as the evaluation of some points by calculating the RS code i.e it is a polynomial in the finite field) and to auxiliary information like a PCP (Polynomially Checkable Proof) of Proximity (PCPP) or an IOP (Interactive Oracle Proof) of proximity (IOPP); the verifier’s task is to distinguish with high probability and with a small number of queries to $f$ and the auxiliary PCPP/IOPP oracle(s), between the cases:

that $f$ is a codeword of $RS[F,S,\rho]$; and the case that
$f$ is $δ-$far from all codewords of $ RS[F,S,\rho]$ in relative Hamming distance.

The existing solutions such as LINK used some techniques including Fast Fourier Transform and also you can find more information about IOP.


texts: What are the advantages of CBC over ECB?

texts:
From this question I understand that, for a block cipher, using CBC is better than ECB. It seems that if one only has part of the cipher text, then decryption is difficult because the decryption depends on the previous cipher block.

But, what if one does have the whole cipher text? Is CBC then better? It seems, that in this situation one can just first XOR each cipher block with the previous cipher block and then convert the cipher text into what would have been the output using ECB (I assume that the IV is known). Is that correct? If so, what other advantages does CBC have over ECB?


texts: Prove integer is within the interval [a,b]

texts:
I am trying to find a schema to ensure that a secret integer lies in the interval [a, b], where a and b are not power of 2.

I took a look at hash chains as described in this paper and at 'range proof' with ring signature as described here.

Unfortunately, I don't think those systems meets my requirements.
Do you know any other schema which could help me?

I can already tell that my numbers lies in the range [0, 100].
Thanks!


texts: Details about ROS attack on blind Schnorr signatures

texts:
My question concerns the recently uploaded paper On the (in)security of ROS that describes an expected polynomial-time attack on the unforgeability of Schnorr blind signatures.
a) Does this mean that Schnorr blind signatures should not be used anymore (ie. is the attack merely theoretic or can it be used in practice)?
b) How does this attack affect Okamoto-Schnorr blind signatures? In particular, I do not understand the comment of the authors that their attack does not contradict the analysis of Pointcheval-Stern. Were Okamoto-Schnorr blind signatures already broken?
c) The ROS problem mentioned by the authors and initially by Schnorr himself seems quite generic. Could the attack be applied to all blind signature schemes?


texts: Why are polynomials chosen with coefficients in $GF(2^{8})$ in Section 4.3 of NIST FIPS 197 for implementing AES?

texts:
I was trying to understand  AES (Rijndael) from a very mathematical perspective. I'm quite new to abstract algebra and Galois Fields. I understood that we are considering a byte (8 bits) as a polynomial in $GF(2^{8}) $ where the coefficients are either $0$ or $1$ i.e. they are elements of {0, 1} and all operations are done modulo the Rijndael polynomial 0x11b ($x^{8} + x^{4} + x^{3} + x + 1$).
But Section 4.3 confused me a little when they are explaining that the coefficients themselves are considered as "bytes" i.e values from $0$ to $255$ . Can anyone please explain to me, why is this context switching possible, or why is it done?

  Four-term polynomials can be defined - with coefficients that are finite field elements - as:
  $a(x) = a_{3} x^{3} + a_{2} x^{2} + a_{1} x + a_{0}$ (4.5)
  which will be denoted as a word in the form $ [a_{0} , a_{1} , a_{2} , a_{3} ]$. Note that the polynomials in this
  section behave somewhat differently than the polynomials used in the definition of finite field
  elements, even though both types of polynomials use the same indeterminate, x. The coefficients
  in this section are themselves finite field elements, i.e., bytes, instead of bits; also, the
  multiplication of four-term polynomials uses a different reduction polynomial, defined below.
  The distinction should always be clear from the context.

Every help will be greatly appreciated!!!


texts: How can scrypt be improved to counter GPU mining

texts:
I know scrypt was designed to lessen the GPU/ASIC advantage.

We now have litecoin as a real-world example of this. However, it hasn't worked out perfectly.  Most coins are mined by GPUs, although the advantage is probably smaller than it would have been with SHA-256.

I wonder how the future for scrypt and newer generations of this approach looks like:

Are there alternatives being developed?
Are there specific issues exposed by Litecoin that could be addressed?


texts: Is it possible to derive related signature?

texts:
For example, the message is a json: {name: john, age: 13}, and is sealed with signature.

Now, is it possible to derive a signature for the new message: john is less than 18 ?

I feel, to achieve that, the less than operator should be well-defined.

Any known research in this field?


texts: Does the Message Integrity Check in WPA(2) standard solve the problem of non-repudiation?

texts: Whether the receiver can be sure that the message is sent by the source only and not spoofed by someone else?


texts:
I'm encrypting some files using AES in CBC mode.

I'm also using file's digest (SHA-1) to check that data is decrypted correctly (so I need to store it with file).

Is it safe to use this digest as AES's IV and store it in the header of file? Or it has security issue?


texts: Why is $H(k\mathbin\Vert x)$ not a secure MAC construction?

texts:
If $H(m)$ is a secure hash function, can't we implement a MAC using $H(k\mathbin\Vert m)$?

However, it seems the more widely used MACs, such as NMAC and HMAC (both originally defined in Keying hash functions for message authentication) use a much more complicated scheme. Why is this concatenation scheme insecure?


texts: AES: a question about dual ciphers and security

texts:
I have recently learned of dual ciphers, in particular dual ciphers of AES. It seems there are many. Most of my information comes from:(1) Representations and Rijndael Descriptions.

In this paper the authors (which includes one of the designers of AES) discuss $256!$ equivalent ciphers of which $2^{62}$ are useful (4.1 and 4.2).

if dual ciphers are equivalent can we assume they are all just as secure?

Another paper (2) In How Many ways Can You Write Rijndael discusses different types of dual ciphers, such as Log Dual Ciphers and Square Dual Ciphers.

This paper refers to trivial dual ciphers, could anyone give a simple example using a very basic cipher? I could not understand the explanation in the paper.

In sec. 4 of paper (2) they mention changing the irreducible polynomial (there are 30 with each having 8 square dual ciphers, giving a total of 240 dual ciphers).

If we used a different irreducible polynomial for each round of AES to create a kind of multi-dual cipher (my own term), would that make it harder to cryptanalyse and therefore stronger against DCA and LCA? If so, could we use fewer rounds whilst retaining the same level of security?
And, further to 3. above, what if each round's irreducible polynomial  were chosen at random and were changed for each full encryption? Again, would this allow for fewer rounds whilst retaining the same level (or at least adequate) security?

I understand that a so-called multi-dual cipher may have huge implementation problems and may slow the cipher considerably, but I am thinking purely in terms of security, i.e. resistance to analyse.


texts: Why is $-1$ an illegal message in the Goldwasser-Micali Encryption Scheme

texts:
I'm not sure why in the Goldwasser-Micali encryption scheme with a Blum integer $N$, the message $-1$ is always a illegal message.

Can you give me some direction for starting?

What is illegal message's meaning?


texts: No way to do ECDH with OpenSSL from the command line?

texts:
I've scoured this website and the OpenSSL wiki pages, and done numerous internet searches, and I've come to the seemingly incredible conclusion that one cannot generate an ECDH shared secret key using a given public key and a given private key from the openssl command line. There is at least one other post on this web site that claims you can, without providing an example.

I know the wiki does provide 'C' code examples, but my use case is such that having the command line capability would've been much preferred.

If anyone can kindly disabuse me of this notion by providing an example, I would surely appreciate it.


texts: Can TLS session resumption work after client dropped connection & reconnected to server?

texts:
I'm developing a sensor node and investigating TLS/OpenSSL. The network the node runs behind could drop and reconnect a lot. The node has limited data plan so data overhead is the key where TLS handshake is a big contributor as I understand.

Can session resumption be used after each network drop & reconnection? Or full handshake is needed in this case?


texts: How to efficiently generate a stream of independent, but biased random bits?

texts: Usually, in cryptography, one is interested in debiasing a stream of independent (true) random bits, and several algorithms exist to do this. What about the converse? Let's assume I have a stream of independent and unbiased random bits at my disposal, and that I would like to generate a stream of statistically independent bits, but where $\Pr[B=0] = \frac{1}{5}$, say. How do I do this without sacrificing too much entropy from the initial source? A common algorithm for this precise case would consist in drawing $3$ bits, and interpret them as a number $0 \leq a \leq 7$. If $a=0$, then output $0$, else if $a < 5$, then output $1$, else output nothing. The problem is that I will sacrifice a lot of entropy: with probability $\frac{1}{4}$, I discard 3 bits, and with probability $\frac{3}{4}$, I transform 3 bits of entropy into a single one. Are you aware of a less entropy-hungry method?


texts: Is Googles Envelope Encryption the same as Hybrid Encryption?

texts:
Google is advertising the use of Envelope Encryption in their products with their KMS. By the description, it sounds very much like Hybrid Encryption. But since I could not find any reference to Hybrid Encryption, I wonder if there might be a difference in the idea behind it.

Source: https://cloud.google.com/kms/docs/envelope-encryption


texts: What is the discrete logarithm assumption and why it is not easy with Shank's baby-step/giant-step

texts:
When I read about the DLP, it seems that the assumption is that it is not generally possible to solve it in polynomial time. But I also read that there are several algorithms in $\mathcal{O}(\sqrt{n})$, for instance, the Shank's baby-step/giant-step so there must be some misunderstanding by me.

What is the assumption?

If I understand the problem correctly, we are given a group with a modulus and a generator of that group. The problem is:

Given an element $x$ of the group, find the number $a$ so that the generator $g$ will generate $x$ by $$x = g^a \bmod q.$$ And the assumption is that we cannot do it for a random or worst instance of the problem in polynomial time, but I must have misunderstood because I read about deterministic algorithms such as Shank's baby-step/giant-step which solve the problem in $\mathcal{O}(\sqrt{|G|})$ which is quite fast isn't it?

Where is my mistake?


texts:
I am confused about the hardness of the one-way function behind cryptography -- if someone could factor the large number produced back into two primes quickly then the one-way function would be broken?
     TIA


texts: Can it be proven that my home-brewed hash function is not LESS secure than a known good hash function it leverages?

texts:
Home brewed cryptography is strongly discouraged because it is so easy to get it wrong.

Even if we leverage a known good hash function, one example, sha256, here by referred to as g() and use it in conjunction with a home-brew function b(), we can reduce our security because we have reduced our entropy; example:

g(b('secret')) will be less secure than just g('secret') if b() is collision prone.

Proving (I am not using prove in the strictest mathematical sense) a hash function is more secure than another is a herculean task that requires a lot of time from cryptography experts, and is beyond the scope of this question.

However, let's say no crypto-hash function that suits my needs currently implemented on my platform so I want to home-brew. If I am okay with worse performance, ect, and simply want to ensure it is not less secure than a known good function g() it leverages extensively.

For example, if we define b() to be g(g(g(g(g(g(g(g(g('secret'))))))))) we know that b() is not less secure than g()

Are there a set of quick set of guidelines that can be leveraged to ensure a derivative home-brew function is not less secure than the function it uses?

One example function b() might look something like this where it mainly uses a propriety logic as salt for g() (please do not think that this is intended as a replacement for random salt!!):

b() is defined as g('secret' + b1('secret'))


texts: How to express a coin flip based random generator mathematically?

texts:
I would like to know how to express a coin flip based random generator mathematically.

I have recently started Dan Boneh's Cryptography 1 and in the slides a pseudo random generator G, which outputs n-bit sequences, is defined as $G:K \rightarrow \left\{0,1\right\}^n$.

So following this I have come up with this for a coin flip:
$$
G(n) = \left\{0,1\right\}^n
$$

The idea is that n is the number of tosses and the function G will output n-bit length random numbers. The latter part with curly braces and the exponent $\left\{0,1\right\}^n$ is something I have not come across before. Is this a notation that's only used in cryptography?

Formal definitions are definitely a weak point for me so I don't know if I'm way off. Or if there's some better way to express this. Or if I'm approaching this completely wrong.


texts: Step by step conceptual implementation of AUTHENTICATED Diffie-Hellman?

texts:
I'm already doing classic DH with pre-shared key in my setup, and it prevents people knowing the same password from eavesdropping on others' traffic. But it doesn't cover situations where a third party authenticates to the server, then masquerades as the server to an incoming client, performing an authentication and then forwarding the traffic to and from the server transparently to both parties, all the while it is able to read and modify it at will.

Wikipedia contains half an explanation in its DH article about how the authenticated/public key flavor goes, but it's confusing to follow step by step. From what I managed to understand, the private key is g^a%p=PUBKEY then for each one-way encrypted message, g^b=ENCRYPTED_SECRET is computed, and sent to the PUBKEY holder.

I do not understand however, what the PUBKEY holder is supposed to do with ENCRYPTED_SECRET upon receipt in order to retrieve b, if b is indeed what is supposed to even be retrieved. Nor what the formula for this should be, what I exponentiate to what etc.

A step by step would help. Thank you.


texts: Symmetric proxy re-encryption practical implementations

texts:
I want to encrypt some files in a cloud and delegate decryption rights to authorized users. The performance matters for me and I think I should use schemes utilizing symmetric encryption.

Could anyone suggest practical (production ready, maybe) implementation for symmetric proxy re-encryption? I'm looking at pyUmbral, but this is thresholded scheme. I'm not sure if using it with N=1 and threshold=1 is ok (if it is, just let me know).

I also found "Realizing proxy re-encryption in symmetric world" paper, which looks promising for me, but I couldn't find any implementations.

Encrypting files with any symmetric cipher and proxy re-encrypt just decryption key is not ok for me, I want to be able to revoke access to files.

Thank you.


texts:
I try to understand the GCM-MODE used in TLS.
The problem I have had is described below.

1:textbook describes how GHASH works:

2:
I get some debuginfo from openssl code that contain enc_key(32 bytes) and ADD(13 bytes).

I try to simulate the GCM MUL by coding like this:

static unsigned char buf[16]={0};
static unsigned char ctr[16]={0};
static unsigned char ectr[16];

static int poly[]={128, 7, 2, 1, 0, -1};
BN_GF2m_arr2poly(poly, p);

AES_set_encrypt_key(gcm_key, 256, &ghash_key);//gcm_key is derived from debug info
AES_encrypt(ctr, ectr, &ghash_key);

BN_bin2bn(ectr, 16, k);//construct K
memcpy(buf, gcm_add, sizeof(gcm_add));//gcm_add is a 13 bytes data derived form debug info
BN_bin2bn(buf, 16, a);//construct ADD
BN_GF2m_mod_mul(r, a, k, p, bnctx);//compute  (add · K) as first part of computing tag

But the result r is different from the result in openssl code(The code use GCM_MUL).
I confirm that the gcm_add and gcm_key are correct and even the ectr encrypted by gcm_key is also correct compared to debug info from code.


texts:
I'd like to encrypt a message using PGP keys, and elliptic curve cryptography as the method.

In practice, using the Erlang :crypto module, but first, I'd like to wrap my head around how I would begin to go about this.

Should I generate an ECC PGP key?
Should I use my normal PGP key and sign using :crypto module using ECC as the method.. if that is possible that is.

Any pointers in the right direction would be appreciated.

First time poster in Cryptography, BTW.


texts: AES + CBC encryption for a stream of UDP packets

texts:
I am developing an application that is based on UDP, and I need to send a stream of packets. As you can imagine, packets can get lost or corrupted. I need to make sure that the content of those packets is encrypted, and I also need to be able to certify that the packet is correct when I receive it.

Finally, since performance is crucial in my application, I would like to keep the encryption overhead as small as possible. Often times, packets are relatively small, so even a few blocks can build up a relatively big overhead.

I don't have a reliable previous experience with cryptography, so I thought it was better not to trust myself on this.

Here is the strategy I have used until now (my application is far from being released, so having to change it more or less completely won't be so much of a problem).

First of all, packets are of fixed size, which is usually multiple of the block size of AES. I have no need whatsoever for padding, since messages aren't variable in length.
I use a shared key (obviously) and two fixed IVs, each endpoint uses one of the two to encrypt its messages. I use AES in CBC mode.
Since obviously using a fixed IV leads to a whole bunch of security flaws, I need to make my first block vary in a uniformly random fashion: that will act as IV for the next blocks.
Therefore, I prepend a block at the beginning of my packet. Its content goes as follows:

First four bytes: current timestamp in seconds
Next 12 bytes: zeros
I compute the sha256 hash of the message (32 bytes)
I xor the timestamp + zeros block with the first half of the hash
I xor the result with the second half of the hash

When I receive the packet on the other endpoint, I decrypt it with the key and the remote iv.
I compute the sha256 hash of the message (without the first block), xor the first half and the second half.
I xor the result of the hashing procedure with the first block.
If I get a timestamp that is no more than a few seconds ago, and 12 bytes of zeros, then the packet is correct.
If the packet is not correct, I just drop it, exactly as if I didn't receive it. No answer is sent back.

What are the flaws in this procedure?


texts: Which is the simplest cryptographic algorithm which is close to commercial-level security?

texts:
An algorithm is simpler than another if

It is easier to explain to a noob with basic high-school math knowledge.
It is easier to securely self-implement by an intermediate programmer (Yes I know one should never 'roll their own' but this is just a metric of comparing simplicity)
Can be done by hand & paper more easily (not necessarily that it can practically be done on paper, but that it is easier to do on paper if one were to take the pains to do so)
Involves lesser steps.
Any other factors that don't immediately come to mind.

To give an example with popular ciphers, by these criteria RSA is simpler than AES.
The point of this question is maybe find out about some very clever albeit less popular/unheard of cryptographic algorithms that are at or quite close to real commercial-level security while still being incredibly simple.
To use simpler words, the requirements are much above Caesar cipher but much below AES, in terms of complexity.
A question on the most secure hand ciphers inspired this question, except there are no such limitations of not having computational/calculational power here, but similar/stricter restriction on complexity. The idea is to test the limits of simplicity that cryptography can reach while still being done right.
Perhaps symmetric ciphers would be ideal for the criteria of simplicity. However, obviously, any cipher is to-the-mark if it is simple and secure enough.
Edit 1 : The criteria listed above are in order of importance, i.e, the 1st is more important than the second and so on.


texts: Are theorems 2 and 3 in the Town Crier paper (Zhang et al, 2016) proven using the UC framework?

texts:
I am reading the paper ‘Town Crier: An Authenticated Data Feed for Smart Contracts’ by Zhang et al (2016), but there is something I just cannot wrap my head around.

In Section 7 and Appendix C, it is stated that three theorems (Authenticity, Gas Sustainability, and Fair Expenditure) are proven following the UC framework.  My understanding of this framework is that security of a protocol π  is proven by first defining an ideal functionality F, which is a trusted party, and then prove that π realizes the ideal functionality in an environment without this trusted party.

Now, in the proof of theorem 1, they indeed use the formal abstraction for SGX. However, in the proofs of theorem 2 and 3, it seems to me that only the protocols defined in figures 6, 7 and 8 are used and there is no comparison with any ideal functionalities.

So my question is: are these theorems still proven in the UC framework? And if so, what am I missing?


texts: How can I enhance the security level of my RSA code?

texts: I am trying to enhance the security level of my RSA code that I implemented in Python. I tried to add blind operation, randomized algorithm to my RSA code (separately, not together), but I am not sure about the enhancement. Is it possible to enhance the security level of my RSA code by modifying it? If it is possible, what are the other ways to enhance the security level of RSA, or is it correct to try to enhance the algorithm with blinding, or randomized algorithm? In short, how can I enhance the security level of my RSA code in Python? I really need help with this. Thank you!


texts: How can semi-weak DES keys be leveraged to attack DES?

texts:
I see how DES weak keys can be leveraged under chosen plaintext attack where an adversary feeds the ciphertext encrypted by a weak-key back to the DES encryption function and gets plaintext as a result.

The probability that both keys from the semi-weak key pair are used seems to be very small ($6/2^{56} \times 1/2^{56} \approx 1/2^{110}$) making chosen ciphertext attack significantly slower as compared to exhaustive key search ($1/2^{56}$). If this logic is correct, then how can one leverage semi-weak keys to attack DES?


texts: Do I have to have a different salt for each password?

texts:
Should I use a different salt for each password?

In my system, there are no user names, only passwords.  When a user logins in, he types in one or more passwords and the server compares the results of the password(s) hashed many times (PBKDF2) for authentication.  Each password might unlock some subset of functions.

As I see it, salt has two purposes:

Decrease the feasability of using (rainbow) tables: The salt makes rainbow tables with just ascii characters useless and the cost of making rainbow tables for all possible salts is greater than that of brute-forcing the password.
Unique salts per password mean that users selecting the same password won't have identical authentication results.

In my situation, using a salt per-password makes authentication an O(n*n) problem, time that could be spent on adding rounds to the hash.  With a single salt, (1) is accomplished and (2) doesn't matter because there are no user names.

So, can I use just a single salt?


texts: Definition of symmetric cipher and definition of asymmetric cipher

texts:
So I'm currently taking a cryptography class right now and my professor has told the class that she can't even define symmetric cipher for us without getting into asymmetric ciphers and the textbook we use hasn't been helpful. It gives me five points: plaintext, encryption algorithm, secret key, ciphertext, and decryption algorithm.

I was just wondering (plus I've googled around, there didn't seem to be much helpful definitions of these) could anyone please help define what exactly a symmetric cipher is? And if possible, an asymmetric cipher?

Thanks!


texts: MAC using a modified CBC mode of operation

texts:
I'd like to know whether the following modified CBC-MAC is secure (given a fixed IV).

Source: an old course on Network Security

Are there some obvious attacks I can't see?


texts: Are LRC (Longitudinal Redundancy Check) or CRC (Cyclic Redundancy Check) of any use in modern day computing?

texts:
I am currently learning about the history of Data integrity / Error detection.

In the old days of tape drives, LRC was used for error detection. They were also used (at certain point in time) for ensuring data integrity. But nowadays, the work that CRC or LRC did, has been mostly replaced by Hashes (MD5, SHA1 etc).

My questions are:

What were some of the reasons, why CRC or LRC was replaced by Message Digests?
Are these methods (LRC & CRC) still applicable/safe in modern day computing?

P.S.: I am asking this question from a cryptographic/Computer Security standpoint.


texts: Rule 30 Cellular Automaton for Cryptography

texts: Steven Wolfram of Mathematica uses a pseudorandom number generator based on Rule 30 for applications in Mathematica software but I would like to know if a pseudorandom generator based on Rule 30 is cryptographically secure? Can anyone weigh in on this?


texts: What is the advantage of Encrypt-then-MAC over Encrypt & MAC separately the plaintext

texts:
For secrecy, authentication & integrity, you can either use

CipherText = Encrypt(PlainText)
Signature  = Hash(PlainText)

CipherText = Encrypt(PlainText)
Signature  = Hash(CipherText)

Either case, you send both CipherText & Signature to the receiver.
What is the advantage of one method over the other? Does it differ in case of Symmetric vs Asymmetric Encryption?


texts: a doubt in Rijndael's key expansion sizes

texts:
I've often heard/read that AES key sizes 256 & 192 would be weaker than 128 or not stronger as expected from the size increase, but I've never seen a proof. How does one proof the strength of a Rijndael key size?

If I understand correctly, the main effect of having the key size different from the block size is on the key expansion. The iterative algorithm is moving along the columns, but the key size determines the number of columns. Later, this expansion is used in the addRoundKey() by taking sets that fit with the number of columns due to the block size.

I've been trying to understand, assuming this issue would be correct, from where this would come from.


texts:
I know it is possible to use RSASSA-PKCS1-v1_5 with client certificates in TLS 1.3.
But what about the other way around: using RSASSA-PSS with client certificates in TLS 1.2?
Is it possible to use RSASSA-PSS signed certificates with TLS 1.2 at all? Do I have to fall-back to RSASSA-PKCS1-v1_5 during handshake?
I searched through the RFC5246 but was not able to find anything that answers my questions.


texts:
I'm taking a hardware cryptography class and working on a problem that focuses on Montgomery Reduction.

So by definition:
Computing $a * b \text{ mod } N$

Pick $R$, s.t. $R > N$, $gcd(R,N) = 1$
Compute $N^{-1} \text{ mod }R$
$a’ = a * R \text{ mod } N$
$b’ = b * R \text{ mod } N$
$c’ = (a’ * b’) * R^{-1} \text{ mod } N$
$c = c’* R^{-1} \text{ mod } N$

Claim: $c ≡ a * b \text{ mod } N$

Proof: $c’R^{-1} ≡ (a’b’)R^{-1} R^{-1} ≡ (a’ * R^{-1}) * (b’ * R^{-1}) ≡ a * b \text{ mod } N$

If $R=2^k, x * R, ÷ R, \text{ mod } R$ are trivial an option to implement modular exponentiation.

Now I am ask to solve for this given the following 25 modulo 109 w.r.t. 128. The question I have is since I only have $a= 25$, does this mean there is no $b$ value?  And if that is the case, I can ignore calculating the $b’ = b * R \text{ mod } N$ expression and also remove it from calculating the $c$ equation?


texts: How can a decryption program tell me that a private key is incorrect for RSA and ECC?

texts:
I have a program which will encrypt the symmetric key with RSA public key with keysize 2048. I am able to decrypt the message with the corresponding private key.
My question is,  is it possible to decrypt a message with the different private key with same key length successfully? if it is possible then decrypted data can be junk data? In this case, how can I know, decryption is / was successful?

I have the same program for ECC keys (256,384) and will decryption return junk data in ecc using a different private key?


texts: Is multiple encryption with stream ciphers vulnerable to meet-in-the-middle attacks?

texts:
Let's suppose I encrypt something with a stream cipher (CSPRNG) two times using two 256-bit keys and different IVs.
Will I get 512-bit encryption strength?


texts: Does it necessarily mean that an RSA moduli generated with poor randomness is not random?

texts:
In 2012 a group of researchers collected a large amount of RSA moduli and calculated their greatest common divisor in order to find common factors between them. By finding a common factor they could the divide and completely factorize the key. They concluded that the vulnerable moduli where generated by PRNGs with inadequate randomness.
Does it necessarily mean that those key are not random?


texts:
We all know that signing a document is to encrypt its hash using signer's private key.
https://commons.wikimedia.org/wiki/File:Digital_Signature_diagram.svg
I've been searching the web for days, looking for a simple online page where you can sign a text using your private key (you can do this part offline), and others can verify a text's author inputting the received text, signature and signer's public key. But I didn't find anything, just symmetric encryption like https://encipher.it So I decided to create myself an app using PHP's OpenSSL capabilities. Here's the source code http://pastebin.com/Czp3SZHd

The problem is that I've read people saying that "you can't encrypt using your private key", "signing is not the same as encrypting", "raw RSA, without padding, is insecure".

So I'm confused. Isn't public-key cryptography supposed to be secure? That is, it isn't feasible to calculate the private key from the public key, not even having samples of plain and cipher texts, encrypted with the private key.

UPDATE:

I have updated the key length, from RSA-1024 to RSA-2048. Now I use phpseclib with RSA-PSS as default padding for signing. It also uses setHash('sha512').

Source: http://pastebin.com/rSzQ5uKs

Of course, I'm not taking into account other factors like server-client communication, key generation, etc.


texts: How to ensure confidentiality of an encrypted but public message given that computation power increases?

texts:
Say I encrypt a message with the public key of a party whom I want to contact with and then send the ciphertext over an insecure channel.

Naturally, an adversary who listens to this channel can obtain the ciphertext.
This adversary can simply wait some years for computation speed to increase and then might launch a brute force attack once it becomes feasible.

What methods do we have to prevent such attacks?


texts: Argon2 or scrypt instead of PBKDF2 with AES

texts:
Is using scrypt or argon2 a better key stretching technique with AES compared to PBKDF2 or bcrypt with regards to
a quantum computer brute force attack. The brute force attack I'm referring to is trying to generate keys from lets say a million
passwords and trying them on an encrypted text to get the password. In other words, can a quantum computer scale up a memory intensive
hash generation with scrypt or argon2 compared to PBKDF2 or bcrypt?


texts: Generating dataset for LFSR stream cipher

texts:
I have implemeneted the code for cryptanalysis of LFSR stream cipher . But I have a problem with generation of dataset i.e to get valid  pairs using LFSR stream cipher. In the stinson book it is mentioned that if coefficients $$(c0,c1,\dots,cm-1)$$ are chosen in suitable way and if non-zero $$k=(k1,\dots,km)$$ is chosen then we will get a periodic stream cipher with period $2^{m-1}$.

What should be the values of $$c0,c1,\dots,cm-1$$ that I should choose?


texts: Which hash function is usually used in RSA?

texts:
I know there are several available, however I can't seem to find whether there is one standard one or not.

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

Thanks


texts: Signing an integer, which may be increased

texts:
I have a 64 bit integer. It has some sort of signature so that one can be sure it is valid.

Anyone may increase the integer, update the signature, and remove all trace of the old signature. But it is not permitted to reduce the integer.

Many updates are permitted.

Is there a scheme such that, given $n$ and publicly verifiable signature $S(n)$, we can calculate $n+x$ and $S(n+x)$ but only if $x>0$?


texts: Solutions to $\gamma \equiv \sum_{i=1}^m \xi_i\cdot x_i\bmod p$ with $|x_i| < \ell$

texts:
Are there any clear conditions on $p,\ell$ and $m$ under which the equation $\gamma \equiv \sum_{i=1}^m \xi_i\cdot x_i\bmod p$ has at most one solution with $|x_i|<\ell$ with high probability over a random choice of $\gamma$ and the $\xi_i$?

This is closely related to the SIS problem, but instead of having several equations this only involves one.
Also, the question is not about the hardness of finding such solutions, but about the conditions on which at most one solution exists.

As an example, if $\ell = 2$, then the problems looks much like the Knapsack problem, and is likely to have one solution at most. However, as $\ell$ grows larger, the chances there are more than one solution also grow.


texts: Recover all keys on differential cryptanalysis

texts:
I am practically implementing differential cryptanalysis on a cipher from the book "the block cipher companion" .
I am successful to get the last key $k_5$. Just to say some words about the implementation:

I search for a good differential, calculate the probability and generate a list of input pairs which satisfy my input difference.
I let the pairs flow through the cipher (with the unknown keys) and then I guess the key bits of the sbox in the last round who are involved in my expected differential.
Now I decrypt with my guessed key, undo the sbox and generate the difference of the pair. If it satisfys my expected value, I count it as a hit. The key with the highest counter is probably the right one. So far so good. I can recover $k_5$.

However I can not get it work with the $k_4$.

I do the following: Search for a good differential, calculate the probability and generate the list with pairs which satisfy my input difference. I let them flow through the cipher and decrypt the last round with my recovered $k_5$. Then I undo the sbox and apply my guessed $k_4$ undo the permutation and undo the next sbox. Then I generate the difference and compare to the expected...

But this does not work. Is there a general mistake in my doing here?


texts: How many hash collision will exist where the digest is a pre-image?

texts:
This question follows on from the question Circular hash collision where digest is pre-image: Could hash(a) = b, hash(b)=c, then hash(c)=a?

The question was answered but the issue of the number of collisions was also raised. I have moved my answer to this query as a separate question. The other question begins:

For any SHA-family of algorithms (including Keccak) except for SHA1, would it be theoretically possible for there to exist a pre-image a whose hash digest b is the pre-image to the hash digest c which is the pre-image to a thus completing a circle (i.e. circular hash or collision of pre-image a with the digest a)?

${{hash(A)\to B}}$, ${{hash(B)\to C}}$ , ${{hash(C)\to A}}$

The answer to this is yes. My question is, how many such collisions would typically exist?


texts: I was wondering about what is permutation entropy(PE). Then, I came to know this paper which describes PE. Now, let's assume that we have a pseudorandom permutation that is generated using an entropy source and we used a uniform shuffle algorithm(like Fisher-Yates shuffling algorithm). Also, assume that we use a 256-bit entropy to shuffle $\{0,1\}^8\rightarrow\{0,1\}^8$. Then is the fact true that the output permutation can have at max 256-bits of entropy? For every value of entropy, we shall get a unique corresponding permutation.


texts:
I have read .
Replay attack is a kind of attack in that the attacker eavesdrops valid message and sends that message repeatedly to make requestor in busy mode. It can be prevented by adding timestamp to the broadcasted message.

Does that definition true? Some says that the definition seems to be incorrect.


texts: end-to-end encrypted chat app with symmetric + public key encryption, TLS and cert pinning

texts:
A big drawback of end-to-end encrypted messaging services is that, as soon as you lose your device, you lose all your messages. Your private key is gone after all. I was wondering though, wouldn't it be possible to do the following in a chat app for iOS, using certificate pinning and TLS for all communication with the server:

as soon as a user logs in in the app, an asymmetric keypair is generated and stored locally, and the public key is sent to the database;
when user X starts a chat with user Y, X's device generates a symmetric encryption key, stores it locally, encrypts it using Y's public key (downloaded from the central database), and sends the cyphertext to the database;
Y's device, as soon as it comes online, downloads the cyphertext, decrypts it using it's private key, and stores it locally.

Now, X and Y both have the key generated by X's device and can send messages to each other using symmetric encryption, and nobody, except for X and Y of course, has the symmetric encryption key. When, lets say, X gets a new phone, the following will happen:

X logs in on the new device and sends the new public key to the database.
Y's device will notice that a new public key was uploaded, downloads this key, encrypts the symmetric encryption key (that it received in step 3) with X’s new public key, and sends the cyphertext to the database.
X's device downloads the cyphertext, decrypts it using its private key, and can now download all old messages and decrypt them.

So, I guess my question is: what am I missing that makes my design unsafe? Is it just not smart to store keys in the database for a long time, even when they are encrypted with strong asymmetric encryption (lets say like 8192 bits, just for fun)?

Also, I am an iOS developer, and all keys would be stored in the iOS keychain, which is a very safe way of storing information locally. Nothing is 100% secure, I know, but storing stuff there is pretty much the best you can get on iOS as far as I know.


texts: Is it safe to use a key as message in keyed hashing (HMAC)?

texts:
Scenario:

User gives password.
A "password key" is derived from the password (e.g. by PBKDF2). A random salt is applied.
The password key is hashed with a HMAC algorithm (e.g. HMAC-SHA256), with itself as the key.
The salt and HMAC result are stored in database, for verification of the password (for further user logins).
The password key is used to encrypt other data.

Question: Is it safe to apply step 3 in terms of: can the password key be (easily) determined because it is known that it is the message to be HMACed?


texts: What is the proof that a hash output contains random binary numbers

texts:
I have heard quotes by many that a SHA-512 hash output is random.

Does anyone know what method was used to come to this conclusion? If it is not randomized, how could that be shown?


texts:
Let $N=pq$, where $p$ and $q$ are prime numbers, and order of $G_1$ and $G_2$ is equal to $p$. Suppose that $e(G_1, G_2)=G_t$ is a pairing of composite order. I know that, usually the order of target group $G_t$ is $p$.

Is it possible to set the order of target group to $pq$? In other words, is it possible to set order of target group be bigger that the order domain groups?


texts:
Let $H(-)$ be a cryptographic hash function with values in $\{0,1\}^k$.

What do we mean when we say that $H(x) < D$ for some $D\in \mathbb N$? Are we summing the elements of $H(x)$?


texts:
Party A has a ciphertext $c = (g^r, g^2 h^r)$, which is an encryption of the integer 2 under A's public key, $h$. The encryption scheme used is the additively homomorphic variant of El Gamal. This ciphertext has been homomorphically modified by other parties, so A does not know the randomness $r$.

Is there a way for A to prove that $c$ is an encryption of a non-negative integer? All of the range proof schemes I have found seem to use commitments, which require A to know the randomness in the ciphertext.


texts: Turning a cipher into a hashing function

texts:
This is theoretical question. I'd like to know if it's possible (and what are eventually the consequences), not that I'm going to do it in one of my projects. ;)

The first hashing functions created were based on a symmetric cipher (just like the first Unix crypt was based on DES). The idea was simple. Use the password as key to encode a constant.

I'd like to know if it's still possible to convert any modern symmetric cipher into a hashing function (and second question: into a cryptographic hashing function). Is it possible (easier) to guess the key, when you have an encoded and decoded messages?


texts:
Let's say we have a program that only accepts numerical inputs and the output is simply an increment by one of the input.

Example with input "a" and output "b":

$$Input: a = 7$$

$$Output: b= a+1 = 8$$

So it would be easy to know what the program is doing.

Is it possible to obfuscate the program code in such a way that we can never be sure how it's done?

For example our program could take the input:

$$7$$

double it:

$$14$$

subtract input - 1

$$14 - (7 - 1) = 8$$

Is it possible to obfuscate the exact functionality, so that it can't be reverse-engineered? If not: Could such an obfuscation scheme exist one day or is there something fundamental that prevents it?


texts:
In a 2006 paper Bellare showed that HMAC remains secure even if collision resistance for MD5/SHA-1 is broken as long they are still PRFs.

The Wikipedia article on cryptographic hash functions mentions that

  In practice, collision resistance is insufficient for many practical
  uses. In addition to collision resistance, it should be impossible for
  an adversary to find two messages with substantially similar digests;
  or to infer any useful information about the data, given only its
  digest. In particular, should behave as much as possible like a random
  function (often called a random oracle in proofs of security) while
  still being deterministic and efficiently computable.

It seems to me that in practice hash functions are usually considered to be PRFs. Is this valid and are commonly used compression functions all PRFs?

Note: The Bellare paper states

  (There are to date no attacks that compromise the pseudorandomness of
  the compression functions of MD5 or SHA-1.)

Has this changed since then?

An interesting related paper by Kim et al., also from 2006, gives distinguishers for HMAC based on SHA-0 and HAVAL to distinguish it from HMAC with a random function. Which at least hints that it might be hard to determine if a compression function is a PRF.


texts:
Is it correct that increasing the iteration possibly decreases the cipher strength but increases the amount of time it would take to find the original hash values if using brute-force on a given hash? (i.e. from a compromised database)?

In other words, if someone accessed user password hashes would be better to protect against weaknesses in the cipher implementation or weaknesses in the amount of time it takes to calculate hashes?

public function hash_password(password, usersalt)
{
    var result = hash('sha256', usersalt . SITE_SALT . password);

    for (i = 0; i < 100; i++)
    {
        result = hash('sha256', usersalt . SITE_SALT . result);
    }

    return result;
}

Note: SITE_SALT is a value stored in a configuration file outside the document root. usersalt is a unique salt generated for each user and stored with the password hash in a database.


texts: Differential or Truncated Differential Attack On Small Cipher

texts:
The cipher given below is a  16-bit toy cipher which uses 8-bit sbox and 2x2 byte Matrix. The Key $k_0$ and $k_1$ are $\oplus$ with the data. The multiplication with matrix is performed in $GF(2^8)$ with irreducible polynomial of $x^8+x^4+x^3+x+1$

The differential probability (DP) of the sbox for input difference of $0x01$ and output difference of $0x01$ is $40/256$.

For simplicity, it is assumed that $k_0$ and $k_1$ both are same, so guessing $k_1$ is enough.

A Brute force attack will take an effort of $2^{16}$ keys to be tested. How differential attack can be mounted with effort less than brute force.

I tried to mount attack differential attack with input pairs which has a difference of {$0x01$,$0x00$} but this required doing an effort of $2^{16}$. I did following

Get ciphertext of 256 chosen plaintext pairs which has difference of
{$0x01$,$0x00$}.
For all values of $k_1$ , Xor $k_1$  with Ciphertext pair, run it through invMatrix, pass it to inv of sbox and then Compare the difference
If difference if equal to  {$0x01$,$0x00$}, increment the count for this value of K1
The Key with highest increment is valid value of $k_1$

The content of Sbox is

6A, 3F, BF, 3D, BA, 2F, 91, B3, 1A, 52, F4, DE, 9B, D4, 7D, 7A,
72, 5A, 11, 36, A7, F5, E0, A0, E4, AC, 08, 1B, 50, F3, DC, 9A,
D7, 8B, AB, 09, 1D, 54, FE, FC, F8, EB, C9, 68, 44, CE, 78, 73,
62, 31, 98, D3, 87, A1, EC, C8, 67, 47, E2, AE, 16, 46, DD, A3,
FB, F6, E7, BE, 51, 0A, 20, 5E, 29, 81, 8E, BB, 42, D2, 8C, B7,
39, B9, 40, CD, 7B, 83, 9C, ED, CA, 6F, 66, 4E, 07, 1E, 5C, 27,
80, 90, C0, 49, EF, D1, 85, A4, 02, 0B, 1C, 57, 15, 43, D9, 95,
CF, 7C, 89, AF, 1F, 58, 18, 4D, FF, 00, 01, 03, 04, 05, 06, 0C,
0D, 0E, 0F, 10, 12, 13, 14, 17, 19, 21, 22, 23, 24, 25, 26, 28,
2A, 2B, 2C, 2D, 2E, 30, 32, 33, 34, 35, 37, 38, 3A, 3B, 3C, 3E,
41, 45, 48, 4A, 4B, 4C, 4F, 53, 55, 56, 59, 5B, 5D, 5F, 60, 61,
63, 64, 65, 69, 6B, 6C, 6D, 6E, 70, 71, 74, 75, 76, 77, 79, 7E,
7F, 82, 84, 86, 88, 8A, 8D, 8F, 92, 93, 94, 96, 97, 99, 9D, 9E,
9F, A2, A5, A6, A8, A9, AA, AD, B0, B1, B2, B4, B5, B6, B8, BC,
BD, C1, C2, C3, C4, C5, C6, C7, CB, CC, D0, D5, D6, D8, DA, DB,
DF, E1, E3, E5, E6, E8, E9, EA, EE, F0, F1, F2, F7, F9, FA, FD


texts: Design a OT-based Private Set Intersection protocol to obtain $A \cap B \cap C$?

texts:
This is a tutorial question for a Foundations of Privacy computer science course, I'm unsure on how to tackle it because we haven't talked much about these particular topics in class.

(a) Assume Alice, Bob and Carlo respectively have the data set $A = \{ \ldots \}$, $B = \{ \ldots \}$, $C = \{ \ldots \}$. How to use the OT-protocol to design a Private Set Intersection protocol among Alice, Bob, and Carlo, so that each one can obtain $A \cap B \cap C$. You can design your solution based on the OT-based PET (Private Equality Test) protocol in the figure below.

PET Figure

(b) How to use the OT-protocol to design a privacy-preserving integer comparison protocol between two parties, e.g., two integers $x,\space y$, both of them are $n$ bits, where $x \gt y, \space x \lt y,$ or $x = y$. You can design your solution based on the above OT-based PET protocol. (Hint: you may disclose two bits information in your solution!)

I think I understand what to do for (b):

If Alice and Bob use a homomorphic encryption algorithm, Alice can
use a private key pk and a public key sk. Bob would only have the
public key pk.
Alice then sends $\text{E}(x)$ and $\text{E}(y)$ to Bob. Bob computes
$\text{E}(r(x-y)) =$ $($$\frac{\text{E}(x)}{\text{E}(y)})^r$ using the homomorphic
property, where $r$ is a random number, and returns $\text{E}(r(x-y))$ to
Alice.
Alice recovers $r(x-y)$, and if it is equal to $0$, then $x = y$,
otherwise $x \not= y$.

With this solution, are the only bits disclosed the ones that are given in the comparison result? I'm a little more foggy on how to attempt (a). Any help is appreciated!


texts:
I'm working on a short story taking place in the near future in which a hacker gains access to the DARPA mainframe and files related to a highly classified DARPA project.

Being ignorant about state of the art cryptanalysis techniques, is it safe to say it would be virtually impossible to decipher encrypted DARPA files unless our rogue programmer has access to a quantum computer?


texts: How is an AES S-Box cyclically shifted to the left?

texts:
I'm trying to an implement an enhanced version of AES which was proposed recently. The link to the paper is here: http://sdiwc.net/digital-library/enhancing-aes-using-novel-block-key-generation-algorithm-and-key-dependent-sboxes

In their proposed algorithm, a unique S-box is created for each round by XOR'ing all 16 bytes of the round key, and cyclically shifting the original static S-Box to the left by that value. I'm new to cryptography in general, and I understand the original AES algorithm well, but I don't understand what the authors mean by cyclically shifting the S-Box. Obviously, each individual byte can't be shifted, since the shift values produced are as high as 127. Is it each row of the S-Box that has to be shifted, or are all 256 bytes lined up somehow and shifted?


texts:
Let $n$ be the size of the image-space of a hash function $H$.

It is known that you can find a collision on $H$ in $O(\sqrt{n})$ time (by birthday paradox).

How can I show that, in order to find $k$ collisions, it is needed only $O(\sqrt{k\times n})$ time?

I have no idea yet... I guess this happens because after you look $O(\sqrt{n})$ times for collisions, the probability grows significantly, but I don't know where I can apply $k$.


texts: Fastest algorithm for message authentication?

texts:
I'm searching for the fastest way to verify that a message was sent by the correct user.

The first solution I know of is to use HMAC. But in order to verify, I'll have to produce another signature and compare it with the original. In my case, this does not seem to be the best choice, because the time needed to verify is practically equal to the time needed to produce the signature.
To use a classic cryptographic signature (RSA or AES) over a MD hash.     I didn't find benchmarks/times for verifying a signature (but just for producing the signature). Surely, to produce a signature is slow, but to verify?
Finally, is there any algorithm that use a statistical  method for granting authentication (most of the messages are valid)?

After comparing benchmarks, it seems there is a third way which is a lot faster (10 times more): to use the GMAC/VMAC algorithms.

I'm developing in Java, but a C/C++ library would also be OK.

Specifically, my questions are:

Can you confirm that the best solution is GMAC/VMAC for this scope?
If yes, does anyone have an example for how to write the code for generating/verifying a byte array in Java (perhaps with the Bouncy Castle library).


texts: When to use RSA and when ElGamal asymmetric encryption

texts:
If i am not wrong in cryptography there are 2 basic cryptographic schemes for public key cryptography. RSA encryption whose security is based on the infeasibility of solving the factoring of big primes problem and the ElGamal encryption which is as secure as the discrete logarithmic problem. The question is whether or not there are specific circumstances where you must use ElGamal instead RSA and vice versa. What are the weak and the strong points of each?

To sum up is it harder under the same attacking model to solve the factoring problem or the discrete logarithmic problem?


texts: Is RSA vulnerable to the padding oracle attack?

texts: I know that AES in combination with CBC mode is vulnerable against the Padding Oracle Attack. RSA also uses some kind of padding, hence can this attack be apply to RSA encrypted messages too?


texts: For the hash computation of SHA-256, is it computed in parallel or series?

texts:
I'm trying to write my own SHA-256 implementation in VHDL, which runs in parallel execution style

I have been using this as a reference to the SHA-256 algorithm: https://www.researchgate.net/file.PostFileLoader.html?id=534b393ad3df3e04508b45ad&assetKey=AS%3A273514844622849%401442222429260

In the hash computation where a, b, c, d, e, f, g, h, T1 and T2 are being calculated for 64 rounds, are these values being computed in parallel or sequentially?

For example, if we take the iteration number at 10 for the value e
e = d+T1
Does e take the value of d and T1 from the previous iteration 9, or the value of T1 which was just calculated in this iteration?

Thanks


texts:
I really want to learn how to calculate the number of active s _boxes for block cipher cryptographic algorithms.
I want to do that manually after running each round of an algorithm such as LED algorithm, what should I notice or compare in order to calculate the number of active s_boxes ?
I read that definition ".You run the algorithm with two different plaintexts (whose difference is usually small – just a few bits, everything else being equal).

Wherever these plaintexts lead to different inputs to an S-box (in any layer/round of the algorithm), we call this S-Box “active” (since the other S-boxes produce the same result for both plaintexts, they are called “passive” and are not considered further)"", and want to learn how to calculate the number of differential active s_boxes?


texts: Does the Shappening mean HTTPS can be broken?

texts:
For years we've been warned that SHA-1 is weaker than originally thought and should not be used.  This reached its peak with the Shappening and experts from Schneier on down have been warning that we should get off SHA-1, or something bad will happen.

What are the practical 'something bad's?  Once an attacker has the capability to create a SHA-1 collision, what then can they do?  I'm interested in confidentiality and integrity of HTTPS, but am open to broader answers.

Specifically would it be feasible to do a MITM attack by creating a fake certificate for an existing website?  It seems plausible: the attacker creates a fake certificate with the same name, but varies the other data in order to produce a SHA-1 hash that matches the SHA-1 hash of the original certificate.


texts: Build a hash function that returns a digest in $\mathbb{Z}_{N}^{\ast}$

texts:
I want to know if there is a way to build a Hash Function in a such way?

$\mathcal{H}:{\left\{ {0,1} \right\}^*} \to \mathbb{Z}_{N}^{\ast}$, $N=pq$ and where $p,q$ are primes.


texts: Why is SHA2 used for file verification if it's susceptible to length extension attacks?

texts:
Am I misunderstanding length extension attacks, or is there some different reason, or is it really a bad idea to use SHA2 for file verification?

If the answer is that it's really a bad idea, would removing the last 4 bytes be advisable since now the chances of the attack succeeding will be around one in 4 million, and we will have remaining, in the case of SHA512, 480 bits of security?


texts: Do Carter–Wegman MACs allow key reuse if the MAC tag is kept secret?

texts:
Poly1305 (and GHASH) are secure authenticators, but only for one use.  Thus, nonce reuse in Poly1305-AES, ChaCha20-Poly1305, and AES-GCM all reveal the authentication key.  However, my understanding is that this is because (in Poly1305-AES, ChaCha20-Poly1305, and AES-GCM) the output of the hash function is encrypted using a stream cipher, and as such nonce reuse gives away the XOR of the hashes.

Suppose that one uses AES in ECB mode to encrypt the authentication tag instead (using a secret key that is unrelated to the other keys, the message, and the nonce).  In this case, nonce reuse gives away no information unless the auth tags collide (which will only happen with probability about $2^{-56}$ or so).  Similarly, one could use Blake2 or Keccak to hash a nonce, secret key, and the tag to produce a larger tag.

At least this is all my understanding.  I am not a cryptographer, and I could be wrong!  Am I?

Note: I do not plan on using this in any actual software.


texts: Obtain Enigma key having a encrypted text and the plain text

texts: I have an Enigma message and I know what the original message is (a repetition of the same letter). Is it possible obtain the enigma key? I only know what kind of Enigma machine is it, but I need to guess the config. parameters.


texts:
So people say to choose $d$ such that $e*d=1(mod((p-1)*(q-1)))$.

However, $1\%$ anything always equals $1$. Maybe I am not understanding it correctly, but the only way to get $e \cdot d=1$ is just by doing $e^{-1}$ which leads into a very very small number $\lll 1$ because $e$ is large.

How are people getting $e$ and $d$ such that they are both large numbers?

My main confusion really just comes from that $1\%$ anything always equals $1$.


texts: Simple explanation of Miller's algorithm

texts:
Could someone explain to me in few lines (even one sentence) what Miller's algorithm computes?

Without talking about divisors and all the other concepts, I would like to be able to explain it to someone who doesn't necessarily know elliptic curve cryptography in details but understands the basics because it's a really abstract concept.

Like what is the value returned by the Miller's function and why use this function ?


texts: Succint, interactive proof that $y^2 = x$ in $\mathbb{Z}^*_p$

texts:
Let $p$ be a large prime, such that $(p = 3) \mod{4}$. Let $x$ be an element of $\mathbb{Z}^*_p$ such that, for some $y \in \mathbb{Z}^*_p$, we have $y^2 = x$. It is a well-known result that $y = x^{\frac{p+1}{4}}$: $y$ can be computed from $x$ through a sequence of repeated squarings, which makes $y$ long to compute from $x$.
Now, consider the case where a prover wants to prove to a verifier that it computed $y$ from $x$ (both $x$ and $p$ are known to both). Trivially, the prover can send $y$ to the verifier, which can verify $y^2 = x$.
However, since $p$ is large, the approach above can be heavy from a communication point of view. So, I am wondering if some mechanism like the following exists:

The verifier randomly selects a (small) challenge $c$, which it sends to the prover.
From $c$ and $y$, the prover (quickly) generates a (small) proof $r$, which it sends back to the verifier.
The verifier (quickly) verifies the correctness of $r$, establishing that the prover indeed computed $y$.

Here, by small I mean significantly smaller than $p$, $x$ or $y$. By quickly I mean significantly faster than the time required to compute $y$ from $x$.


texts: Is there a password hash function with a human component?

texts:
Sort of Related: Is there a cryptographic hash function that can be performed with pencil and paper?

One problem with hashing passwords is that the attacker has more of everything it seems. More speed, more memory, more time, newer algorithms, etc. It's a constant race to keep up. We have the advantage of having to try less passwords, but even that is only somewhat enough.

What if we threw a human into the mix? Currently, solving 1000 captchas, for example, is \$2. If we had a task as complex as a captcha incorporated into a hash function, and the attacker needed a billion guesses, that would be \$2,000,000 to crack one password.

Of course, incorporating captcha into a hash function I'm pretty sure would be impossible. But there are other tasks that humans seem better that are purely computational. For example, see foldit.

The idea is that when the user enters their password, at a certain step in the hash function, there would be a problem that a human can solve much more efficiently, and the human does it (it can, for example, be presented as a game). It would probably be for the more security conscious, depending how "fun" the hash function is to compute.

Is there such a thing? Is there a hash function such that one of the steps is much more efficient for a human to compute, while still being cryptographically secure?

Note: As for why captchas probably wouldn't work is this, there are only two approaches I can imagine, neither of which works:

The algorithm produces an image for the human to solve (based on the input and other parts of the algorithm). The human solves it, and the algorithm factors that into the hash. The problem is that, unless it used some direct method, to generate a captcha it would need to generate a random word, and then create a distorted image of that word. An attacker can simply edit out the "create a distorted image" step from the algorithm, and no human is necessary. (Perhaps cryptographic obfuscation could be used to prevent removing the distortion part of the algorithm, but that technology is practical yet.)
Same as above, but to generate the captcha, and has a huge base of images. Keep in mind that it simply needs to be a captcha, the algorithm doesn't need to know what word goes with each captcha (that's what the humans for). The problem is that A) you would need an infeasible number of images to make it secure and B) whoever is generating all these captchas may make them in such a way that they know what how to solve them.

Also, computers are somewhat good at solving captchas.

Okay, here's what I think we need:

There must be a very large number of problems (on the same order as the number of passwords/inputs).
A computer must be able to efficiently generate a random problem without knowing the solution.
A human must be able to solve the problem a couple of orders of magnitude better than a computer.

It should be hard for the computer to guess the answer as well. This means the space of possible solutions needs to be large.

There should be a unique solution.

The computer should be able to check if something is a solution

Bonus: Being fun

With these, what we do is:

Use the password/input to seed a random number generator
Generate a random problem
Have the human give the solution
Now process that into the final hash

Steps #1 and/or #4 will involve computer hashing algorithms. (It doesn't need to exactly follow the above steps; I'm just trying to reduce it to a simpler problem.)


texts: Can someone give me an idea of active areas relating to pairing based cryptography, and what they involve?

texts:
Apologies if this isn't the place to ask this question. I'm an undergraduate math student and I've been reading about elliptic curves. I've learned about the Weil and Tate pairings as well as Miller's algorithm. I was hoping someone would be able to give me some information about what's "out there" that I could look at to continue my reading. I've read that there's active research in the problem of building pairing-friendly curves, and also trying to optimize Miller's algorithm for special cases.

Are there any other topics that I should consider looking into? I'm a bit hesitant to dive into the issue of building pairing-friendly curves. It seems very technical and heavy on the math. I like math, but I'd like to get a little taste of computer science if possible.


texts: Is it possible to make an encrypted text look like a sentence consists of random words?

texts: Without having any knowledge of common encryption methods, I wonder if an encrypted text can look like random valid words as if it is a sentence. Is it possible? If so, what methods should I use?


texts: Signal Double Ratchet - How can Alice send 2+ messages in the beginning of the Signal Protocol?

texts:
I'm studying about Signal Protocol and I had a doubt in Double Ratchet Algorithm. This section describes how to derive the receiving and sending key messages.

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


texts: Is the RC4 KSA the same as an extractor?

texts:
I am studying the RC4 stream cipher, particularly when it used to be applied in the TLS/SSL protocol.

Is it safe to say the KSA acts like an extractor taking in the shared secret key, k (between 128bits and 256bits) and then blows it up to a scrambled 256 byte array?

Then this is essentially used as a "seed" for the PRGA that comes next?

If the above is correct, then what is the difference then between an extractor and a key-scheduling algorithm?

NOTE: I have zero intention of using RC4 in any TLS application, this is purely for my own education.


texts: Elliptic Curve Point at Inifnity in Projective Coordinates

texts:
I'm implementing an elliptic curve system primarily for ECDSA verification. I've evaluated different point representations and decided that using Jacobian projective coordinates suits best for my needs. Using this representation the point at infinity $\infty$ corresponds to $(X:Y:Z)$ = $(1:1:0)$.

As it is required to check for the point at infinity $\infty$ inside the point doubling and point addition functions, I'm currently comparing all three coordinates of an elliptic curve point to $(1:1:0)$. My question here is, if it would already be enough to check only for $Z=0$. As you can imagine this could make some difference in terms of performance, as doublings and additions are repeatedly called for point multiplication and omitting the check for $X$ and $Y$ would thus reduce some time.

Is checking for $Z=0$ enough? Could there be any corner cases for which I get $Z=0$ but actually have not reached the point at infinity? I've tested it with a high number of ECDSA verifications, and it seems to work but who knows if I have really tested the "special" cases especially on curves with 512-bit order.


texts:
If an attacker had a padded message and its corresponding CBC-MAC tag, how would they construct another message which produces the same tag for the same key as the original? The padding scheme used in this scenario is to add 0's to the end of the message until is it a full block.

What about when the attacker has an non-padded message? How would they accomplish a similar attack and what conditions are needed for the message for the attack?


texts: Hash and (MAC) based signatures using zk-SNARK

texts:
I was wondering if we could use any general symmetric key MAC, a collision resistant hash $H$ and zk-SNARK (or any general NIZK scheme) to construct a signature scheme. I have a MAC key $k$, which is also my private key, and the public key is $h = H(k)$. As a signature for the message is $(mac = MAC_k(m),\pi)$  where $\pi$ refers to a proof using SNARK circuit which takes public input $m,h,mac$ and private input (witness) $k$ and calculates $mac' = MAC_k (m), h' =H(k)$ and outputs $1$ iff $mac=mac'$ and $h'=h$ .
Looks like we need to be extra careful if the MAC above is an HMAC with the same hash function $H$ since it uses actual $Key' = H(Key)$ if the $Key$ longer than block size,other than that are there other issues with it?
Is it secure?
If it is not secure can anyone give a reason why? Way to recover key or forge a signature would be even better.


texts: Enforcing Randomness in Malicious Setting

texts:
I was going through some lecture notes where it said that if we have a 2-party protocol that requires both the parties to generate random integers during the course of protocol, then if we migrate the protocol and tweak it to make it work in Malicious setting, then we need to ensure that both parties instantiate random numbers which are indeed random.

It said that this can be achieved by using the following protocol:

$P_1$______________________________________________________$P_2$
commitment($s_1$) -------------------------------------------------->>
<<------------------------------------------------------commitment($s_2$)
$s_2'$----------------------------------------------------------------------->>
<<---------------------------------------------------------------------------$s_1'$

Now, both parties can find their random number $r_i$, $i\in \{1,2\}$ as
$r_i = s_i \oplus s_i'$.
I had a doubt that how does a party ensure that the other party will find $r_i$ as $s_i \oplus s_i'$ and not as just $r_i = s_i$?
How is this ensured that both parties will find their $r_i$s in the exact same way as the protocol says?


texts: multi-theorem vs single-theorem for non-interactive zero knowledge

texts:
I am trying to understand the definition of zero knowledge for non interactive zero knowledge (signature of knowledge). Sometimes I find multi-theorem zero knowledge, sometimes I find single-theorem. What's the difference ?

My main task is to show that a Zero Knowledge Signature of Knowledge which is zero knowledge (for one signature) is zero knowledge for several signatures. In other words, if you don't reveal anything by signing one message, you don't reveal anything if many people sign many documents with this ZKSoK.


texts: What exactly is a multi-target attack? How does the attack work on different cryptographic schemes (block ciphers, hash functions, elliptic curves)? How can it be avoided?


texts: What are the disadvantages of XOR key derivation?

texts:
Assume a 256-bit Key and a 256-bit Salt, with uniformly distributed entropy, both fully independent.

Assume Key is secret and Salt is public.

What theoretical advantages would deriving an AES-256-CTR encryption key using Key XOR Salt give to an attacker?

Assume that the product of Key XOR Salt will remain secret.

Assume that a KDF such as HKDF or a PRF such as HMAC cannot be used.


texts: Why we can't implement AES 512 key size?

texts:
Out of curiosity why we can't implement AES 512 key size?

Please explain somehow i can understand! I'm not an expert.


texts: What is the difference between known-plaintext attack and chosen-plaintext attack?

texts:
I am very confused between the concept of known-plaintext attack and chosen-plaintext attack. It seems to me that these two are the same thing, but it definitely is not.

Can anyone explain to me how these two differ?


texts: Does having multiple hash iterations of the same message weaken your original message security?

texts:
Take a hash function H() to be something like SHA-256 and message m. If you are given H(m) and H(H(m)), can you use this info to help derive m?

Also interested in knowing how you analyze this problem to come up with your answer.


texts:
It is commonly understood that CRC satisfies the linear identity with respect to the $\oplus$ (XOR) operation:

$\operatorname{CRC}(a) \oplus \operatorname{CRC}(b) = \operatorname{CRC}(a \oplus b)$

But after some experimentation and research it appears that this is not generally true.

The particular algorithm in question is the one used in HDLC, ANSI X3.66, ITU-T V.42, Ethernet, Serial ATA, MPEG-2, PKZIP, Gzip, Bzip2, PNG (see Wikipedia) which uses the polynomial $\mathtt{0x04C11DB7}$.

In what sense is CRC linear? Is this a misconception?


texts: Proper number of salt bytes for Rfc2898DeriveBytes/PBKDF2

texts:
I know that .NET's Rfc2898DeriveBytes requires at least 8 bytes of salt, but how many bytes are ideal?

When a user is created, or changes their password, my server stores a new random salt for that user, and a "hash", which is really just some number of bytes from Rfc2898DeriveBytes (ed: .NET's implementation of PBKDF2), using the user's password and the salt, and 5000 iterations.

My client app connects to the server via SSL, sends the user's user name, the server sends the salt for that user, the client calls Rfc2898DeriveBytes with the user's password and the salt, and sends that "hash" to the server for authentication.  If the server receives an invalid user name, it returns a random salt, so that the client doesn't know whether the user name or the password is invalid, and so some time is wasted to hamper hacking.

My understanding about salt is that it's really only intended to get different keys for the same password, which would lead me to think that 8 random bytes should suffice, but since I'm sending it over SSL, I'm wondering if a longer salt would increase security somehow.

Besides the number of salt bytes, how many "hash" bytes would be best?


texts: How the message is decrypted in an RSA chosen ciphertext attack when it's a modulo?

texts:
During the last stage of decryption of a chosen ciphertext attack we are left off with this equation
$$c = m \cdot t \pmod n$$
Removing all exponents like $d$ and $e$ where $c$ is the decrypted message which (doesn't mean anything), $t$ is the message we multiplied original ciphertext with, $m$ is the message we want.
If we substitute with value like these after decryption $c=2$, $t=2$, $n=5$ for example, we get:
$$2 = (m \cdot 2) \pmod 5$$
But here $m$ can be many different values. It can be 6 or it can
be 11: $(6*2) \bmod 5 = 2$. I mean it's a clock so many options for $m$ would give same decrypted ciphertext output.


texts: Using what we already know about the data to decrypt it?

texts:
Are there any methods or tools out there that let us use what we know about the data in order to crack the encryption?

For example let's say I get access to an encrypted database file but I know everything about it... Let's say I know it's a RDBMS, the table & field names, and the primary keys/foreign keys. Since I know the field names I also know what will be stored as boolean, string, numeric, date/time, etc.

Would this or any other information about the data help with decryption? (Maybe the character encoding)

I'm not talking about cracking a password that "decrypts" the file for us (like public/private key), I am wondering about decrypting the actual data.

I'm not very educated on encryption or ciphers, but I can't seem to find any information about introducing the human element into decryption. Sure it may take more time than the universe has existed to break AES encryption using a billion gpgpus processing in parallel, but this is only brute force -- shouldn't we be able to narrow down the the possibilities based on whether the output makes sense?

Just so I could play around with this idea, is there any software that will output the results of the keys that are tried?

I guess a better question with more scope would be, "Is there any way to narrow down our possibilities?"


texts:
I am fairly new to HE and would like a short clarification on how exactly integers are securely encrypted using bits. The main idea is that one encrypts each bit value and represents the n bit number as n ciphertexts like this: $$E(x)=(E(x1),E(x2),...,E(xn))$$ where xi is the bit on position i. Why is that secure, when I have just ciphertexts that correspond to '0' and '1' in a particular order? Example:
$$101 -> (E(1), E(0), E(1))$$  Can't I just guess 101 only from the E() values.
Why is this not possible?
Pointing me out to a good paper or read on that would be greatly appreciated!


texts: How can I prove the result of a long computation with a short string?

texts:
I have a simple program F (think of a cellular automaton) that, when executed in some input X, takes a while to complete and returns a short result (a hash function, for example). How do I produce a short string that proves the result F(X) = Y without requiring the verifier to run the entire computation?

I'm aware of zk-snarks, but I couldn't a simple, practical "get started" guide to them. Moreover, they might be overkill for this since I don't need any privacy.


texts: Back up an information as $n$ pieces and require exactly $n-1$ to recover it

texts:
Let $X\in \Bbb F_2^p$ be some information.

How do I create $Y_1,\dots,Y_n \in \Bbb F_2^q$ so that having less than $n-1$ of the $Y_i$s gives you no information on $X$ but having $n-1$ of them allows you to recover $X$?

I first though of error correcting codes, but I don't think those would be able to ensure that having less than $n-1$ of the $Y_i$s would give no information.

My second thought was to use some kind of one time pad. For a given $r\in\{1,\dots,n\}$ (which is the index of the $Y_i$ we won't use to recover $X$), you could let $Y_r=0$, let $n-2$ of the remaining $Y_i$s be random elements of $\Bbb F_2^p$ and let the last $Y_i$ be the sum (meaning XOR) of the other ones and $X$. Then you could concatenate that for every $r\in\{1,\dots,n\}$. In other words, you use $n-2$ of the $Y_i$s to create a one time pad and use it to encrypt $X$ in the last $Y_i$. But that seems a bit brutal to me. You would need $q=np$.

I was wondering of there was a way to do it so that $q=\mathcal O(p)$ (meaning it doesn't depend on $n$).

The first thing that comes to mind is to make the $Y_r$ with three elements: its index, one random element of $\Bbb F_2^p$ and the sum of $X$ and the $n-1$ $Y_i$s that after this one including it (so $Y_r,\dots,Y_{r+(n-2)}$, where you reduce the indices modulo $p$ in the obvious way). This way, when you have $n-1$ of the $Y_i$s, you can find which index $r$ which is missing and then sum the third part of $Y_r$ with the second part of $Y_r,\dots,Y_{r+(n-2)}$ and recover $X$. That would be $\mathcal O(p\log n)$ (because of the index) which is acceptable. But I feel like you could recover part of the message with less than $n-1$ of the $Y_i$s because you kind of used the one time pad several times.

Edit: I'll use it in https://github.com/xavierm02/combine-keys


texts: Elliptic curve trapdoor function without modular arithmetic?

texts:
From what I understand, an elliptic contains a set points satisfying the equation

$y^2=x^3 + ax + b$

together with the point at infity.

It seems clear how multiplication with a scalar and a point works, and how point addition works. Discussions about cryptographic applications usually jump right to curves defined over finite fields at this point. I think I understand how that works as well.

What doesn't make sense is whether a curve defined over the field of real numbers could also work as a trapdoor.

If I know that point Q results from multiplication of some integer with the generator point on a curve over real numbers

$Q = dG$

what feasible methods exist to compute d given only a, b, and Q, and G?

In other words, aside from convenience in implementation, what exactly does the finite field add to elliptic curves as trapdoors?

I've seen this discussion, but it doesn't seem to directly address the question here.


texts: Can someone explain how OPRF (Oblivious pseudo-Random Function) is based on OT (Oblivious Transfer)?

texts:
Can someone explain to me how OPRF is based on OT extensions? I'm currently reading papers about private set intersection problem that uses efficient OT-based protocols based on OPRF, the link of the paper is here: https://eprint.iacr.org/2016/930.pdf.

I understand how the OT-based PSI works,  and how the OPRF is used for PSI, but I’m confused in understanding how the OPRF is implicitly used in the OT-based PSI. And also in the paper's proposed protocol, I can’t see the difference (in the computational cost) in case we use only OPRF for the PSI and in case of evaluating OPRF via OT.

From what I understand in their protocol (s+b) OPRFS will be used, and from my understanding if we just used OPRF for PSI we will use almost the same number of OPRFs instances, it’ll be depending on the number of inputs. So what’s the difference?


texts: Any Idea on this identification scheme's problem?

texts: I was looking at the exercises of Cryptography theory and practice and I could not find the answer to this question anyone has an idea?


texts: What is the sign bit for in Feige-Fiat-Shamir?

texts:
The Feige-Fiat-Shamir identity scheme is based on a ZKP assuming that square roots are "hard" modulo an integer of unknown factorization.  The "parallel version" of this protocol includes a "sign bit" and the wikipedia article claims that the older version of the protocol leaked a bit, so the sign bit was added.  Here is the protocol as given by wikipedia:

Peggy chooses a random integer $r$, a random sign $s\in\{-1,1\}$ and computes $x \equiv s\cdot r^2 \pmod{n}$. Peggy sends $x$ to Victor.
Victor chooses numbers $a_1, \cdots, a_k$ where $a_i$ equals 0 or 1. Victor sends these numbers to Peggy.
Peggy computes $y \equiv rs_1^{a_1}s_2^{a_2} \cdots s_k^{a_k}\pmod{n}$. Peggy sends this number to Victor.
Victor checks that $y^2 \equiv \pm\, x v_1^{a_1}v_2^{a_2} \cdots v_k^{a_k}\pmod{n}$.

I cannot find the old version of FFS, nor do I see what bit is leaked without the sign bit added.  It must be something related to a Jacobi symbol?!

The relevant quote from Wikipedia that I'm asking about is:

  In an early version, the Fiat-Shamir-Scheme (on which the
  Feige-Fiat-Shamir-Scheme was based), one bit of information was
  leaked. By the introduction of the sign s even this bit was concealed
  resulting in a zero-knowledge-protocol.

So if this sign value $s$ were removed, what would be leaked?

Note: After reading Samuel's response, I wonder if the wikipedia version of the scheme is actually correct?!


texts:
I am now reading a paper 'The Exact Security of Digital Signatures - How to Sign with RSA and Rabin' and there is an equation e = (q_sig + q_hash) * e' on page 401.
(e : success probability of RSA, e' : success probability of RSA-FDH)

What I want to know is the relation between query count(q_sig, q_hash) and security parameter k.
Is query count is proportional to poly(k) or 2^k?

In case of RSA, k is the bit length of modulus. So I feel like it should be proportional to 2^k.
And if it is proportional to 2^k, how is e is guaranteed to be negligible in case e' is be negligible?

Thanks in advance.


texts: I am curious to know whether (Yao's) garbled circuits are actually deployed in practice. There has a lot of works on optimising garbled circuits (e.g., here and here) and I am interested in whether these simply of theoretical interest or with practical applications in mind. (A quick Google search did not yield much.)


texts: EdDSA point encoding difference between documentation and implementation

texts:
The RFC 8032 describes the point encoding like this :

A curve point (x,y), with coordinates in the range 0 <= x,y < p, is
coded as follows.  First, encode the y-coordinate as a little-endian
string of 32 octets.  The most significant bit of the final octet is
always zero.  To form the encoding of the point, copy the least
significant bit of the x-coordinate to the most significant bit of
the final octet.

And implements it like this :
def point_compress(P):
    zinv = modp_inv(P[2])
    x = P[0] * zinv % p
    y = P[1] * zinv % p
    return int.to_bytes(y | ((x & 1) << 255), 32, "little")

Could you explain the meaning of the word "copy" in this sentence "copy the least significant bit of the x-coordinate to the most significant bit of the final octet" ? Why isn't the bit copied in the code ? Why is it just a bitwise OR ?