While the need for quantum-computing proof cryptography increases, I propose a new (?) digital signature algorithm.

Although I find it hard to imagine that I'm the first to come up with this idea, I've not read about it, nor have I seen it being used.

However, I'm not a cryptographer, so I may have missed or be overlooking things. Please let me know if this algorithm was already proposed by others. Also, if anyone believes that this algorithm should /not/ be used, or restrictions should apply to its application, please let me know the reasons why.

Basis
- The privkey (private key) and pubkey (public key) are mathematically independent cryptographically secure random numbers, long enough to (hopefully) be globally unique.

- Only cryptographically secure hash functions (HMACs) are to be used (collissions must be practically impossible to find).

Simplified algorithm
Not taking into account possible length extension attacks:
Notes:
- The plus sign denotes concatenation.
- Sending the public key is optional (the recipient may already possess it or obtain it through some other -trusted- channel).

Full algorithm
Note: applying Argon2 or similar to sig0 between step 1 and 2 may help thwart some attacks.

Please note that this website prevents me from editing (correcting) this text one hour after posting it, so please look at posts below for corrections and/or additions.

SHA-3-256 kan overigens nog een miljoen jaar mee.

Men rekent ermee dat zowel SHA-256 en SHA3-256 ongeveer 2166 “logical qubit cycles” nodig hebben om deze te kunnen kraken.

Dat gaat men dus niet doen, men probeert de sleutel te bemachtigen of de hash via een MiM, TEMPEST, via ondermaats plain txt management of zoiets. De zwakheden van de menselijke factor derhalve, zoals vaak.

Hash collusie is trouwens niet op te lossen.

Maar een collusie veroorzaken voor een nep digitale ondertekening ligt wel degelijk in de mogelijkheden. Helpt jouw idee hiertegen?

luntrus

Dat dachten de bedenkers van MD5 en SHA-1 wellicht ook; enkele tientallen jaren zou al mooi zijn.

Het wellicht grootste probleem van asymmetrische cryptografie is het onterecht erop vertrouwen dat een publieke sleutel van degene is wie zij of hij zegt te zijn (of zegt/suggereert te vertegenwoordigen). Ik zie echter niet hoe ik tegelijkertijd technische problemen en menselijke tekortkomingen zou kunnen adresseren.

Vooral bij inputs die langer zijn dan de output (hashwaarde) is het vanzelfsprekend dat er collisions bestaan. De vraag die we ons moeten (blijven) stellen is of je die collissions binnen een praktisch tijdbestek kunt vinden. Bovendien zijn de huidige (op o.a. RSA gebaseerde) digitale handtekeningen al gebaseerd op hashes; als mijn voorstel bruikbaar is heb ik de niet-quantum-proof component eruit gehaald.

Beste Erik van Straten,

Wellicht valt dit ook toe te voegen, modulaire reken-beveiliging.

Lees: https://nrich.maths.org/4350


luntrus

Je hebt hier een pub/secret keypaar *voor iedere text* .

En wat je "out of scope" gelaten hebt is de distributie ervan , en de koppeling naar de identiteit van de afzender .

Wat de "normale" public key signatures zo sterk/makkelijk maakt is dat de distributie van de public key van de afzender slechts eenmalig is (of hoeft te zijn)- maar ook breed ge-broadcast kan/mag worden , om te kans voor een aanvaller om een valse public key te verspreiden lastig te maken .
En ruim vooraf kan gaan aan het ondertekenen van een brontekst.

Daarboven op zijn er dan de mogelijkheden om public keys te signen (central zoals bij X509) of decentraal zoals bij PGP .
Dat kan bij de gratie van het model dat een entiteit slechts een enkele public key (of een pubkey per jaar) hoeft te verspreiden , en daarmee willekeurig veel bronteksten kan tekenen .
(denk aan de <linux distro pgp key>, die tig packages in de loop van de tijd kan signen .


In jouw schema moet je - op betrouwbare manier - voor *iedere* brontekst een sig0 en sig1 verspreiden op z'n manier dat je iedere keer weer bewijst dat jij het echt bent die de sig0 en sig1 gemaakt heeft.
En dat verspreiden kan pas op moment dat je een brontekst hebt die je wilt tekenen . Ik kan geen pubkey van je meekrijgen tijdens een fysiek bezoek om daarmee dingen die je later geschreven hebt te verifieren .


Met de caveat dat ik ook geen cryptograaf ben - ik zie - als je erin slaagt om aan die voorwaarde te voldoen - zo geen zwakheid .
Alleen - als je toch voor iedere brontekst een sig0/sig1 moet verspreiden op betrouwbare manier waaruit jouw authorship blijkt - wat is dan de meerwaarde ten opzichte van het gewoon leveren van de hash ? Als je de hash van de tekst op dezelfde betrouwbare manier verspreid heb je toch hetzelfde bereikt ?

Ik heb een heel vaag vermoeden dat je schema in de richting van Merkle Tree (1 diep??) zit .

Beste Erik,

Mijn ervaring is een aantal jaren bij Hoge School Technische IT 3e jaars, lambda berekening toetsen, XSS error verificatie toetsen etc.. begeleiden. Nu in de desktop provider opleidingen,alhoewel de meeste kandidaten slechts goede gamers blijven.*)

