To decrypt a cipher text encrypted using keyed substitution I'm looking for decryption of this cipher text which was encrypted using simple substitution using secret key. I have already spend a lot of time on this. However it should not be that tough. So I think my procedure may not be correct.

The question is something like this:

The secret key (a permutation of the English alphabet) was generated from a key letter and a keyword. The key word is an English word (names of cities and countries are allowed) having no repeated letters. The secret key is then derived by writing the key word beneath the key letter in the alphabet; followed by then writing the remaining letters of the alphabet in cyclic order after the key word.

For example,if the key letter is 'm' and the key word is LAND, then the secret key is:

a b c d e f g h i j k l m n o p q r s t u v w x y z
O P Q R S T U V W X Y Z L A N D B C E F G H I J K M

All punctuation and spaces were removed from the plaintext, which was then blocked into groups of 5 letters prior to encryption.

The cipher text is:

LUPFK LLVBB VSTBU PAPFK VBVST QEALE ZPBUV STEAL EZPME OHKSO LVSNP LVBBV STKSO
FKVBV STFKL BUPES YHBUV STBEO EWCLB BUPSL UPLKB KSOFK VBPOF VBUKY YUPAZ VTUBK
SOZKV SZKBB UPFPS NECSB PAPOB UPLBK BVESZ KLBPA YENXV STCRB UPBVN XPBEQ QVNPR
APRKA KBEAH BETEV STUEZ PQEAL CRRPA KSOKL XPOUV ZVQBU PQVDP BUVAB HBAKV SFECY
OLEES MPKYE STBUP QVDPB UVABH BAKVS UKLMP PSVSK SOTES PUKYQ KSUEC AKTEK SLFPA
POBUK BMAVL XEQQV NVKYM CBBUP APFKL KRKLL PSTPA OAERR POEQQ QEAHE CKYVB BYPTV
AYLUP LLVBB VSTEC BBUPA PESBU PLUVS TYPLV KLXPO UPABE TEVSB EBUPY KOVPL FKVBV
STAEE ZMCBL UPVSQ EAZPO ZPTAK DPYHB UKBLU PRAPQ PAAPO BELBK HECBL VOPBU PAPFK
LZEAP LNERP QEAVZ KTVSK BVESL UPLKV OLUPL KNKLP VLUEC YOLKH VZSEB PGRPN BVSTK
TVAYL KVOZK BBUPF MYKSX YHVBL KMEHV DPNEZ PQEAU PLUEC YOMPU PAPZA LKYPG KSOPA
LRPSN PAFKL BEMAV STUVZ EDPAQ AEZSE DKLNE BVKQE AZPBU PLBKB VESZK LBPAF UVLBY
POPBN

We know the following are the letters of the English alphabet, grouped by letters whose frequencies are approximately equal.

The letters in each group are listed in order of decreasing frequency:

Group 1:   e
Group 2:   t a o i n s h r
Group 3:   d l
Group 4:   c u m w f g y p b
Group 5:   v k j x q z

The  most  commonly  occurring  digrams  in  the  English  language,  in decreasing order of frequency, are:

th  he  in  er  re  on  an  en  at  es  ed  te  or  ti st

So I started with frequency analysis and some guesses and could find:

T was encrypted as L
H was encrypted as U
E was encrypted as P

A was encrypted as V
N was encrypted as S
D was encrypted as T

R was encrypted as A
S was encrypted as B

Am I doing things correctly?

I seem to be stuck after doing this. Are there any techniques that I get try to get this solved?

When trying to decrypt any substitution cipher, my first step would be to count the number of times each letter occurs in the ciphertext, and plot the ranked letter frequencies.  Doing that for your ciphertext yields the following plot:

P: 84 ##########################################
B: 73 #####################################
V: 60 ##############################
K: 59 ##############################
E: 56 ############################
L: 52 ##########################
S: 47 ########################
A: 45 #######################
U: 44 ######################
O: 26 #############
T: 24 ############
Y: 21 ###########
Z: 21 ###########
Q: 19 ##########
F: 15 ########
C: 13 #######
N: 13 #######
R: 12 ######
H: 11 ######
M: 10 #####
D:  6 ###
X:  6 ###
G:  2 #
W:  1 #
I:  0
J:  0

(If you suspect you might be dealing with a simple Caesar shift cipher, looking at the same plot sorted alphabetically can also be useful, since you may be able to spot some distinctive patterns like the A/E/I triple peak that can reveal the shift amount.)

Comparing this plot with typical English letter frequencies, the general shape looks very similar, suggesting that this is indeed an monoalphabetic substitution cipher.  The next step, then, is simply to try a few substitutions and see if they make sense.

For example, we might guess that the two most common letters in the ciphertext, P and B, stand for the plaintext letters E and T respectively.  This guess yields the following partially decrypted message (shown with the ciphertext in lowercase, and the corresponding candidate plaintext below it in uppercase):

lupfk llvbb vstbu papfk vbvst qeale zpbuv steal ezpme ohkso lvsnp lvbbv stkso
__E__ ___TT ___T_ E_E__ _T___ _____ _ET__ _____ __E__ _____ ____E __TT_ _____
fkvbv stfkl bupes yhbuv stbeo ewclb bupsl uplkb ksofk vbpof vbuky yupaz vtubk
___T_ _____ T_E__ __T__ __T__ ____T T_E__ _E__T _____ _TE__ _T___ __E__ ___T_
sozkv szkbb upfps necsb papob uplbk bvesz klbpa yenxv stcrb upbvn xpbeq qvnpr
_____ ___TT _E_E_ ____T E_E_T _E_T_ T____ __TE_ _____ ____T _ET__ _ET__ ___E_
aprka kbeah betev stuez pqeal crrpa ksokl xpouv zvqbu pqvdp buvab hbakv sfecy
_E___ _T___ T____ _____ E____ ___E_ _____ _E___ ___T_ E___E T___T _T___ _____
olees mpkye stbup qvdpb uvabh bakvs uklmp psvsk sotes pukyq ksuec aktek slfpa
_____ _E___ __T_E ___ET ___T_ T____ ____E E____ _____ E____ _____ _____ ___E_
pobuk bmavl xeqqv nvkym cbbup apfkl krkll pstpa oaerr poeqq qeahe ckyvb byptv
E_T__ T____ _____ _____ _TT_E _E___ _____ E__E_ _____ E____ _____ ____T T_E__
aylup llvbb vstec bbupa pesbu pluvs typlv klxpo upabe tevsb ebupy kovpl fkvbv
____E ___TT _____ TT_E_ E__T_ E____ __E__ ___E_ _E_T_ ____T _T_E_ ___E_ ___T_
staee zmcbl upvsq eazpo zptak dpyhb ukblu prapq paapo belbk hecbl vopbu papfk
_____ ___T_ _E___ ___E_ _E___ _E__T __T__ E__E_ E__E_ T__T_ ___T_ __ET_ E_E__
lzeap lnerp qeavz ktvsk bvesl uplkv olupl knklp vluec yolkh vzseb pgrpn bvstk
____E ____E _____ _____ T____ _E___ ___E_ ____E _____ _____ ____T E__E_ T____
tvayl kvozk bbupf myksx yhvbl kmehv dpnez pqeau pluec yompu papza lkypg ksopa
_____ _____ TT_E_ _____ ___T_ _____ _E___ E____ E____ ___E_ E_E__ ___E_ ___E_
lrpsn pafkl bemav stuvz edpaq aezse dklne bvkqe azpbu plbkb veszk lbpaf uvlby
__E__ E____ T____ _____ __E__ _____ _____ T____ __ET_ E_T_T _____ _TE__ ___T_
popbn
E_ET_

The first thing you should check is that there are no unlikely letter sequences like TTT that might indicate a wrong guess.  In this case, there aren't any, so we can assume for now that our initial guess that P=E and B=T may be correct.  (If we did find some weird-looking letter sequences, we might want to try swapping the guesses around, and seeing if P=T and B=E would yield more sensible-looking results.  We could also try assigning either P or B to the plaintext letter A, which can also be pretty common, etc.)

Once we're reasonably confident about our initial guesses, we can see if we may be able to infer any other ciphertext/plaintext letter pairs from them, e.g. by spotting likely words in the partial plaintext.  Conveniently, the most common word in the English language is the definite article "the", which just happens to contain both T and E.  Looking for patterns of the form T_E in the partial plaintext above, we can see that several of them have U as the middle ciphertext letter.  We may thus tentatively guess that U might stand for H in the plaintext, and try another partial decryption:

lupfk llvbb vstbu papfk vbvst qeale zpbuv steal ezpme ohkso lvsnp lvbbv stkso
_HE__ ___TT ___TH E_E__ _T___ _____ _ETH_ _____ __E__ _____ ____E __TT_ _____
fkvbv stfkl bupes yhbuv stbeo ewclb bupsl uplkb ksofk vbpof vbuky yupaz vtubk
___T_ _____ THE__ __TH_ __T__ ____T THE__ HE__T _____ _TE__ _TH__ _HE__ __HT_
sozkv szkbb upfps necsb papob uplbk bvesz klbpa yenxv stcrb upbvn xpbeq qvnpr
_____ ___TT HE_E_ ____T E_E_T HE_T_ T____ __TE_ _____ ____T HET__ _ET__ ___E_
aprka kbeah betev stuez pqeal crrpa ksokl xpouv zvqbu pqvdp buvab hbakv sfecy
_E___ _T___ T____ __H__ E____ ___E_ _____ _E_H_ ___TH E___E TH__T _T___ _____
olees mpkye stbup qvdpb uvabh bakvs uklmp psvsk sotes pukyq ksuec aktek slfpa
_____ _E___ __THE ___ET H__T_ T____ H___E E____ _____ EH___ __H__ _____ ___E_
pobuk bmavl xeqqv nvkym cbbup apfkl krkll pstpa oaerr poeqq qeahe ckyvb byptv
E_TH_ T____ _____ _____ _TTHE _E___ _____ E__E_ _____ E____ _____ ____T T_E__
aylup llvbb vstec bbupa pesbu pluvs typlv klxpo upabe tevsb ebupy kovpl fkvbv
___HE ___TT _____ TTHE_ E__TH E_H__ __E__ ___E_ HE_T_ ____T _THE_ ___E_ ___T_
staee zmcbl upvsq eazpo zptak dpyhb ukblu prapq paapo belbk hecbl vopbu papfk
_____ ___T_ HE___ ___E_ _E___ _E__T H_T_H E__E_ E__E_ T__T_ ___T_ __ETH E_E__
lzeap lnerp qeavz ktvsk bvesl uplkv olupl knklp vluec yolkh vzseb pgrpn bvstk
____E ____E _____ _____ T____ HE___ __HE_ ____E __H__ _____ ____T E__E_ T____
tvayl kvozk bbupf myksx yhvbl kmehv dpnez pqeau pluec yompu papza lkypg ksopa
_____ _____ TTHE_ _____ ___T_ _____ _E___ E___H E_H__ ___EH E_E__ ___E_ ___E_
lrpsn pafkl bemav stuvz edpaq aezse dklne bvkqe azpbu plbkb veszk lbpaf uvlby
__E__ E____ T____ __H__ __E__ _____ _____ T____ __ETH E_T_T _____ _TE__ H__T_
popbn
E_ET_

Again, we should check that the partial decryption looks plausible.  With the plaintext letters T, H and E tentatively assigned, one possible next step would be to look for plaintext patterns of the form TH_T, which might correspond to the (also fairly common) word "that".  As it happens, we find two such instances, both with the ciphertext letter K in the middle.  Looking at the letter frequency plot above, K is the fourth most common letter in the ciphertext, just slightly behind V in the third place, so it's entirely plausible that it might be the encryption of A, which is generally counted as the third most common letter in English on average.  With that guess, the partial plaintext becomes:

lupfk llvbb vstbu papfk vbvst qeale zpbuv steal ezpme ohkso lvsnp lvbbv stkso
_HE_A ___TT ___TH E_E_A _T___ _____ _ETH_ _____ __E__ __A__ ____E __TT_ __A__
fkvbv stfkl bupes yhbuv stbeo ewclb bupsl uplkb ksofk vbpof vbuky yupaz vtubk
_A_T_ ___A_ THE__ __TH_ __T__ ____T THE__ HE_AT A___A _TE__ _THA_ _HE__ __HTA
sozkv szkbb upfps necsb papob uplbk bvesz klbpa yenxv stcrb upbvn xpbeq qvnpr
___A_ __ATT HE_E_ ____T E_E_T HE_TA T____ A_TE_ _____ ____T HET__ _ET__ ___E_
aprka kbeah betev stuez pqeal crrpa ksokl xpouv zvqbu pqvdp buvab hbakv sfecy
_E_A_ AT___ T____ __H__ E____ ___E_ A__A_ _E_H_ ___TH E___E TH__T _T_A_ _____
olees mpkye stbup qvdpb uvabh bakvs uklmp psvsk sotes pukyq ksuec aktek slfpa
_____ _EA__ __THE ___ET H__T_ T_A__ HA__E E___A _____ EHA__ A_H__ _A__A ___E_
pobuk bmavl xeqqv nvkym cbbup apfkl krkll pstpa oaerr poeqq qeahe ckyvb byptv
E_THA T____ _____ __A__ _TTHE _E_A_ A_A__ E__E_ _____ E____ _____ _A__T T_E__
aylup llvbb vstec bbupa pesbu pluvs typlv klxpo upabe tevsb ebupy kovpl fkvbv
___HE ___TT _____ TTHE_ E__TH E_H__ __E__ A__E_ HE_T_ ____T _THE_ A__E_ _A_T_
staee zmcbl upvsq eazpo zptak dpyhb ukblu prapq paapo belbk hecbl vopbu papfk
_____ ___T_ HE___ ___E_ _E__A _E__T HAT_H E__E_ E__E_ T__TA ___T_ __ETH E_E_A
lzeap lnerp qeavz ktvsk bvesl uplkv olupl knklp vluec yolkh vzseb pgrpn bvstk
____E ____E _____ A___A T____ HE_A_ __HE_ A_A_E __H__ ___A_ ____T E__E_ T___A
tvayl kvozk bbupf myksx yhvbl kmehv dpnez pqeau pluec yompu papza lkypg ksopa
_____ A___A TTHE_ __A__ ___T_ A____ _E___ E___H E_H__ ___EH E_E__ _A_E_ A__E_
lrpsn pafkl bemav stuvz edpaq aezse dklne bvkqe azpbu plbkb veszk lbpaf uvlby
__E__ E__A_ T____ __H__ __E__ _____ _A___ T_A__ __ETH E_TAT ____A _TE__ H__T_
popbn
E_ET_

Next, we could try to look for more partial words, or we could simply guess a few more common letters.  The most common ciphertext letters that we haven't assigned to any plaintext letter yet are V and E; both seem to be occurring in places where one might expect a vowel, so we might tentatively guess that they stand for I and O in either order.  Of the two choices, V=I and E=O yields a somewhat more likely-looking partial plaintext:

lupfk llvbb vstbu papfk vbvst qeale zpbuv steal ezpme ohkso lvsnp lvbbv stkso
_HE_A __ITT I__TH E_E_A ITI__ _O__O _ETHI __O__ O_E_O __A__ _I__E _ITTI __A__
fkvbv stfkl bupes yhbuv stbeo ewclb bupsl uplkb ksofk vbpof vbuky yupaz vtubk
_AITI ___A_ THEO_ __THI __TO_ O___T THE__ HE_AT A___A ITE__ ITHA_ _HE__ I_HTA
sozkv szkbb upfps necsb papob uplbk bvesz klbpa yenxv stcrb upbvn xpbeq qvnpr
___AI __ATT HE_E_ _O__T E_E_T HE_TA TIO__ A_TE_ _O__I ____T HETI_ _ETO_ _I_E_
aprka kbeah betev stuez pqeal crrpa ksokl xpouv zvqbu pqvdp buvab hbakv sfecy
_E_A_ ATO__ TO_OI __HO_ E_O__ ___E_ A__A_ _E_HI _I_TH E_I_E THI_T _T_AI __O__
olees mpkye stbup qvdpb uvabh bakvs uklmp psvsk sotes pukyq ksuec aktek slfpa
__OO_ _EA_O __THE _I_ET HI_T_ T_AI_ HA__E E_I_A ___O_ EHA__ A_HO_ _A_OA ___E_
pobuk bmavl xeqqv nvkym cbbup apfkl krkll pstpa oaerr poeqq qeahe ckyvb byptv
E_THA T__I_ _O__I _IA__ _TTHE _E_A_ A_A__ E__E_ __O__ E_O__ _O__O _A_IT T_E_I
aylup llvbb vstec bbupa pesbu pluvs typlv klxpo upabe tevsb ebupy kovpl fkvbv
___HE __ITT I__O_ TTHE_ EO_TH E_HI_ __E_I A__E_ HE_TO _OI_T OTHE_ A_IE_ _AITI
staee zmcbl upvsq eazpo zptak dpyhb ukblu prapq paapo belbk hecbl vopbu papfk
___OO ___T_ HEI__ O__E_ _E__A _E__T HAT_H E__E_ E__E_ TO_TA _O_T_ I_ETH E_E_A
lzeap lnerp qeavz ktvsk bvesl uplkv olupl knklp vluec yolkh vzseb pgrpn bvstk
__O_E __O_E _O_I_ A_I_A TIO__ HE_AI __HE_ A_A_E I_HO_ ___A_ I__OT E__E_ TI__A
tvayl kvozk bbupf myksx yhvbl kmehv dpnez pqeau pluec yompu papza lkypg ksopa
_I___ AI__A TTHE_ __A__ __IT_ A_O_I _E_O_ E_O_H E_HO_ ___EH E_E__ _A_E_ A__E_
lrpsn pafkl bemav stuvz edpaq aezse dklne bvkqe azpbu plbkb veszk lbpaf uvlby
__E__ E__A_ TO__I __HI_ O_E__ _O__O _A__O TIA_O __ETH E_TAT IO__A _TE__ HI_T_
popbn
E_ET_

Now we can spot the repeating pattern ATIO_, where the following ciphertext letter is always S.  The suffix "-ation" is quite common in English words of Latin origin, so we may guess that S=N, giving:

lupfk llvbb vstbu papfk vbvst qeale zpbuv steal ezpme ohkso lvsnp lvbbv stkso
_HE_A __ITT IN_TH E_E_A ITIN_ _O__O _ETHI N_O__ O_E_O __AN_ _IN_E _ITTI N_AN_
fkvbv stfkl bupes yhbuv stbeo ewclb bupsl uplkb ksofk vbpof vbuky yupaz vtubk
_AITI N__A_ THEON __THI N_TO_ O___T THEN_ HE_AT AN__A ITE__ ITHA_ _HE__ I_HTA
sozkv szkbb upfps necsb papob uplbk bvesz klbpa yenxv stcrb upbvn xpbeq qvnpr
N__AI N_ATT HE_EN _O_NT E_E_T HE_TA TION_ A_TE_ _O__I N___T HETI_ _ETO_ _I_E_
aprka kbeah betev stuez pqeal crrpa ksokl xpouv zvqbu pqvdp buvab hbakv sfecy
_E_A_ ATO__ TO_OI N_HO_ E_O__ ___E_ AN_A_ _E_HI _I_TH E_I_E THI_T _T_AI N_O__
olees mpkye stbup qvdpb uvabh bakvs uklmp psvsk sotes pukyq ksuec aktek slfpa
__OON _EA_O N_THE _I_ET HI_T_ T_AIN HA__E ENINA N__ON EHA__ ANHO_ _A_OA N__E_
pobuk bmavl xeqqv nvkym cbbup apfkl krkll pstpa oaerr poeqq qeahe ckyvb byptv
E_THA T__I_ _O__I _IA__ _TTHE _E_A_ A_A__ EN_E_ __O__ E_O__ _O__O _A_IT T_E_I
aylup llvbb vstec bbupa pesbu pluvs typlv klxpo upabe tevsb ebupy kovpl fkvbv
___HE __ITT IN_O_ TTHE_ EONTH E_HIN __E_I A__E_ HE_TO _OINT OTHE_ A_IE_ _AITI
staee zmcbl upvsq eazpo zptak dpyhb ukblu prapq paapo belbk hecbl vopbu papfk
N__OO ___T_ HEIN_ O__E_ _E__A _E__T HAT_H E__E_ E__E_ TO_TA _O_T_ I_ETH E_E_A
lzeap lnerp qeavz ktvsk bvesl uplkv olupl knklp vluec yolkh vzseb pgrpn bvstk
__O_E __O_E _O_I_ A_INA TION_ HE_AI __HE_ A_A_E I_HO_ ___A_ I_NOT E__E_ TIN_A
tvayl kvozk bbupf myksx yhvbl kmehv dpnez pqeau pluec yompu papza lkypg ksopa
_I___ AI__A TTHE_ __AN_ __IT_ A_O_I _E_O_ E_O_H E_HO_ ___EH E_E__ _A_E_ AN_E_
lrpsn pafkl bemav stuvz edpaq aezse dklne bvkqe azpbu plbkb veszk lbpaf uvlby
__EN_ E__A_ TO__I N_HI_ O_E__ _O_NO _A__O TIA_O __ETH E_TAT ION_A _TE__ HI_T_
popbn
E_ET_

Now we're starting to have enough decoded letters that, with a bit of imagination, we can start making out more and more full words in the plaintext.  For example, near the end of the plaintext we have the sequence THE_TATION, with the undecrypted letter L in the middle.  Just about the only plausible English phrase that this could stand for is "the station", suggesting that L=S.  Again checking that the letter frequencies look plausible, we can try this and get:

lupfk llvbb vstbu papfk vbvst qeale zpbuv steal ezpme ohkso lvsnp lvbbv stkso
SHE_A SSITT IN_TH E_E_A ITIN_ _O_SO _ETHI N_O_S O_E_O __AN_ SIN_E SITTI N_AN_
fkvbv stfkl bupes yhbuv stbeo ewclb bupsl uplkb ksofk vbpof vbuky yupaz vtubk
_AITI N__AS THEON __THI N_TO_ O__ST THENS HESAT AN__A ITE__ ITHA_ _HE__ I_HTA
sozkv szkbb upfps necsb papob uplbk bvesz klbpa yenxv stcrb upbvn xpbeq qvnpr
N__AI N_ATT HE_EN _O_NT E_E_T HESTA TION_ ASTE_ _O__I N___T HETI_ _ETO_ _I_E_
aprka kbeah betev stuez pqeal crrpa ksokl xpouv zvqbu pqvdp buvab hbakv sfecy
_E_A_ ATO__ TO_OI N_HO_ E_O_S ___E_ AN_AS _E_HI _I_TH E_I_E THI_T _T_AI N_O__
olees mpkye stbup qvdpb uvabh bakvs uklmp psvsk sotes pukyq ksuec aktek slfpa
_SOON _EA_O N_THE _I_ET HI_T_ T_AIN HAS_E ENINA N__ON EHA__ ANHO_ _A_OA NS_E_
pobuk bmavl xeqqv nvkym cbbup apfkl krkll pstpa oaerr poeqq qeahe ckyvb byptv
E_THA T__IS _O__I _IA__ _TTHE _E_AS A_ASS EN_E_ __O__ E_O__ _O__O _A_IT T_E_I
aylup llvbb vstec bbupa pesbu pluvs typlv klxpo upabe tevsb ebupy kovpl fkvbv
__SHE SSITT IN_O_ TTHE_ EONTH ESHIN __ESI AS_E_ HE_TO _OINT OTHE_ A_IES _AITI
staee zmcbl upvsq eazpo zptak dpyhb ukblu prapq paapo belbk hecbl vopbu papfk
N__OO ___TS HEIN_ O__E_ _E__A _E__T HATSH E__E_ E__E_ TOSTA _O_TS I_ETH E_E_A
lzeap lnerp qeavz ktvsk bvesl uplkv olupl knklp vluec yolkh vzseb pgrpn bvstk
S_O_E S_O_E _O_I_ A_INA TIONS HESAI _SHES A_ASE ISHO_ __SA_ I_NOT E__E_ TIN_A
tvayl kvozk bbupf myksx yhvbl kmehv dpnez pqeau pluec yompu papza lkypg ksopa
_I__S AI__A TTHE_ __AN_ __ITS A_O_I _E_O_ E_O_H ESHO_ ___EH E_E__ SA_E_ AN_E_
lrpsn pafkl bemav stuvz edpaq aezse dklne bvkqe azpbu plbkb veszk lbpaf uvlby
S_EN_ E__AS TO__I N_HI_ O_E__ _O_NO _AS_O TIA_O __ETH ESTAT ION_A STE__ HIST_
popbn
E_ET_