Thans vrijwillig 12 jaar website security en error-hunting verzorgd t.b.v. van een forum. Daarvoor Fravia adept searchlores/linguïstisch zoeken tot zijn voortijdig verscheiden. (R.I.P.).

Daarnaast online gewerkt t.b.v. sinkholing bij Peter Kleissner, destijds de beste jonge afgestudeerde hacker van Wenen.

Mijn specialiteit javascript errors en retiring procedures. Later kwam ie met de intelx.io zoekmachine op de proppen.

Dan weet je zo'n beetje met welke anonieme figuur je te maken hebt.

groetjes,

luntrus

Als je daarmee bedoelt dat je voor elke signature een nieuw sleutelpaar zou moeten genereren: nee, dat is absoluut niet mijn bedoeling. Wat we nodig hebben (o.a. voor digitale certificaten) zijn herbruikbare sleutelparen, dat is mijn doel.

Overigens sluit ik niet uit dat, afhankelijk van "de sterkte" van het (de) gebruikte hashalgoritme(s), het na een X aantal signatures gezet te hebben, onverstandig is om een sleutelpaar te blijven gebruiken (met elke sig0 lekt er enige informatie over de private key). Maar precies datzelfde probleem bestaat nu ook al (bij de huidige signatures).

Klopt. Maar als ik geen denkfouten heb gemaakt, zal een digitaal certificaat, naast de gebruikelijke inhoud, niet één hash maar twee (sig0 en sig 1 over de inhoud van het certificaat) moeten bevatten. Dat lijkt mij nauwelijks een probleem.

Ook voor PGP/GPG/GnuPG verandert er bijna niets: een public key blijft een public key. De wijzigingen zijn:
1) de signature-zettende software moet twee hashes berekenen (zie mijn voorstel);
2) de standaard voor signatures moet worden aangepast met het opnemen van 2 hashes;
3) de signature-checkende software moet controleren zoals in mijn voorstel.

Ik hoop hiermee de meeste van jouw vragen te hebben beantwoord.

Ik weet van het bestaan van Merkle trees, maar heb mij er nooit in verdiept. Ik ben ook allesbehalve een ster in hogere wiskunde, maar wellicht is dat juist mijn kracht.