Now, we can take a guess that the beginning of the plaintext, SHE_A SSITT IN_TH E_E_A ITIN_ _O_SO _ETHI N_ might read "she was sitting there waiting for something", giving us F=W, T=G, A=R, Q=F and Z=M.  Plugging those guesses in, we get:

lupfk llvbb vstbu papfk vbvst qeale zpbuv steal ezpme ohkso lvsnp lvbbv stkso
SHEWA SSITT INGTH EREWA ITING FORSO METHI NGORS OME_O __AN_ SIN_E SITTI NGAN_
fkvbv stfkl bupes yhbuv stbeo ewclb bupsl uplkb ksofk vbpof vbuky yupaz vtubk
WAITI NGWAS THEON __THI NGTO_ O__ST THENS HESAT AN_WA ITE_W ITHA_ _HERM IGHTA
sozkv szkbb upfps necsb papob uplbk bvesz klbpa yenxv stcrb upbvn xpbeq qvnpr
N_MAI NMATT HEWEN _O_NT ERE_T HESTA TIONM ASTER _O__I NG__T HETI_ _ETOF FI_E_
aprka kbeah betev stuez pqeal crrpa ksokl xpouv zvqbu pqvdp buvab hbakv sfecy
RE_AR ATOR_ TOGOI NGHOM EFORS ___ER AN_AS _E_HI MIFTH EFI_E THIRT _TRAI NWO__
olees mpkye stbup qvdpb uvabh bakvs uklmp psvsk sotes pukyq ksuec aktek slfpa
_SOON _EA_O NGTHE FI_ET HIRT_ TRAIN HAS_E ENINA N_GON EHA_F ANHO_ RAGOA NSWER
pobuk bmavl xeqqv nvkym cbbup apfkl krkll pstpa oaerr poeqq qeahe ckyvb byptv
E_THA T_RIS _OFFI _IA__ _TTHE REWAS A_ASS ENGER _RO__ E_OFF FOR_O _A_IT T_EGI
aylup llvbb vstec bbupa pesbu pluvs typlv klxpo upabe tevsb ebupy kovpl fkvbv
R_SHE SSITT INGO_ TTHER EONTH ESHIN G_ESI AS_E_ HERTO GOINT OTHE_ A_IES WAITI
staee zmcbl upvsq eazpo zptak dpyhb ukblu prapq paapo belbk hecbl vopbu papfk
NGROO M__TS HEINF ORME_ MEGRA _E__T HATSH E_REF ERRE_ TOSTA _O_TS I_ETH EREWA
lzeap lnerp qeavz ktvsk bvesl uplkv olupl knklp vluec yolkh vzseb pgrpn bvstk
SMORE S_O_E FORIM AGINA TIONS HESAI _SHES A_ASE ISHO_ __SA_ IMNOT E__E_ TINGA
tvayl kvozk bbupf myksx yhvbl kmehv dpnez pqeau pluec yompu papza lkypg ksopa
GIR_S AI_MA TTHEW __AN_ __ITS A_O_I _E_OM EFORH ESHO_ ___EH EREMR SA_E_ AN_ER
lrpsn pafkl bemav stuvz edpaq aezse dklne bvkqe azpbu plbkb veszk lbpaf uvlby
S_EN_ ERWAS TO_RI NGHIM O_ERF ROMNO _AS_O TIAFO RMETH ESTAT IONMA STERW HIST_
popbn
E_ET_

At this point, it should be pretty straightforward to fill in the missing bits of the plaintext, giving us:

lupfk llvbb vstbu papfk vbvst qeale zpbuv steal ezpme ohkso lvsnp lvbbv stkso
SHEWA SSITT INGTH EREWA ITING FORSO METHI NGORS OMEBO DYAND SINCE SITTI NGAND
fkvbv stfkl bupes yhbuv stbeo ewclb bupsl uplkb ksofk vbpof vbuky yupaz vtubk
WAITI NGWAS THEON LYTHI NGTOD OJUST THENS HESAT ANDWA ITEDW ITHAL LHERM IGHTA
sozkv szkbb upfps necsb papob uplbk bvesz klbpa yenxv stcrb upbvn xpbeq qvnpr
NDMAI NMATT HEWEN COUNT EREDT HESTA TIONM ASTER LOCKI NGUPT HETIC KETOF FICEP
aprka kbeah betev stuez pqeal crrpa ksokl xpouv zvqbu pqvdp buvab hbakv sfecy
REPAR ATORY TOGOI NGHOM EFORS UPPER ANDAS KEDHI MIFTH EFIVE THIRT YTRAI NWOUL
olees mpkye stbup qvdpb uvabh bakvs uklmp psvsk sotes pukyq ksuec aktek slfpa
DSOON BEALO NGTHE FIVET HIRTY TRAIN HASBE ENINA NDGON EHALF ANHOU RAGOA NSWER
pobuk bmavl xeqqv nvkym cbbup apfkl krkll pstpa oaerr poeqq qeahe ckyvb byptv
EDTHA TBRIS KOFFI CIALB UTTHE REWAS APASS ENGER DROPP EDOFF FORYO UALIT TLEGI
aylup llvbb vstec bbupa pesbu pluvs typlv klxpo upabe tevsb ebupy kovpl fkvbv
RLSHE SSITT INGOU TTHER EONTH ESHIN GLESI ASKED HERTO GOINT OTHEL ADIES WAITI
staee zmcbl upvsq eazpo zptak dpyhb ukblu prapq paapo belbk hecbl vopbu papfk
NGROO MBUTS HEINF ORMED MEGRA VELYT HATSH EPREF ERRED TOSTA YOUTS IDETH EREWA
lzeap lnerp qeavz ktvsk bvesl uplkv olupl knklp vluec yolkh vzseb pgrpn bvstk
SMORE SCOPE FORIM AGINA TIONS HESAI DSHES ACASE ISHOU LDSAY IMNOT EXPEC TINGA
tvayl kvozk bbupf myksx yhvbl kmehv dpnez pqeau pluec yompu papza lkypg ksopa
GIRLS AIDMA TTHEW BLANK LYITS ABOYI VECOM EFORH ESHOU LDBEH EREMR SALEX ANDER
lrpsn pafkl bemav stuvz edpaq aezse dklne bvkqe azpbu plbkb veszk lbpaf uvlby
SPENC ERWAS TOBRI NGHIM OVERF ROMNO VASCO TIAFO RMETH ESTAT IONMA STERW HISTL
popbn
EDETC

(If you're curious about the source of the plaintext, a quick Google search will reveal that it comes from chapter 2 of the book Anne of Green Gables by Lucy Maud Montgomery, published in 1908.)

Oh, and the keyword?  Well, we didn't really need it to decode the message, but since we now have (almost) the whole ciphertext alphabet, we can write it down sorted by plaintext letter to get:

ABCDEFGHIJKLMNOPQRSTUVWXYZ
kmnopqtuvwxyzser?albcdfgh?

where the two question marks stand for the letters I and J that don't occur in the ciphertext, as they correspond to the rare plaintext letters Q and Z.  Guessing that I=Q and J=Z, we can see that the keyword is "serial", and the key letter is N.  (Of course, the keyword "serjal" would also work in this particular case, but as far as I know there is no such word in English.)


What is the meaning of "transcipher" (if such term exists) recently I heard the term "transcipher" during a discussion (seems something related to double encryption using two different keys), but I was not able to find any information about such a term in the internet. Is it an actual cryptography term? if so, what does it mean?

It is a command of the german health card.
See here for the RSA version. There exists also  an ECC version for the generation 2 card. The specification is also on the www.gematik.de web site but its a bit tricky to find it.


Increased security weaknesses when truncating SHA1 Given the following preconditions:

A plaintext A (~512bit length), that is hashed by using SHA-1 and truncated to (the first) 64 bits.
I know both, the plaintext and the truncated hash, and want to perform a Second Preimage Collision Attack.
Furthermore, a part of the new plaintext B, that should produce the same (truncated) hash value, is fixed (the same as in plaintext A), the remainder can be choosen randomly.

Are there any increased weaknesses when truncating SHA1 to the first 64 bits only (besides the decreased number of bits)?

Are there any other circumstances (like controlling a whole block of 512 bits, equality of both plaintexts in all but one word, controlling the last block, etc.), that could interfere with the truncation, so that there are further weaknesses that could facilitate the cracking?

Are there any attacks against SHA-1, that aim for a Second Preimage Resistance Attack?
Most of what I found were birthday attacks (that could increase the possibilty to find a collision from $1/(2^{80})$ to $1/(2^{60})$). I understand, that a preimage attack on full SHA-1 is not feasible, but a theoretical attack could help me to make the cracking of the partial hash possible.

The required number of tries to find a collision on this hash with a probability of 50% is $2^{63}$, right? This would take around 150 years on a single GPU.

Given message $A$, you have to find message $B$, such that the first 64 bits (say, MSB) of their hashes collide:
$$
MSB_{64}(H(A)) = MSB_{64}(H(B))
$$

This problem is called Second Preimage Search for the function $MSB_{64}(H)$, or Partial Second Preimage Search for the hash function $H$ alone.

When $H$ is the full round SHA-1, there is no result, theoretical or practical, that would allow you to do it faster than by trying $2^{64}$ (on average) arbitrary strings for $B$. Clearly, your third restriction does not make the things easier, but still, you need to brute-force $2^{64}$ messages to solve the problem.


How is Homomorphic Encryption secure (over integers)? I have been reading a bit about homomorphic encryption, and have been intrigued by its properties.

If I have some cryptosystem that is homomorphic and supports addition, from my understanding, I can do this:

E(A) + E(B) = E(A+B)

...And then I can decrypt E(A+B) without knowing either A or B.

However, if A and B were something like salaries stored somewhere...

E($120k) + E($100k) = E($120k + $100k) = E($220k)

From what I understand, I may not be able to decrypt A or B, but I can calculate A or B given some math. For example:

D(E(A+B)) = $220k (since I can decrypt the result without knowing the individual encryptions)
X = E(-$220k) (since I can encrypt any values myself)
X + E(A) = E(-$220k) + E($120k) = E(-$100k) (this gives me the negative of B... but I can negate that to get B)

Am I understanding this correctly? If so, how is homomorphic encryption secure?

The use case for homomorphic encryption is that I encrypt my own data with my public key. I then ship this data to the cloud. The cloud can perform operations on those ciphertexts. But, since the cloud does not have the private key, the cloud cannot decrypt the results of the operations.

Once the operations have been performed, the cloud sends the resulting ciphertext back to me. I can decrypt that to get the answer.

So the key is allowing another untrusted party access to encrypted versions of my data that they can compute on, but can't get the results of the computations. If someone else encrypts their private data with your public key and sends it to you, you will be able to get their private data since you can decrypt.


Quantum resistance of Lamport signatures The Lamport-Diffie signature scheme is said to be quantum-resistant. Why is that? What would a quantum attempt to attack this signature scheme look like, and how does it fail?

The security of the LD scheme can be reduced to the one-wayness (aka preimage resistance) of the used hash function. The reduction is quite easy:

Assume you want to invert the one-way function $f$ for image $y=f(x)$, given a forger for LD-OTS. Then you generate a valid LD key pair using $f$, sample a random position i in the key pair and a bit b and replace $pk_{i,b}$ by $y$ and run the adversary on the modified $pk$. If the adversaries query has bit $b$ in position $i$ you abort and restart the proceedure. Otherwise, you can answer the query. Now you hope that the adversaries forgery hash bit $b$ at position $i$. If this is the case, the $i$th element of the signature is a preimage of $y$ under $f$.

The reduction works with only a slight loss in success probability, i.e. you loose something as you abort in some cases. However, this loss can be bounded by $1/2m$ for $m$ bit messages. You can find the details in the post-quantum cryptography book by Bernstein et al..

Now, the argument for the LD scheme to be quantum secure follows from the fact that the best known generic attack against the one-wayness of a hash function using a quantum computer is Grovers algorithm that has exponential runtime. Moreover, there exist several hash functions that are conjectured to be one-way, even in the presence of a quantum computer.

Something else was recently shown by Boneh and Zhandry in their Crypto2013 paper. There they show that the scheme remains secure even if the adversary is given the ability to make super position queries. This models the case that the scheme itself is run on a quantum computer, not only the adversary.


Backward Expansion of SHA1 Given a SHA1 hash, is it now possible to "practically" find the source material that was passed through SHA1 now that the Shattered paper has produced the first "practical" collision?

As a follow on question - if I have the SHA1 Hash and the Source document, can I find/produce the 2nd document using the Shattered algorithm, if I know in advance that it exists?

Can you find the source material given a hash?

No, doing so would break the preimage assumption which is so far unbroken for sha1. (Assuming the message has sufficient entropy as to make brute forcing impractical)

  Can I find a 2nd document now that Shattered exists?

Yes / no. Yes, you can find many documents based on the shattered examples; but no you cannot create a new document without spending the same computations that the researchers did.

Take the two shattered examples, you can control all bytes after their distinct prefix blocks collide. All bytes after must be equal. So you're not introducing any new collisions, just extending the known collisions.

What is broken then?

Collision resistance.

You can (given lots of computing time) produce collisions just as they did in the paper, but this is still expensive. If a protocol assumes collision resistance and you pass it the two shattered files, it'll break. Likely assuming the second file is redundant, or incorrectly equivalent to the first.


What methods allow us to determine the language used in a monoalphabetic substitution cipher? Working on a cipher (which I assume to be a mono-alphabetic substitution cipher due to the letter frequency) I struggle with the fact that I don't know which language the plain text is written in. Looking at the letter frequency only, gives some hints, at least to exclude some languages, but far from pointing out one. I have also studied the index of coincidence, but several languages are quite close to each other and I am uncertain how much I can trust this.

Both these ways indicates that my particular cipher isn't written in English. It's also a patristocrat (no separations between words), which makes word-matching harder.

My question is: what methods are there, and which one tends to produce optimal results?

I can't tell you which method is the best, but I can point out some places to look. The longer the message the easier it is easier to identify. How long is the message?

n-gram frequency: Look at the likelihood that groups of n-letters appear next to each other (often called n-grams). For example is does the n-gram AAA appear frequently (not many languages have words that contain the same letter repeated three times). N-grams are often used for language recognition. Bi-gram and Tri-gram (2-gram and 3-gram) frequency tables can be found here. Any long subsections of the ciphertext repeat?

Writing analysis Is this a hand written note? Often different languages that share the same character sets have different ways of writing characters (Germans/Mathematicians tend to put a line in the middle of their Z's, members of the US military tend to cross-slash their zero's).

Size of Alphabet: Are there 26 different letters in the ciphertext? Are the characters the standard latin alphabet. Any whitespace? Any punctuation? Numbers (many WW1 ciphers were broken by attacking ciphered numbers)? Capitals/Lowercase?

Plaintext: Do you have any clues about what the plaintext might be? Even if you don't know the language if you know that the ciphertext might be about battleships you can try translating water/gas/ships/boats/knots/depth into the candidate languages and see if you find any matches. You can try a similar approach with common words (equivalents of 'to be', 'to', 'it', 'hello' etc).


RSA padding: what is it and how does that work? If I am not mistaken, plaintext RSA is not secure. So, I have read that padding and hashing is needed to make the RSA algorithm secure. However, I am confused on what does padding or armoring mean in this context. What does RSA-padding mean, how does it work?

For instance here I have read about this, but I do not really understand the meaning behind the notion of padding. Can anyone enlighten mean about this?

Padding in cryptography means adding a (mostly secret) random set of data to the cryptographic functionality.

In practice and when done correctly, cryptographic padding adds a cryptographic problem and thereby reduces attack vectors because (theoretically) it reduces the success in “guessing” intermediate or final states of the encryption and/or decryption functionality.

Two notes:

The reason why I wrote “when done correctly” is that one of the disadvantages of cryptographic padding is that it could make the plain text of the message susceptible to padding oracle attacks.
Note that I wrote "(theoretically)" as some algorithms were weakened and even broken due to incorrect or missing implementations of cryptographic padding, but there are also ample cryptographic algorithms that can do without cryptographic padding as they use cryptographic approaches that differ from RSA's.

If you want to dive deeper into RSA-related cryptographic padding, take a look at this question and especially it's accepted answer which dives into the practice a bit more.

EDIT

Note that there's also a nice and more broad description of cryptographic padding available at
http://en.wikipedia.org/wiki/Padding_%28cryptography%29


Why does NaCl's crypto_secretbox for xsalsa20-poly1305 require the first 32 bytes to be zero? The NaCl web site says this is a requirement of the API, but its seems more than just an API issue. It means the first 32 bytes of the first salsa20 block are effectively ignored. I didn't see anything in the documentation that explains the reason for this.

Does ignoring the first 32 bytes of the first salsa20 block improve security in some way?

The first 32 bytes of XSalsa20 output are used as key for the one-time-mac Poly1305. Poly 1305 needs a new 32 byte key for each message, using part of the key-stream is a natural way to obtain those.

Requiring those empty bytes makes implementing the API easier. The implementer only needs to call XSalsa20 on the zero padded input buffer once, receiving both the Poly1305 key and encrypting the message.

Without a padded input it's necessary to split the call to XSalsa20 into several calls, one to HSalsa, two to Salsa20 and a bit of copying. This is a bit annoying and incurs a minor performance hit.

IMO requiring zero padding is bad API design. This is an implementation detail that shouldn't be exposed to the user. APIs should be designed with the consumer in mind, not the implementer.


A bijective hash function Suppose:

$H: \{0,1\}^{n} \rightarrow \{0,1\}^{n}$.
$H$ is bijective.
It is difficult to derive $x$ from $H(x)$.

Is this type of function possible? What would the strength of it be?

I realize that RSA and discrete logarithms can fulfill this, but I was thinking of using standard operators instead of those two. Other primitives could be acceptable.

On the practical side of things, if your hypothetical function is hard to invert, and assuming collisions are hard to find, why does it matter that it be bijective? For sufficiently large $n$ you can't construct a counterexample anyway, so a hash function may as well be bijective as far as anyone cares.

Otherwise, not exactly what you're asking for but you could try for a white-box block cipher implementation, basically just pick a block cipher, pick a random key, and embed the key in your implementation in such a way as to not be easily retrievable from the code. There are some papers describing techniques to do so, it might be worth taking a look.


Does displaying HMAC hashes of user inputs compromise the HMAC validation? Here is the scenario:

"SECRET" is a secret key that is kept private and only used in this one application.
The application allows users to enter in any "VALUE" (within various open-ended limits such as numeric > 50, max length 20, etc... depending on the field)
The application creates an HMAC-SHA2-256 "HASH" from VALUE and its field name using SECRET as the key
HASH is displayed to the user

"CONTROL" (comparison) scenario:

Only a certain number of field VALUEs and their corresponding HASHes are shown to users
Users cannot input additional VALUEs to see the corresponding HASHes

Other information:

The HASHes are used to prevent the VALUEs from being changed while being sent to a third party application.
If a user tries a HASH with a corresponding field name and VALUE, either it works or an error message comes up.
There are no limits or precautions against automated testing other than network speed.

Real-life application (not necessary for the question):

The hashes are used as an easy (==low cost) alternative to IPN validation for products sent to FoxyCart, a Javascript-powered secure checkout.
The hashes prevent a user from spoofing exact values but cannot handle complex conditions such as minimum and maximum values of a user-chosen option. For such situations, FoxyCart provides a special hash value that disables validation of that field.
The easy solution would be to validate the user input on the server and hash it before forwarding it to FoxyCart.

Questions:

Does allowing users to test VALUEs increase the likelihood that SECRET will be broken or illegal hashed values generated, relative to the CONTROL scenario?
By how much?
How is this calculated or proved?

Does allowing users to test VALUEs increase the likelihood that SECRET will be broken or illegal hashed values generated, relative to the CONTROL scenario?

By definition a cryptographic Message Authentication Code such as HMAC is secure only if resists existential forgery under chosen-plaintext attacks. i.e. if allowing users to test VALUEs increases the likelihood of discovering the SECRET or generating illegal hashes, then HMAC would not be a secure MAC (and the current state of our knowledge is that it is strong when used with a half decent hash function).

In your particular usage though, unless the HASH value is tied to a particular cart/session it might be possible to replay HASH values obtained from previous interactions.

  By how much?
  How is this calculated or proved?

The 2006 security proof for HMAC by Mihir Bellare provides a proof and tightness bounds on that proof, but for your purposes you could probably treat the difference as negligible.


Implementing commitments and challenges for a distributed ElGamal encryption scheme I am trying to implement a distributed encryption system by having as a main source of information this book (Introduction to Cryptography by Delfs and Knebl) and this Internet article (More Mix than Net by Wood).

I generate the following variables:

$p$: prime,
$g$: generator,
$x$: random within $[1, p-1]$,
$h$: $g^x \bmod  p$

I can then use these variables to successfully encrypt, re-encrypt, and decrypt a message.

I am now trying to make the system use multiple authorities by following subsection 4.5.5 on Delfs's book that states:

According to this subsection $x$ is computed as a random number between $1$ and $q-1$, yet I am using the range $1$ and $p-1$ as shown in the article. Another difference is that in the book there is no mention of modulo $p$ when computing $h$.

Note that I have also implemented the ElGamal system as described in the book, but I would like to go with the implementation from the article since it makes more sense to me and I would like to not use external libraries).

My question is, what is the commitment I should generate and how can I later verify it?

I can't access the book, so not sure exactly what it says, but the article you referenced also seems to be generating values in a group with order q: my intuition is that they are just using separate variables and group is of the same size in both texts just using $q$ and $p$ as variables respectively. As long as you are sampling $x_i$ uniformly from the full modular group you should be okay.

A for using modulo p, the security of El Gamal relies on the hardness of discrete log within the group $G$ with order $p$, so all operations are bounded via $\bmod p$.

Hope this is helpful, did I understand your question correctly?


Are these two methods of differential cryptanalysis different? I'm trying to understand how differential analysis works. I'm reading this and this tutorials, but it looks like they do different things. In the first paper author tells us to bruteforce last round using every possible keybits for active sboxes and traces differential up to r-1 round. In second work differential goes to the end and bruteforce goes only for a number of keys and author finds k0 and k1 at the same time. Which method is a basic to find round keys?

The approach in the Heys’ tutorial where the author uses the approach

bruteforce last round using every possible keybit [at the output of] active sboxes and trace differentials up to [the output of] $r-1$ rounds

is more fundamental because it is more general.
One needs to meet in the middle at the output of some round and check which value for the guessed keybits results in the highest probability differential for the set of plaintext/ciphertext pairs with a fixed input difference.
It is most convenient and natural to use meet in the middle at the input to the last round, and let the guessed key bits be the bits from the last round.
In fact the other (amazing king) reference is essentially using the same approach (whether the author of the webpage realizes it) since that is a one round cipher with $r=1,$ so $r-1=0,$ and the $r-1$ differential is the input (plaintext) difference.