Zo zijn er dit jaar al twee kandidaten van de NIST PQC challenge "afgeschoten" (https://arstechnica.com/information-technology/2022/08/sike-once-a-post-quantum-encryption-contender-is-koed-in-nist-smackdown/) die dachten dit soort problemen op te kunnen lossen door er bergen hogere wiskunde tegenaan te gooien (de laatste werd in 1 uur gekraakt op een ordinaire laptop).

Het voordeel van simpele oplossingen, vooral indien bouwend op bestaande en bewezen technologiën, is dat (onverhoopte) kwetsbaarheden snel gevonden moeten kunnen worden. Als de private- en public key wiskundig ongerelateerd zijn (zoals in mijn voorstel), is het m.i. onmogelijk om de private key uit de public key te kunnen afleiden. Het is waarschijnlijk zelfs zo dat als iemand anders toevallig dezelfde public key heeft (bijv. t.g.v. een slechte random number generator), dat bij mijn voorstel, de kans dat de private keys ook identiek zijn, kleiner is dan bijvoorbeeld bij RSA.

P.S. t.o.v. RSA, DSA en dergelijke is mijn voorstel mogelijk "groener": er zou wel eens minder CPU-power voor nodig kunnen zijn.

Waar we dit nodig zouden hebben is voor het beveiligen tegen traffic analyse, data is versleuteld de rest niet. Men weet nu met wie Erik communiceert, dat onder alle omstandigheden.

Moeten we dan gaan wachten tot tor uiteindelijk main stream gaat en wordt dat dan getolereerd?

Een decentralisering via het buzzword 'nudges' in combinatie met ...

Modulaire operatoren:
http://www.java2s.com/Tutorial/JavaScript/0040__Operators/Modulus.htm

Nee, dit is geen versleutelen maar authenticiteit bewijzen.

Als het authentiek bewijzen is, is dit je al voorbereiden op de niet meer te ontlopen surveillance en monitoring van burgers via de EU digitale identiteit.

Je helpt ze zo alleen maar met hun snode plannetjes.

k wil graag code om juist hier zo lang mogelijk van verschoond te kunnen blijven en het hen zo moeilijk mogelijk te maken mij alle rechten te ontnemen als een willoos slachtoffer van hun regel- en machtshonger.

Dat lukt al niet in de cloud en ook niet bij blockchain toepassingen en zeker niet bij CBDC toepassingen.

Vluchten kan dan niet meer, all the clamps will come down ook met een authenticering waar geen EU-burger meer aan te ontsnappen weet. Willen we dat eigenlijk wel?

Die discussie is al elders op dit forum aan de gang, maar de meeste nerds zijn kopschuw voor dergelijke fundamentele keuzen en sluiten zich op in hun techno-bubbels.

Ter verduidelijking, hoe digitaal signeren nu werkt:
Hierbij wordt dus de hashwaarde versleuteld met asymmetrische cryptografie - die waarschijnlijk kraakbaar is met toekomstige quantum computers.

Ter herinnering: het idee achter asymmetrische encryptie is dat je twee sleutels hebt, en dat wat je met sleutel 1 versleutelt, uitsluitend met sleutel 2 kunt ontsleutelen (dus niet met sleutel 1).

Ter vergelijking kopieer ik hieronder mijn voorstel van bovenaan deze pagina:
Merk op dat verificatie hier hetzelfde is als stap 2 bij het signeren (waarbij de uitkomst in een andere "variabele" sig1' wordt opgeslagen om daarna te kunnen vergelijken met de meegezonden sig1).

Een essentieel verschil met de huidige aanpak is dat in mijn voorstel niets omkeerbaar versleuteld wordt (mogelijk zijn er te veel cryptografen die focussen op asymmetrische versleuteling quantum-proof maken).

Feitelijk is mijn stelling dus dat je voor digitale handtekeningen geen omkeerbare versleuteling nodig hebt, maar uitsluitend cryptografische hashfuncties - waarbij het sowieso één van de vereisten is dat ze niet omkeerbaar zijn.

Dat het niet je wens is van een signature schema is mooi, maar je uitleg gebruikt de brontekst als input van sig0 en sig1 .

Ik kon er niet uithalen hoe je een keypaar s0 en s1 op basis van TXT1 zou gebruiken om TXT2 te signen.

Wat ga je nu publiceren als public key waarmee ik je tekst van volgende week kan verifieren ?



Nee - wat je niet hebt duidelijk gemaakt is hoe je schema werkt voor een tweede brontekst .



Danger - crank territory .


Schneier had een goed advies voor beginnende cryptomensen - besteed je tijd aan het *breken* van ideeen .
Iets maken waarvan je zelf geen zwakheid ziet is vrij simpel . Het betekent alleen niets wanneer je kennis in het spotten van problemen nihil is.

Als mijn webbrowser een slotje toont, met in de adresbalk bijvoorbeeld "mijn.ing.nl", dan wil deze "nerd" dat mijn webbrowser met behoorlijke zekerheid verbinding heeft met een webserver van ING. En dat wil ik in elk geval vóórdat de kans bestaat dat een quantum-computer dat kan saboteren. Todo: QPC DH-vervanger.

Mijn vaardigheden in het spotten van kwetsbaarheden zijn verre van perfect, maar ook niet nihil (het is mijn vak, wat geenszins betekent dat ik feilloos ben, maar wel dat ik geen beginner ben).

Juist omdat ik weet dat ik fouten maak en gaten in mijn kennis heb, publiceer ik mijn ideeën en vraag ik om commentaar, in de hoop op de inhoudelijke soort van iemand die voldoende van de materie begrijpt. Overigens heb ik dit ook op de cryptography maillijst (metzdowd.com) gepost, maar daar wacht mijn mail nog op moderatie.

Aan de andere kant weet ik ook dat dit voor veel mensen lastige-, maar wellicht interessant gevonden, materie is, en daarom probeer ik het ook aan die groep (zo goed en duidelijk als ik kan) uit te leggen (zie bijvoorbeeld https://security.nl/posting/767239).

Vervalser kiest eigen tekst en willekeurige sig0, berekent sig1 met
pubkey. Hoe detecteert ontvanger dan de vervalsing? Wat bewijst dat de
afzender de private key weet?

Ik denk dat je - summiere wiskunde kennis - en , vzviw, nul track record in het vinden van zwakheden in andere crypto schema's feitelijk je kennis op dat vlak wel nihil is .

Geen schande - het geldt voor 99.9% van iedereen inclusief mensen die in andere takken van security werken .

https://www.schneier.com/blog/archives/2011/04/schneiers_law.html


https://www.schneier.com/crypto-gram/archives/1999/1015.html#SoYouWanttobeaCryptographer


Daar heb je meer kans op mensen die de literatuur redelijk kennen dan hier.
Mijn kennis op dit vlak is ook verre van expert - beter dan veel anderen in "de security" maar ver weg van mensen die echt in de cryptografie werken.

Zie ook:https://uptime.netcraft.com/perf/graph?orderby=epercent&site=ocsp.digicert.com

Via een Amazon gedreven dienst.
luntrus

Houdt dit draadje in de smiezen. Het wordt interessant, vooral als lieden hier op elkanders schouders willen gaan staan.

Ondergetekende heeft veel geleerd van Erik, en andersom ook wel eens nuttige info aangedragen.

luntrus

Doordat sig1' dan hoogstwaarschijnlijk ongelijk is aan sig1 (met een kans van ruwweg/in de orde van grootte van 1 op 2^hashlengte_in_bits dat ze toevallig identiek zijn - uitgaande van betrouwbare hashfuncties en "echt" random keys die lang genoeg zijn).

Om de tijdens verificatie noodzakelijke waarde van sig0 te kennen, moet je over de private key beschikken om die sig0 te kunnen berekenen. M.a.w. je hebt niets aan een "willekeurige sig0".

Wat je suggereert is vergelijkbaar met dat je, zonder de private key te kennen, een willekeurige PGP "sig" zou kunnen maken die valideert bij de ontvanger (voor dat proces zie https://security.nl/posting/767239).

Een m.i. zeer sterk bewijs (zie bovengenoemde uitzondering) heb je als sig1' gelijk is aan sig1.

Edit 15:31: de uitzondering aangevuld

Iets meer detail. Vervalser kent pubkey, kiest Vtekst en Vsig0 (kan
willekeurige hash uitkomst zijn) en berekent volgens "stap2" Vsig1 :=
hash(pubkey + Vsig0 + Vtext). Vervalser stuurt bericht met Vtekst,
Vsig0, Vsig1 op naar ontvanger. Ontvanger berekent dan conform "check"
sig1' = hash(pubkey + Vsig0 + Vtext), gelijk aan de meegestuurde Vsig1
en accepteert het vervalste Vtekst bericht als getekend door de pubkey
en privkey eigenaar.

In dit schema kan de ontvanger niet controleren dat Vsig0 bij Vtekst
hoort (dat doet het niet bij het vervalste bericht), tenzij die
ontvanger ook over de private key beschikt en daarmee "stap1" kan
uitvoeren. Maar het idee van een digitale handtekening is dat die de
ondertekenaar identificeert doordat alleen de ondertekenaar over de
benodigde private key beschikt.

Dank voor jouw uitleg, je hebt gelijk (en sorry dat ik de eerste keer miste wat je bedoelde). Ik ben in de val getrapt waar ik zelf vaak voor waarschuw: als jij kunt bewijzen dat iets authentiek is, betekent dat niet automatisch dat niemand anders de boel kan bedonderen.

De fout die ik maak is dat sig0 effectief net zo random is als de private key en dus door een aanvaller verzonnen kan worden.

Mijn dank aan allen die hebben meegedacht, vooral aan de Anoniem die mijn fout doorzag. En mijn oprechte excuses voor valse verwachtingen die ik mogelijk heb gewekt.

MIJN VOORSTEL BOVENAAN DEZE PAGINA DEUGT NIET, MIJN EXCUSES.

Terug naar de tekentafel :-(

P.S. ik heb ook een Engelstalige "sorry"-post geschreven, maar die wacht op moderatie. Als die niet wordt doorgelaten zal ik het nog eens proberen.

Daarom gebruikt men connectbot en
https://pubkey.pm[/urlHet is OK dat een pubkey publiek is, niet OK dat ie te wijzigen valt.In geval van Python gebruik SIP of swig en gebruik cython.Lees: https://crypto.stackexchange.com/questions/48423/is-it-bad-to-expose-the-public-keyluntrus

ENGLISH READERS: an Anonymous visitor of this site pointed out correctly (thanks to her or him!) that I made a mistake in my proposal at the top of this page (both the Dutch and English versions).

I did not take into account that an attacker does not need the private key to generate a random sig0 and use that value to sign the text. Thanks again to Anonymous for pointing out my oversight. My sincere apologies for possibly creating false expectations.

MY PROPOSAL AT THE TOP OF THIS PAGE IS FLAWED, MY APOLOGIES.

Back to the drawing board :-(

We geven echter niet op en gaan op basis van andere premissen code opzetten, op basis van tijd-differentiatie, klopt die niet valt er het volgende te ontwaren: https://unix.stackexchange.com/questions/604373/curl-7-cant-complete-socks5-connection-to-0-0-0-00-1

Kun je dit implementeren, Erik? Hoe tijd-differentiatie quantum AI verslaan kan, althans modulaire encryptie op basis hiervan.

luntrus

Maar wat is hier nu precies “kwantum” aan?
Die eerste zin is clickbait.

Elk device, dus elke keyhouder, heeft dus een exacte tijd en ook de exacte tijd van elk device verschilt fractioneel.

Dat fractionele verschil kan onze unieke signatuur uit gaan maken, waartoe een anders fractioneel verschillende key(s) geen toegang hebben.

Kan dit reëel in code worden uitgevoerd, het modulair procedeeracht me op dit idee.

luntrus

Het device waarop ik hier dit berichtje schrijf, wijkt 1,9 seconde af van de tijd hier gegeven: https://time.is dat is mijn device-tijd. Een ander device kan een andere afwijking vertonen, bijv. 0,9 seconde.

luntrus

Betere precisie geeft https://clock.zone
Gaat over 0,284 sec precisie bij 120 sec device verschil.

Werkzaam voorbeeld: http://www.ntp.org/ntpfaq/NTP-s-config-adv.htm en http://www.ntp.org/ntpfaq/NTP-s-config-adv.htm#Q-CONFIG-ADV-AUTH-AUTOKEY
luntrus

Nog mijn wonden likkend na het debacle van gisteren (https://security.nl/posting/767297): om verwarring bij nieuwe lezers te voorkómen, stel ik voor dat degenen die iets over potentieel bruikbare alternatieve algoritmes willen schrijven, daar een nieuw topic voor te starten.

Kritiek of opmerkingen hieronder over mijn stommiteit begrijp ik, maar om zoveel mogelijk te verhinderen dat nieuwe lezers denken dat zij mijn posts bevenaan deze pagina serieus kunnen nemen (ik kan ze -helaas- niet meer editten en "inline" daarvoor waarschuwen), vraag ik elke volgende reageerder vriendelijk om elke post af te sluiten met onderstaande twee regels, graag met vette opmaak:

LET OP: het algoritme bovenaan deze pagina is onjuist en onbruikbaar.
NOTE: the algorithm at the top of this page is flawed and should not be used.

Leuk draadje. Ik moest er even inkomen (waarom zou dit werken? Toch maar doorlezen want Erik heeft het geschreven...). Ik zag het daarnet pas. Ergens klopte het gevoelsmatig niet maar kon de vinger er niet op leggen tot ongeveer bij de reactie van Gisteren, 13:51 door Anoniem : de methode kan worden gebruikt om de integriteit vast te stellen, maar datgene wat Erik probeert te voorkomen (asymetrische encryptie) is nodig om de authenticiteit van de zender vast te stellen. En hierboven correct en volledig uitgelegd door Gisteren, 16:00 door Anoniem . Erik, Luntrus en Anoniem: bedankt voor het puzzeltje :-)
Q

LET OP: het algoritme bovenaan deze pagina is onjuist en onbruikbaar.
NOTE: the algorithm at the top of this page is flawed and should not be used.