gpg --gen-random quality level: is higher "better"? The GNU Privacy Guard manual pages have this to say about using the gpg --gen-random 0|1|2 count command:

  Emit count random bytes of the given quality level 0, 1 or 2. If count is not given or zero, an endless sequence of random bytes will be emitted. If used with --armor the output will be base64 encoded. PLEASE, don’t use this command unless you know what you are doing; it may remove precious entropy from the system!

I am wondering what the "quality level" means.  Is 2 "better" (i.e. more random) than 0? How much "more random" is one level over another?

BACKGROUND:
I came across this command in an article in Linux Journal that illustrated using gpg's --gen-random command to generate a random password. I want to have as random of a password as possible, so I want to know what "quality level" is best for this purpose.

This is a really hard question to answer. The definitive answer can only be found in the source code of gpg. However I can still answer your question using a mail I found (from 2013, details may have changed).

  Is 2 "better" (i.e. more random) than 0?

Yes, 2 is "better" than 0 and 1.
As per the linked mail the quality level determines the number of bytes being read from /dev/urandom and /dev/random for answering the query.

As it appears in the mail 0 and 1 are actually the same (this may have changed by now) and gpg will just answer your query with the requested amount of fresh bytes from /dev/urandom.

2 however is different. It uses /dev/random, meaning you have higher guarantees concerning the quality and entropy of the output (as you may have to wait some time, if this trade-off is actually worth it is another question). And more importantly it requests significantly more bytes from /dev/random than you query, namely nearly 19x as many and post-processes them somehow. So the entropy of the result is high even if /dev/random doesn't provide you with high-quality random bytes.


Why is data signed with SHA256-RSA-PKCS and digest signed with RSA-PKCS different? I need to sign some data using RSA. I have the digest that I can sign but the signature turns out different from the signing source data.
There is data in data.bin and its sha256 digest in digest.bin
$ xxd -p -c32 digest.bin
19d512fc649e1668eb84741284ad95ec03f3225719a83e40389dbade4eabe5ed
$ sha256sum data.bin
19d512fc649e1668eb84741284ad95ec03f3225719a83e40389dbade4eabe5ed  data.bin

Why is the signature different when signing data using SHA256-RSA-PKCS and when signing a digest with RSA-PKCS? In both cases, the same sha256 digest should be created and then signed.
$ pkcs11-tool --module /usr/lib/libIDPrimePKCS11.so --pin=$PIN --slot 0x11 --sign --input-file data.bin --mechanism SHA256-RSA-PKCS |base64 -w0
Using signature algorithm SHA256-RSA-PKCS
N4XkgBhyu5fAFTSraEj4RlKeyKy2fyUD4kv9QgBVmRl/u0jDYuPdQ/Gr0Hf2wRD8B3AWe98Y3WWtv5/c2NILosG5VzqrQEKVFKLCLkdpV7cQoSDkzAv0YjRRWKMJPr1Y9Vwi15yua17W8JqnqAc0D/Mda68qgugxgCzfwC+BkWnjsN3EaxixIzwZ9aMbfuBbA8R/+uRZMdPHc6w/aFIhSM9sS3jyeb2ZYy7semPlFMAx1BQx4C2uGlEW5GI7BCq1sTCchuB0baR4WX+yoHp+bRsJHWjEcXmgFloxfb6k0n3rvZOZboO0h9UPbxlxFxHou1v6UqymNgnt+oC1KkclRQ==

$ pkcs11-tool --module /usr/lib/libIDPrimePKCS11.so --pin=$PIN --slot 0x11 --sign --input-file digest.bin --mechanism RSA-PKCS |base64 -w0
Using signature algorithm RSA-PKCS
RseZYWjkyNRcU1lI1KR+I+0C1jC+FVp2kTAhyOUsE2x6UGf+UMSf3kqD4KGBb+eIryXDFTzNsdo8XroUtWvYQvHgPLPaRQ8xfPtTOZS/crQY168S2lk4buAeDZWat/xiGeXgU4rL7hdbjojdkfbeGWHfIERcese6wv521t9x9w5K3XGz50Ec9Y/C4cPPo4xuQMSQlCrx1iIlfeGbkElxGIdIkZvt2nTrhl/ico5YCbTJfuDqZaaaJxPkXcfgAcvFVU/kILi7U3XQCvz7zohZoRj4vkeTutanW6I7qGyWvIcxXGJx29MInF3pohT0+KUzegN4A1GfkW5hfk5HyCP2Gw==

public key is
-----BEGIN PUBLIC KEY-----
MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEAwzz8XZ5iDjWlLZOfXgzh
VsyFcx85QEhgrcJJXkFV2k+vmVUA1R4oZPuvE+cF13ymh05+GLM0OHHzrohSrbv9
3AUmkWLPY04jF0NXSEAd180ImJ84Y2lSaqo4op+l3cPjIWeeBN0DPX78GdLGJnIr
Fq51TwKcdtjgQMvfWDuxZbjo2C20QQIIzp0cWGTsWOBFamjOJGhfRcQ/TT4MDA2h
//813N2HqXnlAtEgvlLH1Jv+VNROd/WIN+CMo0NLDQGS0AhVZPctatNqH5mXwklZ
goyv62WY284EIZLC1nTgMWxdQQIR6yRyJmQwp7zLs/Fk9rYZDHEOTuILEHd/7dPB
7wIDAQAB
-----END PUBLIC KEY-----

TLDR: it's the DigestInfo
The hash-and-RSA-PKCS schemes defined in Current Mechanisms 2.1.14 do the full scheme of RSASSA-PKCS1-v1_5 which is now defined in RFC8017 primarily in 9.2 as a combination of EMSA-PCKS1-v1_5 'encoding' (usually called padding) plus the RSASP1 and RSAVP1 primitives. (In prior versions the document was organized differently, but the substance was the same.) Concretely this consists of:
#1 hash the data
#2 encode the hash value, plus the hash algorithm, in an ASN.1 structure DigestInfo in DER; since each hash algorithm has constant output size, this amounts to prepending a fixed prefix depending only on the algorithm, as given in note 1
#3-5 prepend padding of the form 00 01 FF...(at least 8) 00
(8.2.1#2) treating the result as a number m, apply RSASP1 which does m ^ d mod n (or for verify 8.2.2#2 apply RSAVP1 which does s ^ e mod n; this is stated as before the three padding steps above but actually can just as well be after)
OTOTH RSA-PKCS defined in 2.1.6 for Sign/Verify does ONLY the latter two of those steps, not the first two. As the text says: "This mechanism corresponds only to the part of PKCS #1 v1.5 that involves RSA; it does not compute a message digest or a DigestInfo encoding as specified ... in PKCS #1 v1.5 ." You externally hashed the data which is the first step, but did not do the DigestInfo which is the second (required) step, and thus got the wrong result.
Except for being PKCS11 (hardware) rather than software, this is crossdupe at least:
https://stackoverflow.com/questions/521101/using-sha1-and-rsa-with-java-security-signature-vs-messagedigest-and-cipher
https://stackoverflow.com/questions/9951559/difference-between-openssl-rsautl-and-dgst
https://stackoverflow.com/questions/38767660/multiple-openssl-rsa-signing-methods-produce-different-results
https://stackoverflow.com/questions/63582544/how-does-jwt-implement-rsa256-signature-verification-in-nodejs
https://stackoverflow.com/questions/62955968/how-can-realize-openssl-pkeyutl-sign-by-java
https://stackoverflow.com/questions/48013643/get-the-sha1-hashed-value-from-xml-signature-value
https://stackoverflow.com/questions/43490188/separate-digest-signing-using-java-security-provider
https://stackoverflow.com/questions/57929493/openssl-digitally-sign-digest-only
https://stackoverflow.com/questions/9380856/openssl-signature-difference-when-using-c-routines-and-openssl
https://stackoverflow.com/questions/13419201/why-are-the-rsa-sha256-signatures-i-generate-with-openssl-and-java-different
https://stackoverflow.com/questions/15092298/signing-20-byte-message-with-256-bit-rsa-key-working-with-openssl-exe-but-not-in
https://superuser.com/questions/943972/what-is-the-difference-between-openssl-pkeyutl-sign-and-openssl-rsautl-sign


Why is the nonlinearity of this Boolean function evaluating to $\frac12$? I am using the method presented in this paper to find the nonlinearity of the function
$$ f: \mathbb{F}^1_2 \to   \mathbb{F}^1_2 \\ f(x) = x$$
The truth table is $f = [0 \space \space 1]$. Now, I read from the paper by Terry Ritter that

Nonlinearity is the number of bits which must change in the truth
table of a Boolean function to reach the closest affine function.

This means the nonlinearity value should be a whole number.
The algorithm to calculate nonlinearity is to first use the Fast Walsh Transform to find the Walsh spectrum, then use the formula
$$Nl(f_k) = 2^{k-1} - \dfrac12 \cdot\max_{a\in\mathbb{F_2^{2^k}}} |W_f(a)| $$
where the Walsh spectrum is calculated by multiplying the truth table of the function by the corresponding Hadamard matrix.
So, since $k = 1$, we use the Hadamard matrix of size $2^1$ giving the following Walsh spectrum:
$$ \begin{bmatrix}0 & 1\end{bmatrix} \begin{bmatrix}1 & 1\\1 & -1\end{bmatrix} = \begin{bmatrix}1 & -1\end{bmatrix} \implies \max_{a\in\mathbb{F_2^{2^k}}} |W_f(a)| = |-1| = 1  $$
Therefore
$$ Nl(f_{k=1}) = 2^{0} - \dfrac12 \cdot 1 = \dfrac12$$
What am I missing?

In case the links are dead, the linked papers are:

Calculating Nonlinearity of Boolean Functions with Walsh-Hadamard Transform by Pedro Miguel Sosa
Measuring Boolean Function Nonlinearity by Walsh Transform by Terry Ritter

In this formulation you need to convert your function's output range to $\{-1,+1\}$ via $$f`(x)=(-1)^{f(x)}$$ and apply the Walsh Hadamard to the new function $f`(x)$. Using the zero one formulation means you are off by a constant depending on the number of variables since
$$
(-1)^u=1-2u
$$
for $u\in \{0,1\}.$
See my answer below on Boolean functions and crypto, it may be useful given your recent questions.
How are boolean functions used in cryptography?


Why is this a fix to Bleichenbacher's attack? Looking at this excellent explaination of the attack, I have one additional question:

  It says that: ""To prevent this attack, SSL servers do not inform the client about padding woes. If decryption fails because of a bad padding, then the server continues with a random pre-master secret (the true failure will then occur when processing the Finished message).""

Why does this prevent the attack?
Why doesn't the attacker just infer that the connection failed because of the bad padding? Why else could the connection fail?

Why does this prevent the attack? Why doesn't the attacker just infer that the connection failed because of the bad padding? Why else could the connection fail?

Well, the connection may fail because the host decrypted a valid pre-master secret, and it wasn't the pre-master secret that we expect.

That is, when the attacker injects his encrypted message, one of two things can happen:

The server attempts to decrypt the message, and finds that the padding is invalid
The server decrypts the message, and finds a value there.

The information that the attacker needs to know is whether (1) or (2) happened; if he can determine that, then he knows whether the padding looked correct or not.

Now, with the attack, if (2) happens, then the attacker has no idea what the value would be.  Hence, if we react to (1) in a way that mimics the behavior in (2), we prevent the attacker from learning that.


Secure symmetric encryption algorithm for any-size base62 data I am searching for a secure algorithm to encrypt base62 (or any other base) data for ids in urls.

It should feature:

No blocksize etc, limiting the length of the message to a factor of n
If you have the decryted and the encrypted message you should not be able to guess the key
An avalanche effect
Any size of charset, not only 256 like in AES, DES etc.
High performance on modern CPUs

This is not required:

Streaming, it is only for small data

Is this possible?

If you define your encryption to be $C=E_{62}(E_k(D_{62}(P)))$ and your decryption to be $P=E_{62}(D_k(D_{62}({C})))$ where $P$ is your encoded URL then you've brought back your problem to finding an encryption function for $l$ bits, where $l$ is the size of $D_{62}(P)$. After that you can "just" look for a Format Preserving Encryption primitive for those $l$ bits. If the encrypted URL is allowed to be larger than the unencrypted URL then you could use CTR mode with a nonce of 8 random bytes.


RSA: Given $n$ and $\varphi(n)$, find $e$ such that $e=d$ Say we have chosen $n=pq$, with $p=89,q=97 \implies n=8633$ and $\varphi(n)=88\times96=8448$. Also, if we want the encoding ($e$) and decoding ($d$) exponents to be equal, we need $$(e,8448)=1 \: \: \text{(relatively prime),}$$ $$ed \equiv 1 \pmod{8448} \implies e^2 \equiv 1 \pmod{8448}.$$

How do I go about solving something like this? My first inclination is that $(e,8448)=1$ means that $e$ must be prime, but I'm really not sure.

If you know the factorization of $\phi(n)$, this can be done like this:

The factorization gives you various prime powers as factors of $\phi(n)$, let's call those $p_i^{e_i}$. Then:

For each $p_i^{e_i}$ with $p_i>2$, the roots of the polynomial $x^2 - 1 = 0 \mod p_i^{e_i}$ are $1$ and $p_i^{e_i}-1$ and there are no other roots. This can be proven by using Hensel lifting for the two roots of the polynomial $x^2-1 \mod p_i$.
For powers of $2$, Hensel lifting the polynomial $x^2-1$ also gives you solutions, but it's more complicated if you want to find all of them, because $f'(r)=2r$ will be $0$ for some root $r$. If you want to find just one, then just use $x=1 \mod 2^x$, where $x$ is the power of $2$ in the factorization of $\phi(n)$. Edit: As an example, every odd number is a square root of $1$  modulo $8$, and modulo $16$ the square roots of $1$ are $\{1,7,9,15\}$.
For each prime power you have a set of two roots $r_1$ and $r_2$ (in a formal prove, you should have indices for the prime powers as well). Choose for each prime power either $x=r_1 \mod p_i^{e_i}$ or $x=r_2 \mod p_i^{e_i}$. If you don't want the trivial solutions $1$ and $-1$, make sure to avoid the 'all $1$' and 'all $p_i^{e_i}-1$' roots.
Use Chinese remainder theorem to assemble the solution $x \mod \phi(n)$

Edit: In the question you only wanted square roots of $1$, which is either $1$ or $-1$ mod any prime $p$. More generally, if you want to find square roots of arbitrary elements, there are also algorithms for that, e.g. Tonelli-Shanks, which work for any prime $p$. Hensel lifting then gives you the roots in the prime powers (but you need to adapt the polynomial), and then assemble the solution via CRT.

Edit:
Of course the choice $e=d$ makes the RSA cryptosystem with public key $(N,e)$ completely unsafe - the value of $e$ is public and you have to assume by Kerckhoff's principle that the attacker knows your system, in this case that you use such a defining equation.


Was the Enigma's double stepping mechanism intentional? It's sometimes refered to as the double stepping anomaly, so was it just a design flaw or was it put in place deliberately?

I suspect it was a semi-deliberate feature.  That is, while it probably wasn't a design goal in and of itself, it neatly solved a mechanical issue that would otherwise have required a more complicated and failure-prone solution.

What was the issue?  Simply, it was making the third wheel only advance one step at a time, rather than 26 steps in a row.  That's what would happen if the Enigma's notch, pawl and ratchet mechanism was modified to eliminate double stepping without making any other changes to it.

To see why this would happen, you need to note a couple of things about the way the Enigma stepping mechanism works:

Each wheel has 26 different positions it can be in, corresponding to 26 different shifts of the cipher alphabet.  Every time a key is pressed, a pawl tries to push each wheel one position forward.
Each wheel has a flange (an "index ring") with a notch at one (or, in some of the later wheels, several) of these 26 positions.  When the wheel is not in the notched position, the index ring holds up the next wheel's pawl and prevents it from rotating the wheel.

What this means is that:

The first wheel rotates one step on every keypress (since there's no other wheel before it to disengage its pawl).
The second wheel (normally) rotates on every 26th keypress, whenever the first wheel is in the notched position.
The third wheel only rotates when the second wheel is in the notched position — and if the second wheel would stay in the notched position when that happened, then it would keep rotating 26 times in a row (i.e. a full turn) until the second wheel would move out of the notched position again!

If the Enigma worked like that, its wheel positions would repeat with a period of only 26 × 26 = 676 keypresses, far less than intended and potentially less than the length of a single longish message.  But by letting the third wheel's pawl also engage the second wheel via the index ring and push it immediately out of the notched position as soon as the third wheel has rotated once — i.e. "double stepping" it — the period is extended to 26 × 25 × 26 = 16900 keypresses, i.e. to over 96% of the theoretical maximum of 263 = 17576 keypresses.

Also, the mechanical effect behind the double stepping, i.e. the pawl also pushing the notch it has dropped into, is something that kind of happens naturally in a mechanism like this.  While it probably could have been avoided by suitably adjusting the shape of the pawls and the notches, in this case it would've been counterproductive to do so.

The alternative solution, of course, would have been to redesign the mechanism to only rotate the third wheel when the second wheel moves into (or out of) the "notched" position.  That would certainly have been possible, even with early 1900s tech: a mechanical odometer, like you'd find in any old car, works exactly like that.

But the pin and gear mechanism used in odometers has more moving (and potentially breakable) parts than the Enigma's simple pawl and ratchet, and would probably have made swapping the wheels more complicated and error prone.  And, perhaps more importantly, odometers are often subject to "gear lash", especially if the mechanism is worn down, causing the later wheels to fail to rotate a full step when engaged.  While such misalignment is harmless in an odometer, and tends to correct itself on the next step, it could be a serious problem for something like the Enigma that relies on the wheels making a precise electrical contact with each other.

So I suspect the designers of the Enigma chose to go with the simpler pawl and ratchet mechanism, and accept an about 4% shorter period in exchange for mechanical simplicity and robustness.


Correlation Immunity of AES SBox How do I calculate the correlation immunity of the standard AES Sbox. All material ive read gives out calculation of correlation immunity of boolean functions with single bit outputs. How can it be translated to the 8bit AES Sbox.

Not unexpectedly, the correlation immunity of a vectorial boolean function $$S:\mathbb{F}_2^n\rightarrow \mathbb{F}_2^m,$$
is defined as
$$
CI(S)=\min \left\{ CI(a^{\top} \cdot S(x)): a \in \mathbb{F}_2^m, a\neq 0_m\right\},
$$
where $0_m$ is the all zero vector of length $m.$ Thus, it is the minimum correlation immunity of all the possible nonzero XOR sums of the output bits of $S$. In the absence of further knowledge about the Sbox, you need to compute a boolean correlation immunity $2^{m}-1,$ times and take the minimum.

In the Rijndael specification, as well as in the book \textit{The Design of Rijndael}, there is a nice chapter entitled Propagation and Correlation, where this is explored from an algebraic point of view. This helps in analysing compositions of functions, when one looks at multiple rounds or cascaded functions.


HTTPS and plaintext authentication I have client connecting a server over HTTPS to send and retrieve data.

The client always connects through HTTPS
The certificate is known to the client beforehand (hard coded into the software)
The password is auto-generated, so not chosen by the client

For authentication, is there any reason I should do anything more complicated than sending username + password in plaintext over the HTTPS connection for every request?

The data is encrypted by the HTTPS layer, so I am not vulnerable, right?

Given your ideal setup, I don't think you need anything else than plaintext authentication.

The only thing could be if the server at the end of the TLS link is not the one managing the authentication (in which case you do not necessarily want to reveal to it your password).


Interlock Protocol for Preventing Man-in-the-Middle (MitM) Attack Trying to turn bookish knowledge to practical:

Alice sends half of the encrypted data to eve, eve eavesdrop and tries to decrypt the data and fails as eve has only half of the encrypted block. So, Eve creates a new message and sends the data to Bob

  why do most documents say about altering the message content by the
  attacker?
  can't the hacker just keep a copy of encrypted block and send the
  encrypted original data to bob?
  Why does a MitM presence interrupt the network? for example, Wireshark captures the packets but still, the actual recipient receives the packet
  Could an interlock system be susceptible to passive attack?
  Can Eve send the original data without altering the message content, and keep a copy of it to integrate it with the remaining message blocks

Let begin with some definitions;

Passive attack: When the attacker only observes and not interacts with any of the parties it is called the Passive Attack. Detection of a passive attack is difficult to detect.

Active Attack: In Active attack, the attacker modifies the system on behalf of him. He can change, replay, or even delete the values or try to impersonate one of the users. There is no bound for the active attacker. Remember the quote;

"Attacks always get better; they never get worse."

  why do most documents say about altering the message content by the attacker?

That really depends on the aim of the attacker. When the attacker is able to change the message and the target is accepting the messages it is perfect. The target is a puppet of the attacker. More sophisticated attacks may require more than a message change as in The 9 lives of Bleichenbacher's CAT, it puts another scratch again. Also, remember that even in Cryptoanalysis the first aim is accessing the message not the key. The key is sufficient but not necessary.

  Can't the hacker just keep a copy of encrypted block and send the encrypted original data to Bob?

If it suits he can, but he is no longer a passive attacker, now he is an active attacker, he modified the protocol. For full answer see in 5.

  Why does a MITM presence interrupt the network? For example, Wireshark captures the packets but still, the actual recipient receives the packet.

The MitM attack requires an active attacker. You use the WhireShark as a passive attacker. This is similar to wiretapping. Tapping is even possible in Fiber Channels.

  could an interlock system be susceptible to passive attack?

There is no known passive attack for the Interlock protocol. Of course, there is always a passive attack, that is; breaking the Diffie-Hellman problem or the Discrete Logarithm Problem.

  Can Eve send the original data without altering the message content, and keep a copy of it to integrate it with the remaining message blocks

Let remember The Interlock Protocol which is designed to expose the MitM attack. Once the key exchange is finished the two sides execute;

Alice encrypts a message $m$  with her key and sends only half of the message.
Similarly, Bob encrypts a message $m$  with his key and sends only half of the message.
Then, Alice sends the other half of her message and finally,
Bob also sends the other half of his message.

Alice and Bob can combine and see the message.

Replaying is not possible as noted in the The Interlock Protocol article. The MitM attacker must decrypt the incoming data and then encrypt with the key between his and Bob. Since he cannot decrypt, he must send something else. But, he cannot send the same half text since when Bob decrypts it with the "wrong" key and Bob will get a garbage message.

Since he is exposed, the parties must establish a new key exchange in a secure way.


Crypto system design : How to design Encryption for Zero width characters Zero width character's can be used to hide text in plain sight.I am building a system where user's can provide their secret message , cover message and a password (key) which I would encrypt and give an output back with only the cover message which has encrypted secret message embedded as zero width characters invisible.When the receiver provides the key with the message, the system would decrypt and translate the zwc's back to the original secret message.

The cost of zwc's is that every two bits can contain one zwc as there are only 4zwc's available in unicode.So to represent a character 'b',it takes 4zwc's (ZWJ,ZW-NJ,ZWS,ZW-No break space).

I have been using AES with ebc mode and I encrypt the secret message with the key given by the user,but due to padding even if the user's secret message is 'hi' its padded as 16bytes when encryption due to aes block size.This means to convey 'hi', I needed 16bytes and due to zwc inclusion its 16*4 =64chars.So I researched more to find cipher text stealing where len(p)=len(cipher text) eliminating padding which is exactly what I needed.But during this process I came to know that EBC mode is insecure and CBC should be used (pretty late realization).CBC requires an IV which takes one byte again imposing more restrictions on my zwc situation.If I don't use a fixed IV, every message is suddenly two bytes 128 characters with zwc.

According to my research,fixed IV's can be used if you key changes in my case user's give the keys to encrypt so technically key changes but as its a password two messages from the same user is encrypted with the same key cause same password.Is it safe to use a fixed IV In my situation.

And I dont understand according to wiki,len(p)=len(ct) for cipher text stealing but if a fixed iv is not used len(p) is never equal to the length of the cipher text?

Can I use cbc with fixedIV and cipher text stealing for my situation?

Is this the right way to design this ? Cause this is my first crypto project

First of all, the use of zero-width characters is what we call obfuscation and indeed stenography. The encryption part that is described seems separate from it.

Generally we don't encrypt each element separate, we encrypt the plaintext and then try to hide the plaintext. Encryption generally needs something to make the key / IV unique otherwise you would get the same ciphertext for identical messages. In your situation it is only safe to use a fixed IV if a unique salt is used for each key that you derive from the password using a password based key derivation function or PBKDF. Of course, instead of having to store an IV you'd now have to store a salt.

CTR mode only requires a nonce rather than an unpredicatable IV. The nonce is a unique value of any size. Because of that the overhead of using the IV is much smaller. Alternatively, if you're stuck to CBC + CTS, you can use a nonce as IV for CBC by encrypting that initial IV with AES to derive the actual IV. IN both cases you might need to right pad the (initial) nonce with zero bytes before you can use it.

I don't see anything about a PBKDF in your description so your design probably still needs a lot of work. However, you are seeing the problems and you ask the right questions, and at this stage that might be more important.


Best non-digital cipher? Is there a cipher that was considered the undisputed best before the computer age?  (This is not supposed to be a discussion; it's either a yes or no.)

Please give a brief description why it is yes or no.

No, nothing is ever undisputed.

There is a cipher that provides perfect security (OTP) but that doesn't mean it is very practical if just for key distribution. So saying it's "the best" can be and should be disputed.

However, the answer the quiz master is looking for is probably the Vigenère cipher. I presume however that there must have been at least one person that had a doubt about the strength of the cipher.


Where x509 signature validation is concerned, what does the error "x509 certificate chain incomplete of leaf TP not found" mean? I'm validating the x509 signature of an XML document and I encounter the following error: "x509 certificate chain incomplete of leaf TP not found"

Any thoughts on what the impact is for a TLS connection?

No TLS impact.

Any thoughts on what the impact is for a TLS connection?

None, because you are verifying an XML document and not establishing a TLS connection at all.

"x509 certificate chain incomplete of leaf TP not found"

This means that you receive a certificate, but because you are missing one or more certificates in your trust store, the certificate itself cannot be verified.
If you cannot verify the certificate then anybody could have created the certificate and send you the signature. So even if the signature verifies against the certificate, the result is meaningless.
Now there are two things that can be wrong:

you didn't establish any secure certificate to use with the sender of the XML document;
the signature or trust store is missing one or more intermediate certificates.

The best generic solution is to make sure all intermediate certificates (up to the trust point) are included in the XML signature and make sure you trust the root certificate in your particular trust store.


Proof of using a literal from known set, inside a computed formula Suppose I have publicly revealed the value of  $\phi(u) = A+Bu$,
where A, B, u are private values from a large group, that I want to keep in secret.

Furthermore, I want to add proof that the value $u$ is from a publicly known set of values, without revealing its real value.

How can I do that?
Same question with proof about $A$

I thought about:

A zero-knowledge scheme, but it seems to be inadequate to that purpose because the value $u$ is publicly known.
Private set intersection - But since $u$ is from a publicly known set I might reveal its value.

In Crypto 94, Cramer, Damgård and Schoenmakers proposed Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols with abstract below:
Suppose we are given a proof of knowledge $P$ in which a prover demonstrates that he knows a solution to a given problem instance. Suppose also that we have a secret sharing scheme $S$ on $n$ participants. Then under certain assumptions on $P$ and $S,$ we show how to transform $P$ into a witness indistinguishable protocol, in which the prover demonstrates knowledge of the solution to some subset of $n$ problem instances out of a collection of subsets defined by $S.$
For example, using a threshold scheme, the prover can show that he knows at least $d$ out of $n$ solutions without revealing which $d$ instances are involved. If the instances are independently generated, we get a witness hiding protocol, even if $P$ did not have this property.
Our results can be used to efficiently implement general forms of group oriented identification and signatures. Our transformation produces a protocol with the same number of rounds as $P$ and communication complexity $n$ times that of $P.$ Our results use no unproven complexity assumptions.
The authors also state:

Our techniques are to some extent related to those of De Santis et al. The models are quite different, however: They consider non-interactive proofs of membership, while we consider interactive proofs of knowledge.

The paper is available here


Difference between Multi-linear and Multi-Secret Sharing Schemes I've been reading papers on secret sharing schemes and came to two different terms, namely, multi-linear secret sharing schemes and multi-secret sharing schemes. As an example, the term multi-linear is used by Beimel et al. in Multi-linear secret-sharing schemes publication.  On the other hand, the term multi-secret is used by Yang et al. and Chien et al. in A $(t, n)$ multi-secret sharing scheme and A Practical $(t,n)$ Multi-Secret Sharing Scheme respectively. Are these two terms the same?
I would appreciate someone helping me with this.

As quoted by Yang's A (t,n) multi-secret sharing scheme line 76.

In fact, various secret sharing schemes have different approaches.

So by using the term Multi-secret sharing means to share multiple secret by any means. That makes Multi-Linear secret sharing is a subset of Multi-secret sharing.
I'm not 100% sure on this but it appears to me that for Linear secret sharing scheme, it involves solving matrix to find a linear recombination of each part of the secret and used it to reconstruct the hidden secret.
In this sense, Chien's A Practical (t,n) Multi-Secret Sharing Scheme is close to Multi-Linear secret sharing scheme in the sense that it has a matrix and you need to solve an equation to find the secret. The different between the two scheme is on how you construct the matrix.
On the other hand, Yang's work relies on Shamir's Secret Sharing as quoted in line 80.

In this article, we will propose a multi-secret sharing scheme based on Shamir's secret sharing


Which public key cryptosystem has the highest security/keysize rate? I'm working on a 16-bit processor msp430 and I need to know what I need to study when it comes to key size efficiency of a public key cryptosystem.

Every public-key system that I have seen in the constrained space was based on elliptical curves instead of the classic RSA scheme.  This is primarily because cycle time is not as important as memory footprint and the 160-bits in ECC is believe to be roughly the same strength of 2048-bit RSA.

There seems to be some specific papers relevant to the MSP430 already.  If you wanted to explore the space, you should start by looking at the cost in memory of storing the long binary words and the cost of each operation in memory.  This will give you a good feel for the total memory, but not the calculation time.  You also will find that things will be much smaller if you do it in assembly.


Difference between salted hash and keyed hashing? A cryptographic salt is additional input other than message itself for a hash function so that it prevents attacker from launching dictionary attacks . Usually the salt is stored along with the hash of say the password etc.

Keyed Hashing is secret key is used as input for hashing along with message like HMAC .

Now is there a difference between salted hash and keyed hash ?

Keyed hashing is usually used to build message authentication codes (MACs), the most common of which is the hashed-based MAC (HMAC).

MACs are basically cryptographic checksums. They are used to detect when an attacker has tampered with a message. Therefore they require a secret key (to be withheld from an attacker) and should be as fast as possible (to reduce overhead).

Salted hashing has a completely different purpose, which you noted. Because they are intended to deter brute-force attacks, they are intentionally designed to be slow. Also, as you said, salts are not assumed to be secret.

You can build a salted hash out of a MAC by using PBKDF2, which basically applies the MAC a lot of times (to make it slower).


What is a randomly derived key? It is a well-known fact that using the same key + nonce combination with a stream cipher twice breaks security. The NaCl library has different primitives for authenticated encryption (i.e., xsalsa20poly1305 and aes256gcm) and its website warns:

  Beware that some of these primitives have 8-byte nonces. For those primitives it is no longer true that randomly generated nonces have negligible risk of collision. Callers who are unable to count 1,2,3,..., and who insist on using these primitives, are advised to use a randomly derived key for each message.

Now, I'm wondering: what is a randomly derived key ?

If I use Argon2i to derive a key K from an user-entered password and random 32-byte (256 bits) salt, is the key K a "randomly derived key" ?

“Randomly derived” is not standard phrasing and I suspect that it isn't what the author meant to write. From context, what is necessary here is to have a distinct key for each message. This can be achieved either by randomly generating a key (I think that's what the author meant to write) or by deriving a key using a key derivation function with a unique input. The second possibility could be called “pseudorandomly deriving a unique key”, because a KDF should be indistinguishable from random if you don't know its secret input, but usually we just say “deriving”.

Since the problem to solve here is the absence of a unique input that's distinct for each message, deriving a key is unlikely to be possible. However, it could be possible if there is a unique input for each message, but it isn't a simple counter, rather it's some long string. With a KDF to derive a key, a unique input of any length is fine. But to derive an 8-byte nonce, a KDF doesn't help, because no matter how it's done, a randomly or pseudorandomly generated 8-byte strings has a $\approx 2^{-32}$ chance of colliding if you generate two of them, increasing as the number of messages increases.

If you derive a key from a password and a salt, that's a pseudorandomly derived key. From the same password and the same salt, you always get the same key. Never use a key that's derived from a password to encrypt actual data: if you ever want to change the password, you'd need to decrypt and re-encrypt the data. Instead, use K only to encrypt a master secret S. Then, on a password change, you only need to decrypt S and re-encrypt it with the new K. Although S can be the key that you use to encrypt data, I recommend adding another level of indirection: it gives you more flexibility. For each message or each conversation, use S as the secret input to an ordinary key derivation function (e.g. KDF1 or KDF2 or HKDF) with two public inputs: a public nonce which is sent with the message (or the first message in the conversation), and a version number which is initially 0 and which you'll increment if you ever want to use S for different things in the future. Once you have that per-message or per-conversation key L, it doesn't matter how it was generated. For each distinct L, if you use L for multiple messages, each needs to have a distinct nonce. If you have different keys L₁ and  L₂, you can use the same nonce twice, once for each key.


derive child keys from a private key My problem is the following:

I have an organization with many members. When someone from the outside communicates with this organization, I want any member to be able to decrypt the communication.

On solution I found would be to use CP-ABE: the organization has a master key and a public key related to it. The owner(s) of the organization can then issue secret keys for all members with a dummy policy that always evaluates to true. That way, an outsider won't have to know anything about the internal structure of the organization or its members; he will just have to encrypt using the organization's public key and any on its members will automatically be able to decrypt using his secret key.

The thing is that I really don't need all the attribute policy part of the CP-ABE so this seems overkill to me. I was wondering if there were any key derivation schemes that would allow me to do so, but I couldn't find any.

I remind my constraints:

the encryption should be done with a single public key for the whole organization
each member should have a different derived secret key

If there is such a scheme, how can we enforce key revocation ?

If key revocation is a requirement, that is, if Alice no longer works for BigCorp, her keys no longer is able to decrypt email to BigCorp, then it either becomes impractical or easy.

That is, you will need to do one of two things:

Either you need to update the master public key when Alice leaves.  This is likely to be impractical.
You require Alice to work with some central body to do the decryption; the central body would verify Alice's employment as a part of the decryption process.

In the latter case, where we can assume a trusted central body, it becomes easy; have the central body hold the private key; it would either decrypt the message for Alice, or alternatively (for example, with RSA or IES), the central body could do a blinded decryption (and so the entity won't be able to track the message)


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

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

So, given a merkle tree with the following properties:

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

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

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

If so, what would these algorithms look like?

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

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

Fig.1 Original Tree.

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

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

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

Updating a Merkle hash tree is trivial.  For instance, if you want to update a leaf, then you update it and then update every node on the path from it to the root.  If you have a particular operation on the tree in mind, the necessary updates follow immediately from the kind of update you want to do.  It's all very straightforward.  There's no reason to expect people to publish papers about this topic in general: it seems too obvious to count as novel, publishable research.

If you are worried about ensuring that the tree remains balanced or that the height remains logarithmic in the number of nodes, you can use any of the standard schemes for balanced binary trees: e.g., AVL trees, red-black trees, splay trees, 2-3 trees, and so on.  You can use any of them with a Merkle tree.  The balanced binary tree data structure describes how you modify the tree on each operation.  The Merkle tree structure adds extra hashes.

Note that there are many standard schemes for balanced binary trees that ensure that all of the basic operations can be done in $O(\lg n)$ time, and ensure that the height of the tree is always bounded by $O(\lg n)$.  Take any of those schemes; it is easy to see that updating all of the Merkle hashes can be done in $O((\lg n)^2)$ time (for each node that is touched, you might potentially need to update the hashes in it and all nodes on the path from it to the root; because of the bound on the height, this means changing at most $O(\lg n)$ hashes per node that is touched).  For many of those schemes, if you analyze them more closely, you find that updating all of the Merkle hashes can in fact be done in $O(\lg n)$ time (because the nodes they touch are all closely related, say, are all on the path from some leaf to the root, or something close to that).

Therefore, you can combine standard balanced binary tree data structures with Merkle hashing to get a Merkle hash tree that can be efficiently updated.  Again, no reason to expect this to lead to lots of publications in the literature: it is combining two standard ideas, and so not terribly novel and thus not likely to lead to lots of publishable papers.

Based on the comments, I realize there is something else I should explain.  In most applications, the exact shape or structure of the Merkle tree is unimportant.  For most applications, all that matters is the set of values that are in the leaves of the tree, and that the height be not too large (say, $O(\lg n)$, where $n$ is the number of leaves).  For those applications, balanced binary tree data structures are fine.

For instance, a typical use of a Merkle tree is as an authenticated set dictionary structure: a data structure that holds a set of values.  The order in which those values appear in the internal data structure doesn't matter; all that matters is, for each possible value, whether it is present in the set or not.  Thus, there is no requirement for the values in the leaves to appear in any particular order -- you can store them in any order you like, and an insert operation can add a new value anywhere in the tree.

More generally, we could imagine some application that cares about the set of values in the leaves and additionally requires they be ordered in some order (say, the values are in increasing order, if you traverse the leaves in left-to-right order).  This too can be accommodated with balanced binary trees.  Notice that such an application still doesn't care about the exact shape or height of the tree, as long as the leaves are in proper order and the height is $O(\lg n)$.

Now if hypothetically we had some application where the exact shape of the binary tree was essential, and each insert operation had absolutely no freedom or flexibility about the shape of the modified tree, then that'd be a different situation.  In that case, standard balanced binary tree data structures would be inapplicable, because they fundamentally need some flexibility in the allowable shapes of the tree.  However, this kind of requirement seems to be extremely rare in practice, and it's not clear what the motivation for it would be.  Therefore, you shouldn't be surprised if there aren't many, or any, published papers that address this odd variant of the problem.

From your comments, it sounds like you are imposing a requirement that is stronger than it needs to be.  It sounds like you are implicitly assuming that the Merkle tree needs to be fully packed at all times, i.e., that it's height needs to be exactly $\lg n$ at all times (plus or minus 1), where $n$ is the number of leaves.  However, there's no need to impose this restriction.  For practical applications, a slightly weaker condition is perfectly adequate: if we can guarantee that at all times the height of the Merkle tree will be $\le 2 \lg n$, that is perfectly sufficient.

And this weaker condition is what allows operations to be efficient.  If you look at standard balanced binary tree data structures, they ensure that the height of the tree is $O(\lg n)$ at all times (or some similar invariant).  This provides a degree of flexibility regarding the shape of the tree: it doesn't have to be fully packed.  This relaxation is what allows balanced binary tree data structures to be efficient (including to efficiently implement the insert-at-front operation you mentioned).  In practical applications there's no reason why we need the Merkle tree to have height exactly $\lg n$; height $2 \lg n$ is just about as good.

Of course, if you have a special application where you need some stricter requirement -- such as that the tree be fully packed, or that it has to have some specific shape at all points -- then standard solutions using standard balanced binary tree data structures might not suffice.  However, that's an unusual requirement whose motivation is unclear, so don't be surprised if there haven't been many, or any, published papers on that variant of the problem.

Hopefully this answers your question about why there haven't been many papers in the cryptographic literature on the topics you mentioned.  The short answer: addressing those problems is straightforward using standard computer science ideas, in the cases that seem to come up in practice, so not publishable (and any remaining variants don't seem to have an obvious practical motivation, so there's no reason why anyone would publish on those remaining variants).


Does one time pad randomness help brute force attacks? I understand that attempting to brute force the decryption of a message coded with a one time pad results in generating every possible message.  The Wikipedia example is that decoding "EQNVZ" with key "XMCKL" produces "HELLO", but the key "TQURI" produces equally plausible "LATER".

However, a "more random" one time pad is supposedly better than a "less random" one time pad.  So there's a way to compare the randomness of two pads, right?

If key TQURI is "measured" as less random than XMCKL, doesn't the likelihood the pad is as random as possible mean HELLO is the more likely message?

Say a coded message consists of only plain English.  A 50-character message could decode to a huge number of possible messages using the same huge number of possible keys.  As we decode character-by-character we can discard anything that isn't obvious English.  That would still leave a large number of possible messages (I have no idea how to estimate how many), but we would simultaneously be increasing the length of the supposedly random key.

If one possible decoding begins ATTACK AT DAWN using the key GJXWHELZYHWLXE while another decoding begins SEND MONEY NOW using the key AABBCCDDEEFFGG, we can probably discard the latter since a pad would never use such a repetitive key.

Therefore, the rule would be to only retain the English decodings for the "most random" keys.  (I have no idea how to pick such a cutoff.)  Could that possibly reduce the potential messages to a reasonable number of candidates?  (I imagine longer keys let you determine their degree of randomness with greater confidence, but I don't know how to calculate that kind of stuff.)

Another possibility would be to retain only messages that parse reasonably well.  BATTALION ALPHA ATTACKS AT DAWN makes sense, but SUNSET DOGGY COOKIE FLOOR can probably be discarded.

Even if individual messages generate a large number of decoded candidates with sufficiently random keys, it would seem a sequence of messages would establish a context that hints at which decodings are valid.  For example, if Message 1 "equally" (because of key randomness) decodes to the candidates

A. WHEN DO WE ATTACK
B. SHOES GREENER ARE
C. MASHED ROOF CARRY

and Message 2 in reply "equally" decodes to

A. ATTACK AT DAWN
B. LEAVE PARLANCE
C. DOG ALPHA MODE

then it seems the "conversation" is probably WHEN DO WE ATTACK/ATTACK AT DAWN.  (Granted, the reply would also decode to ATTACK AT 0100, ATTACK AT 0200, ATTACK AT DUSK, etc., but we're picking the solutions with the "most random" keys.  And even if the keys for ATTACK AT 0100 and ATTACK AT DUSK tied at an equal level of randomness, it's still useful to know an attack is imminent.)  It would seem the more messages you have, the easier it is to guess (or apply some AI regarding) the general thread being discussed.

Therefore, a modified brute force approach would prune away possible but unlikely decodings by (1) discarding invalid and nonsensical content within messages, (2) abandoning decodings with keys not meeting a required threshold of randomness, and (3) abandoning decodings that don't fit intermessage context.  Pruning would have to be done as each new message character is input, to avoid wasting time and space on futile branches.

Would that kind of approach still leave an astronomical number of possible decodings?  Or could it reduce the candidates to a resonably small enough number that NSA computers might possibly be willing to take a stab at predicting (at some level of confidence) what a set of coded messages is probably talking about?

Wikipedia's entry on brute force says a one time pad attack

  ...would eventually reveal every... character string possible, including
  the correct answer – but of all the answers given, there would be no
  way of knowing which was the correct one.

But it seems like some answers could be computed as more likely than others.  Can the set of possible answers be reduced to a reasonable number, especially when the randomness of the required key is taken into account?

There is no such thing as a random key.  There are only randomly generated keys.

What I mean by that is that randomness is not a property of the key (or message, or number, or whatever), but of the process that generates it.  For example, it is not meaningful to ask whether the number 5 is random, or whether it is somehow more or less random than the number 4.  However, if I pick up a die and roll it, and it lands with the "5" face up, then I can meaningfully say that I have just randomly selected the number 5 (and we can also meaningfully discuss just how random or not the way I rolled the die may have been).

In English we often do use "random" as an adjective to describe a thing (as opposed to an action), when we really should be saying "randomly chosen" or something similar.  But this needs to be understood as just a linguistic shorthand.  "A random number" really means "a randomly chosen number", and that's all there is, or can be, to it.

Why am I stressing this point so much?  It's because when you ask something like:

  If key TQURI is "measured" as less random than XMCKL, ...

you're revealing a fundamental confusion about what "a random key" really means.  As I wrote above, randomness is not a property of the key string itself, so there's no way to assert that, say, the string "TQURI" is somehow more or less random than "XMCKL" or, for that matter, "ABCDE".  Even trying to make the comparison is meaningless.

All that we can meaningfully ask is how likely it is that each of those key strings would appear if we, say, randomly picked five letters from a bag containing each letter of the alphabet and wrote them down (returning each picked letter to the bag before picking the next one).  And the answer to that question is that each of those strings (yes, even "ABCDE") is equally likely to be the result of that process.

Thus, if our one-time pad was generated using the method I described (or by any other equally random means), then none of those proposed keys is any more likely to be the correct one than any other, and so examining them yields no information about the message.

Ps. Yes, this also means that randomness testing is, strictly speaking, a fool's endeavor: a truly random process is equally likely to output any string of a given length, so no such string can be said to be any more or less random than any other in that sense.

The best we can do is to look for distinctive features that may appear disproportionately more often in the results of certain kinds of non-random (or incompletely random) processes, and declare the observation of such features as evidence that the process that generated the output may not be perfectly random.  In that sense, it would be more appropriate to call any such tests "non-randomness testing".

Even then, in doing so, we must necessarily accept the possibility of "false positives", i.e. the possibility that even a perfectly random process can, and will, occasionally generate outputs that look like the output of some non-random process.  A perfectly random 5-letter string generator must, necessarily, generate the string "AAAAA" with probability $1/26^5 \approx 0.00000008$ — and if it did not, it would not be perfectly random.


Converting a "raw" non-ASN.1 EC private key to a public key? I have this ECDSA private key that isn't very important, but I do not have it in any other format.

008AF2DA031B2DC39FBE418A238EFDA3B10ABC7C77FE12A750BFE899

I also need it in public form with a size of 0x3C. I don't know how to start with this.
Of course, OpenSSL chokes on it, but that's because it isn't in ASN.1 format, and again I don't know where to start with that.

Without knowing which domain parameters were used this question is impossible to answer. The problem is that the value of the private key is random within the domain.

So although we know that the key size is about 224 bits, there is no way to validate any public key value, because the public key is calculated using the random private key as input in the first place. To be precise, it is the multiplication of the private key with base point $G$ of the curve. This means that we generate a valid public key whichever curve / set of domain parameters we use.

Another issue is the required key size. Normally a public key is identified using a compressed or uncompressed key point. An uncompressed point would add 1 byte for an identifier. However, this in turn is usually put into an ASN.1 BIT STRING, which adds 3 bytes if we assume DER encoding.

So in that case we would for instance get:

033a00046bf056effd0478f8cfe52a07ac42d098f7775314aa84ff4657719c529ce3c117062b42f67b35e2d19276537ea44a14a3b41a072d7fa3c0b7

for P-224 and

033a0004aee24d6692b745b4ecb76d2aff13e51ce177a34f00b5d6c92778d1367dbdb2dd6283fdec3966d33cb800a0e6e5d2060b0daf7e8382e3736e

for brainpoolP224r1, however with no method to distinguish between either two, and there may be more candidates.

Verifying any previously generated signature should of course enable you to select the correct value.