<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Darshana V on Medium]]></title>
        <description><![CDATA[Stories by Darshana V on Medium]]></description>
        <link>https://medium.com/@darshanav?source=rss-68a3bb1045b2------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/0*TMgWOEWG6IvZlsjL.jpg</url>
            <title>Stories by Darshana V on Medium</title>
            <link>https://medium.com/@darshanav?source=rss-68a3bb1045b2------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Fri, 20 Nov 2026 02:12:48 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@darshanav/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[The Correctness Gap: 38% of LLM code that passes tests has hidden bugs]]></title>
            <link>https://medium.com/@darshanav/the-correctness-gap-38-of-llm-code-that-passes-tests-has-hidden-bugs-c1beea717395?source=rss-68a3bb1045b2------2</link>
            <guid isPermaLink="false">https://medium.com/p/c1beea717395</guid>
            <category><![CDATA[code-quality]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[software-engineering]]></category>
            <category><![CDATA[formal-verification]]></category>
            <category><![CDATA[artificial-intelligence]]></category>
            <dc:creator><![CDATA[Darshana V]]></dc:creator>
            <pubDate>Sun, 07 Jun 2026 06:07:56 GMT</pubDate>
            <atom:updated>2026-06-07T06:07:56.723Z</atom:updated>
            <content:encoded><![CDATA[<h3>Why pass@k is the wrong metric for evaluating LLM code generation</h3><p><em>Code and data: </em><a href="https://github.com/darshana-v/llmcodeprobe"><em>github.com/darshana-v/llmcodeprobe</em></a></p><p>Every major LLM code benchmark (HumanEval, MBPP, SWE-Bench, LiveCodeBench) works the same way: generate code, run tests, report the pass rate. The implicit assumption is that passing the test suite is a reliable proxy for correctness. It isn’t.</p><p>I built <strong>LLMCodeProbe</strong> to apply formal analysis techniques to LLM generated code that passes all tests. The results: <strong>17.4%</strong> of human-written HumanEval reference solutions and <strong>38.5%</strong> of LLM-style solutions containing bugs that no test catches but symbolic execution, property-based testing, or boundary analysis does.</p><p>I call this the <strong>correctness gap</strong>: the fraction of test-passing solutions with formally discoverable bugs.</p><p>Test suites are finite. HumanEval averages 7.7 tests per problem. A function that handles those 7.7 inputs correctly can still crash on the infinity of inputs the tests don’t cover.</p><pre>                solutions with hidden bugs<br>gap =  ──────────────────────────────────────────<br>            solutions that pass the test suite</pre><p>A gap of 0.15 means 15% of “passing” solutions have bugs discoverable by formal analysis. This is a lower bound obviously, so formal analysis can’t find everything, so the true rate of buggy but test-passing code is at least this high.</p><h3>Working of LLMCodeProbe</h3><p>Three analysis layers, each targeting different bug classes:</p><ul><li><strong>Layer 1: Boundary analysis</strong> (&lt; 1ms per function): Inject known dangerous inputs- empty lists, zero divisors, integer extremes, null bytes, and check for crashes.</li><li><strong>Layer 2: Property-based testing</strong> (~1–5s per function): Generate random inputs guided by type annotations using <a href="https://hypothesis.readthedocs.io/">Hypothesis</a>, automatically shrink failing cases to minimal counterexamples. Catches bugs where the failing input isn’t a standard boundary value.</li><li><strong>Layer 3: Symbolic execution</strong> (~5–30s per function): Reason over all inputs simultaneously using <a href="https://github.com/pschanely/CrossHair">CrossHair</a> and Z3. If it finds no counterexample within the timeout, the property holds for the entire input space. The most expensive layer, but it finds bugs no amount of random testing would discover.</li></ul><p>Every bug produces a concrete counterexample, i.e. a specific input that triggers the failure.</p><h3>Results</h3><h4>HumanEval’s ground truth is 17.4% buggy</h4><p>I ran boundary analysis on 50 HumanEval canonical solutions — the human-written reference implementations shipped with the benchmark. These are the “ground truth” that models are compared against.</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fdatawrapper.dwcdn.net%2F5r5iY%2F1%2F&amp;display_name=Datawrapper&amp;url=https%3A%2F%2Fdatawrapper.dwcdn.net%2F5r5iY%2F1%2F&amp;image=https%3A%2F%2Fdatawrapper.dwcdn.net%2F5r5iY%2Fplain-s.png%3Fv%3D1&amp;type=text%2Fhtml&amp;schema=dwcdn" width="600" height="433" frameborder="0" scrolling="no"><a href="https://medium.com/media/7c27637670a358ab722d708048a49bfe/href">https://medium.com/media/7c27637670a358ab722d708048a49bfe/href</a></iframe><p>8 of 46 passing solutions crash on inputs the tests never exercise. The dominance of ZeroDivisionError reveals a systematic blind spot: HumanEval almost never tests zero or empty inputs.</p><h4>LLM-style code has a 38.5% correctness gap</h4><p>I then tested 15 solutions written to mimic common LLM output patterns involving code that passes all tests but lacks the defensive programming a careful human would include. Missing empty-input guards, no zero-division checks, unhandled negative indices.</p><iframe src="https://cdn.embedly.com/widgets/media.html?url=https%3A%2F%2Fdatawrapper.dwcdn.net%2FwGWRS%2F1%2F&amp;type=text%2Fhtml&amp;schema=dwcdn&amp;display_name=Datawrapper&amp;src=https%3A%2F%2Fdatawrapper.dwcdn.net%2FwGWRS%2F1%2F" width="600" height="264" frameborder="0" scrolling="no"><a href="https://medium.com/media/7239c6e652d5211e9e7a5c176be23bcd/href">https://medium.com/media/7239c6e652d5211e9e7a5c176be23bcd/href</a></iframe><p>The gap more than doubles. LLM-style code is disproportionately brittle on boundary inputs because LLMs optimize for the test distribution, not the full input domain.</p><h4>A better metric: deep@1</h4><p>I also introduce a three-level scoring system:</p><ul><li><strong>Level 1 (TEST):</strong> Passes tests. This is what pass@k measures.</li><li><strong>Level 2 (ROBUST):</strong> Passes tests AND survives boundary + property-based analysis.</li><li><strong>Level 3 (VERIFIED):</strong> Passes tests AND boundary AND symbolic verification.</li></ul><p>I define <strong>deep@1</strong> as the rate of solutions reaching Level 2 or higher. Two models can both score 100% pass@1 — identical on standard benchmarks — while one has a deep@1 of 90% and the other 40%. pass@1 can’t tell them apart, deep@1 can. The next step is running frontier models (GPT-4o, Claude, Deepseek-Coder) through this benchmark to produce real cross-model deep@1 comparisons.</p><h3>How is this different from EvalPlus?</h3><p>EvalPlus (<a href="https://proceedings.neurips.cc/paper_files/paper/2023/hash/43e9d647ccd3e4b7b5baab53f0368686-Abstract-Conference.html">NeurIPS 2023</a>) tackled the same underlying problem by adding 80x more tests to HumanEval. Pass rates dropped by up to 28.9%, showing test suite inadequacy is a real problem. But EvalPlus stays within the test-based paradigm: 80x more tests is still a finite sample. A function that passes 13,000 tests can still fail on the 13,001st input.</p><p>LLMCodeProbe uses formal analysis:</p><ul><li>Symbolic execution reasons over the entire input space simultaneously</li><li>Property-based testing generates from universally quantified properties and shrinks to minimal counterexamples</li><li>Boundary analysis targets the exact input partitions where bugs concentrate</li></ul><p>When a bug is found, it produces a mathematically concrete counterexample — not just another test case, but a proof the code is wrong. When it finds no bug, the guarantee is stronger than any finite test suite can provide (within the analysis scope).</p><h3>The deeper problem: specification quality</h3><p>Micorosft Research’s RiSE group recently used AI agents to produce 100K+ lines of formally verified code. Then they tested whether the specs themselves were meaningful. 15% weren’t — a verified hash table’s insert could always return false ; a verified Dijkstra’s only proved distance(source, source) &lt;= 0 , etc.</p><p><em>Source: </em><a href="https://risemsr.github.io/blog/2026-04-16-spotting-specs/"><em>https://risemsr.github.io/blog/2026-04-16-spotting-specs/</em></a></p><p>This is spec gaming: code satisfies the formal objective while missing the intent. The correctness gap measures the distance between “passes tests” and “actually correct” and the specification gap measures the distance between “satisfies spec” and “does what we mean”. LLMCodeProbe’s benchmark already includes structured pre/postconditions, and making these executable is the next research step.</p><p>This work has clear limitations that I haven’t measured yet:</p><ul><li><strong>Small sample sizes</strong>: 50 canonical solutions + 15 LLM-style solutions. These numbers will shift as we scale to the full HumanEval + MBPP benchmarks and test more model outputs from GPT, Claude, and DeepSeek.</li><li><strong>Type annotation dependency</strong>: The boundary and Hypothesis analyzers need type annotations to generate inputs. Functions without annotations are partially skipped.</li><li><strong>Lightweight postconditions</strong>: CrossHair needs postconditions to check against. I auto-generate basic type-checking postconditions, but richer specs would catch more semantic bugs (not just crashes).</li><li><strong>Python only</strong>: Extending to Rust, Java, or C would require different symbolic backends.</li></ul><p>The code, data, and benchmark are open-source at <a href="https://github.com/darshana-v/llmcodeprobe">github.com/darshana-v/llmcodeprobe</a>. If you run it on your model’s outputs, I’d love to see the results.</p><pre>pip install -e .<br>python -m llmcodeprobe.run \<br>    --problems datasets/humaneval/HumanEval.jsonl \<br>    --solutions your_model_solutions.jsonl \<br>    --output results/</pre><p><em>I’m a researcher working on AI safety, formal methods, and code verification. More at </em><a href="https://github.com/darshana-v"><em>github.com/darshana-v</em></a><em>.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=c1beea717395" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Getting on Board — Festival of Trusteeship — Day 3]]></title>
            <link>https://medium.com/jrscholarshipnitt/getting-on-board-festival-of-trusteeship-day-3-83e83d4bee43?source=rss-68a3bb1045b2------2</link>
            <guid isPermaLink="false">https://medium.com/p/83e83d4bee43</guid>
            <category><![CDATA[board-of-trustees]]></category>
            <category><![CDATA[scholarship]]></category>
            <category><![CDATA[recruiting]]></category>
            <category><![CDATA[jspf]]></category>
            <category><![CDATA[trusteeship]]></category>
            <dc:creator><![CDATA[Darshana V]]></dc:creator>
            <pubDate>Sun, 07 Nov 2021 13:39:12 GMT</pubDate>
            <atom:updated>2021-11-10T11:46:22.161Z</atom:updated>
            <content:encoded><![CDATA[<h3>Getting on Board — Festival of Trusteeship — Day 3</h3><p>I am grateful to have attended the Festival of Trusteeship along with a few peers from JSPF and have consolidated my notes from Day 3 in this article. The following session was a part of the “Refining Skills” track as part of the Festival of Trusteeship on the 3rd of November 2021. The sessions in this track were all about bringing the charity leadership board to the fore and honing your governance expertise.</p><h3><strong>Impact: What does it mean for trustees?</strong></h3><p>The session covered a few critical aspects regarding the significance of impact for the board, what trustees need to know about impact, how impact can be recognised, and ended with a few practical tips and techniques that were consolidated in a framework to identify and work on achieving the desired impact. Although the sessions and discussions were specifically directed towards small and medium-type charities/organisations, the frameworks and ideas mentioned could be extended to organizations of any size.</p><h4><strong>Words matter</strong></h4><p>Words matter, especially when you are trying to explain what your charity ACTUALLY does.</p><blockquote>“I’m so clever, that sometimes I don’t understand a single word of what I’m saying”</blockquote><blockquote>-Oscar Wilde</blockquote><p>It’s important to clearly mention the vision and mission your charity holds and express it without any jargon.</p><blockquote>Don’t be a buzzword Barry or a jargon Janet.</blockquote><p>One way to proceed through this is to ask yourself as a member — Is there anything else that you find to be more important than the mission and vision? Most charities and organizations focus on making a meaningful impact through their work. Defining the impact clearly and ensuring its aptness is key to:</p><ul><li>Monitor funding targets and outcomes</li><li>Learn, reflect, improve and change</li><li>Motivate staff, volunteers, and others</li><li>Inform and inspire support</li></ul><h4><strong>Impact: What you need to know</strong></h4><p>Now that the importance of specifying the impact your charity creates was understood, the question of how to clearly establish your charity’s impact arose. The speaker, <a href="https://www.linkedin.com/in/steveallman">Steve Allman</a>, discussed a few critical points that could be instrumental in your efforts to define the impact of your charity:</p><ul><li>Ask questions — Why is something important for your charity?</li><li>Focus on the purpose, effect, and outcome of your actions</li><li>Consider the likely audience being targeted</li></ul><h4><strong>Impact: How can you find out?</strong></h4><p>One of the trustees I happened to converse with in a breakout room mentioned she was unsure of her exact contribution to the organization and mentioned how charting out the expectations as a trustee would help. This led us to ponder over external ways to measure our individual impact. A few of my takeaways from the external sources who can inform about your impact were:</p><p><strong><em>Who can tell you about impact?</em></strong></p><ul><li><em>Clients, service users, beneficiaries</em></li><li><em>Internal: paid staff and volunteers</em></li><li><em>External: funders, referrers, partners</em></li></ul><p><strong><em>What can tell you about impact?</em></strong></p><ul><li><em>Interviews, surveys, workshops</em></li><li><em>Case studies, observations, feedback</em></li><li><em>Funding reports, management reports</em></li><li><em>Social media posts, maps</em></li><li><em>Photography, films, illustrations, art</em></li></ul><p>And finally,</p><h4><strong>Things to consider:</strong></h4><p>Defining your impact, recognising and working on it can be made better with these valuable points kept in mind:</p><ul><li>Use the right methodology to define your impact — A sledgehammer is not used to crack a nut. Organize your strategies specific to your charity — lose what doesn’t aid the goal.</li><li>Identify your audience. Who are you trying to engage and what’s the best way to engage with them?</li><li>Go through potential risks. Does your impact activity post any risks to yourself or your audience?</li></ul><p>The above tips are beautifully consolidated in the following impact framework:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/920/1*ekCtQd2CTEAbAO-OfeCn1Q.png" /><figcaption>Impact framework</figcaption></figure><h3><strong>How to shortlist and interview trustees?</strong></h3><ul><li>Work on your <strong>trusteeship constitution</strong> — containing details of trustee Code of Conduct, role and responsibilities of the trustees, powers of the trustees and checks and balances on those powers etc.</li><li>While deciding on the people who will be involved in the recruitment process in different roles and capacities, make sure to account for <strong>conflicts of interest</strong>.</li></ul><blockquote>For example; you cannot have the CEO of the non-profit recruiting for the trustees because there’s a direct conflict of interest involved there. While the recruitment team MUST consult and seek the views of the CEO, the CEO shouldn’t be involved in the final voting or scoring.</blockquote><ul><li>While designing the recruitment process, see if you can make the process <strong>experiential</strong>. This will be a win-win for the parties involved in the process — the prospective trustees will get a ‘taste’ of the work they will be involved in while the recruitment team will get a first-hand view of how the prospective trustee functions.</li><li>Be extremely mindful of designing the recruitment process for <strong>diversity and inclusivity</strong> rooted in the ecosystem that your non-profit functions in — think of the societal privileges/exclusions that exist in the general culture.</li></ul><blockquote>I <strong>would like to cite an experience shared by a fellow participant</strong> — when they were recruiting for trustees in a culture where women generally undersell themselves (which is true in most parts of the world really), they made sure to interview ALL the women candidates to account for the fact that in that culture it was highly likely that the women applicants might have been underselling themselves for the position.</blockquote><ul><li>There is a lot of scope for<strong> innovating</strong> upon the recruitment process. Don’t shy away from designing innovative ways of recruiting — but maintain the rigor in the process. For example — how about you invite video applications?</li><li>While you are setting out to design the recruitment process, don’t think of it as a process with a definite start and a definite end — rather think of it as ‘<strong>pipelines</strong>’.</li></ul><blockquote><strong>Idea proposition</strong> (<em>personal, not mentioned in the conference</em>): How about we have a feature called ‘observer trustees’ — something<em> similar</em> to the concept of ‘observer states’ in diplomatic groupings? This would be sort of an amalgamation of participation, training, and recruitment — participatory recruitment!</blockquote><ul><li>Thoroughly go through all the<strong> legalities (governing documents, laws etc) of the trustee recruitment process in your country of operation</strong>. This is a MUST — both for recruiting and onboarding trustees.</li></ul><blockquote>A few points to remember with respect to interviewing:</blockquote><blockquote>Design the process for <strong>accessibility.</strong> This is crucial so you can attract diversity.</blockquote><blockquote>Only a <strong>diverse recruiting team</strong> can recruit a diverse board. Ensure there is diversity on your trustee recruitment team.</blockquote><blockquote><strong>Use set questions</strong> during interviews — go deeper if needed during the interview — but use the same set of questions as starting questions for every prospective trustee.</blockquote><blockquote>Make it a<strong> two-way</strong> interview process where the interviewees can also ask you some questions.</blockquote><blockquote>In the interview, do NOT assume or test for questions that can be easily learned.</blockquote><blockquote>Explain the entire process in advance and <strong>stick to it</strong>.</blockquote><blockquote><strong>Help candidates be their best</strong> during the recruitment process. Design ways to offer that help/support.</blockquote><blockquote>Design for an <strong>interviewer’s notes booklet</strong> where each interviewer records their comments, observations, etc in a similar format — a pre-defined format.</blockquote><ul><li>Have the <strong>ENTIRE</strong> recruitment process planned to a T, <strong>BEFORE</strong> you open up for applications. This is crucial!</li></ul><blockquote>Decide <strong>who</strong> would do the shortlisting.</blockquote><blockquote>Decide the <strong>metrics</strong> you would look at for shortlisting. While there is always some subjectivity that will inevitably creep in, put some thought and effort into making the shortlisting and interviewing metrics as scientific and objective as possible. This can be tricky!</blockquote><blockquote>Ensure that your shortlisting criteria doesn’t in some way disadvantage the groups you are trying to attract.</blockquote><blockquote>While designing the shortlisting criteria, have clarity on the <strong>distinction between essential versus desirable criteria</strong>.</blockquote><p>While shortlisting trustees and defining our impact as a trustee can be tricky, these points might make the process easier.</p><p><em>Thanks to </em><a href="https://medium.com/u/492da5b70897"><em>Siddhant Chandra</em></a><em> for his inputs in writing this article. Thanks to </em><a href="https://medium.com/u/91e5da72caa0"><em>Sivaranjani Subramanian</em></a><em> and </em><a href="https://medium.com/u/73283cc80e5f"><em>Jitheshraj Scholarship for promising freshmen</em></a><em> for providing me the opportunity to attend the session and AHEAD Trust for sponsoring it.</em></p><p><em>About the author:</em></p><p><a href="https://www.linkedin.com/in/darshana-v/">Darshana V</a> is an Associate at the Jitheshraj Scholarship for promising freshmen, an initiative by the AHEAD Trust. Darshana is involved in the Engineering team and the Panelist Relations team. She is a current student at NIT Trichy.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=83e83d4bee43" width="1" height="1" alt=""><hr><p><a href="https://medium.com/jrscholarshipnitt/getting-on-board-festival-of-trusteeship-day-3-83e83d4bee43">Getting on Board — Festival of Trusteeship — Day 3</a> was originally published in <a href="https://medium.com/jrscholarshipnitt">Jitheshraj Scholarship for promising freshmen</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Encryption Algorithms — Decrypted!]]></title>
            <link>https://medium.com/spidernitt/encryption-algorithms-decrypted-d9431235b3dc?source=rss-68a3bb1045b2------2</link>
            <guid isPermaLink="false">https://medium.com/p/d9431235b3dc</guid>
            <category><![CDATA[cipher]]></category>
            <category><![CDATA[decryption]]></category>
            <category><![CDATA[hacker-series]]></category>
            <category><![CDATA[encryption]]></category>
            <category><![CDATA[spiders]]></category>
            <dc:creator><![CDATA[Darshana V]]></dc:creator>
            <pubDate>Wed, 04 Nov 2020 12:40:53 GMT</pubDate>
            <atom:updated>2020-11-04T12:40:53.975Z</atom:updated>
            <content:encoded><![CDATA[<h3>Encryption Algorithms — Decrypted!</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*sWZE6cm5_rpS6xSFcrOdaA.jpeg" /></figure><h3>What is encryption? Why do we use it?</h3><p>Encryption is a method by which plain readable text or data is converted into an <strong><em>encoded text</em></strong>, that can only be decoded or converted back into readable text by another person with access to a <strong><em>decryption key</em></strong>. This is usually done so that important data remains inaccessible to unauthorized users to help protect private information, sensitive data, and enhance the security of communication between client apps and servers.</p><p><strong><em>How to encrypt data?</em></strong></p><p>Now that the importance of encryption has been enumerated, we will learn how to encrypt data. An encryption key uses an ‘<em>encryption algorithm’</em> to perform the process of encryption, usually called a <strong>cipher</strong>.</p><p>The encryption algorithm is of two types: <strong>symmetric and asymmetric key algorithms.</strong></p><p>With ‘<strong>symmetric key algorithm’</strong>, both encryption and decryption keys are the same, so the same key must be used to enable secure communication. Symmetric algorithm encryptions are commonly used for bulk data encryption and are fast and easily implemented by hardware. The downside is that anyone with that decryption key can decrypt your data even if it is not intended for them.</p><p>Two of the most important symmetric key algorithms widely used are — <strong>Data Encryption Standard</strong> <strong>(DES)</strong> and <strong>Advanced Encryption Standard</strong> <strong>(AES)</strong>.</p><p>DES is a symmetric block cipher with a key length of 56-bits, while AES is a more mathematically efficient and elegant cryptographic algorithm, with an option for choosing 128-bit, 192-bit or 256-bit key, making it exponentially stronger than the 56-bit key of DES.</p><p>In <strong>asymmetric key algorithm</strong> encryption, two separate but mathematically linked encryption keys are used. A public key is used to encrypt the data and can be distributed while the private key is used to decrypt the data and, therefore, is kept private.</p><p>Through the use of a private key, asymmetric encryption eliminates the preliminary exchange of secret keys, allows for public keys to be shared with anyone, and provides an underlying architecture for digital certificates, digital signatures, and a Public Key Infrastructure (PKI). The disadvantages are that it is slower than symmetric algorithm encryption and that it requires greater computation power.</p><p><strong>This article aims to briefly explain the steps involved in encryption and decryption using <em>AES and DES</em>. </strong>In the last section, we shall further venture into how AES could provide the necessary security that DES failed to.</p><h4><em>What is the DES algorithm?</em></h4><p>The DES (Data Encryption Standard) algorithm is basically a <strong>symmetric-key block cipher</strong> created in the early 1970s based on the <strong>Feistel Structure</strong>. The algorithm takes plain text in 64-bit blocks as input and converts them into ciphertext using 48-bit keys.</p><p><em>Why the Feistel Structure?</em></p><p>A modern block cipher is typically used to replace a block of N bits from plaintext with a block of N bits from the ciphertext. Let us consider an example for N = 4: With 4-bits, there are <strong>16 different possible patterns</strong> (The bit pattern 0000 represents integer 0, the bit pattern 0001 represents integer 1, and so on).</p><p>For an ideal block cipher, the relationship between input and output blocks must be random and invertible, and must thus be a one-to-one function of input block mapped to a unique output block.</p><p>Now, if we consider 64-bit block encryption, each possible input block can be thought to consist of 2⁶⁴ integers and for each such integer, a 64-bit output block. Thus, the size of the encryption key will be of size 64 × 2⁶⁴ ≈ 10²¹.</p><p>This size of the encryption key would make the above idea impractical. Thus, the Feistel structure was introduced to solve this problem.</p><h4><em>Implementing DES algorithm — the Feistel structure</em></h4><p>The DES algorithm for encryption and decryption is based on the Feistel Structure.</p><p>A cryptographic system based on Feistel structure uses the same basic algorithm for both encryption and decryption. It consists of multiple rounds of processing of the plaintext, with each round consisting of a substitution step followed by a permutation step. The input block to each round is divided into two halves with L and R, denoting the left half and right half respectively.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/684/1*JZVFP4ejKH4BTrlv-fwN7A.png" /><figcaption>Feistel structure for symmetric key cryptography</figcaption></figure><p>The algorithmic implementation of DES is known as the <strong>Data Encryption Algorithm(DEA)</strong>. The following figure shows a single round of processing in DEA consisting of the following major steps:</p><ol><li>Key transformation</li><li>Expansion permutation</li><li>S-Box permutation</li><li>P-Box permutation</li><li>XOR and swap</li></ol><figure><img alt="" src="https://cdn-images-1.medium.com/max/728/1*mLDT0GJCAiW83jUdypyWIw.png" /><figcaption>One round of processing in DES.</figcaption></figure><p>For decryption, the same algorithm is used with the order of the 16 round keys reversed.</p><p>DES encryption was broken in 1999 by Electronics Frontiers Foundation, introducing the need for a better algorithm.</p><h4>What is the AES algorithm?</h4><p>AES is a slight variation of the Rijndael cipher invented by two Belgian cryptographers Joan Daemen and Vincent Rijmen in 2000. It is a block cipher with a block length of 128 bits. It allows for three different key lengths: 128, 192, or 256 bits. Encryption consists of 10 rounds of processing for 128-bit keys, 12 rounds for 192-bit keys, and 14 rounds for 256-bit keys, where except for the last round in each case, all rounds are identical.</p><p>In this section, the key length is taken to be 128 bits, and thus there would be 10 rounds of processing.</p><p>Each round of processing includes one single-byte based substitution step, a row-wise permutation step, a column-wise mixing step, and the addition of the round key.</p><h4>Implementing AES cipher</h4><p>We consider the 128-bit block to be a 4 × 4 array of bytes, arranged as follows:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/299/1*3HSuHV3NXeEvXML2dxDExg.png" /></figure><p>Notice that the first four bytes of the 128-bit input block occupy the first column in the array, the next four bytes occupy the second column, and so on.</p><p>This 4 × 4 array of bytes is referred to as the <strong>state array in AES</strong>.</p><p>There is another common useful term associated with AES: <strong>word</strong>.</p><p>A word consists of four bytes (32 bits). Hence, each column of the state array is a word, as is each row. The output state array obtained after the final step is rearranged into a 128-bit output block again.</p><p><em>Steps involved for encryption</em></p><p>The input state array is first XORed with the first four words of the key schedule. It is then continued to the subsequent steps: Each round consists of the following four steps:</p><ol><li>Substitute bytes</li><li>Shift rows</li><li>Mix columns, and</li><li>Add round key.</li></ol><p>The last step consists of XORing the output of the previous three steps with four words from the key schedule.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/581/1*JfCf856IwSRRcnFwQDjGEw.png" /></figure><h4><strong>Step 1</strong>: Substitute bytes for the encryption chain</h4><p>Let xᵢₙ be a byte of the state array for which we seek a substitute byte xₒᵤₜ. We can write xₒᵤₜ = f(xᵢₙ). The function f() involves two nonlinear operations:</p><p>(i) Finding the multiplicative inverse x′ = xᵢₙ−1 in GF(28 ), and then</p><p>(ii) Scrambling the bits of x′ by XORing x′ with four different circularly rotated versions of itself and with a special constant byte c = 0x63. The four circular rotations are through 4, 5, 6, and 7-bit positions to the right. This bit scrambling step can also be expressed by the relation: xₒᵤₜ = A · x ′ + c.</p><h4><strong>Step 2</strong>: Shifting rows</h4><p>The ShiftRows transformation consists of</p><ol><li>not shifting the first row of the state array at all</li><li>circularly shifting the second row by one byte to the left</li><li>circularly shifting the third row by two bytes to the left, and</li><li>circularly shifting the last row by three bytes to the left.</li></ol><p>Now, we can imagine how the array representation of the state array is paramount.</p><p>This operation on the state array can be represented by</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/449/1*V-CLQwjQwsWzEAkjuY2Zpw.png" /></figure><p>Recall that the input block is written column-wise (The first four bytes of the input block fill the first column of the state array, the next four bytes the second column, etc). As a result, shifting the rows in the manner indicated scrambles up the byte order of the input block.</p><h4><strong>Step 3</strong>: Mixing columns</h4><p>Each byte of a column is replaced by a function of all the bytes in the same column such that: Each byte in a column is replaced by two times that byte, plus three times the next byte, plus the byte that comes next, plus the byte that follows. The words ‘next’ and ‘follow’ refer to bytes in the same column, and their meaning is circular, in the sense that the byte that is next to the one in the last row is the one in the first row.</p><p>For the bytes in the first row of the state array, this operation can be stated as</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/467/1*P1fgaCNeSWL7_Gim3MgiWQ.png" /></figure><p>For the bytes in the second row of the state array, this operation can be stated as</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/468/1*aZG7Cv0t07Jeuch4A2nSyQ.png" /></figure><p>For the bytes in the third row of the state array, this operation can be stated as</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/473/1*_xxrzN-sTojJKXgzrcSNPA.png" /></figure><p>And, for the bytes in the fourth row of the state array, this operation can be stated as</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/472/1*zSO8HJh5nfWUQePXjO8Lpw.png" /></figure><p>More compactly, the column operations can be shown as:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/544/1*9ehEAsPNILXpUEuXtVH69Q.png" /></figure><p>where, on the left-hand side, when a row of the leftmost matrix multiples a column of the state array matrix, additions involved are meant to be XOR operations.</p><p>The corresponding transformation during decryption is given by:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/581/1*p2oB66gXIqGJpKMnFZYIKw.png" /></figure><h4><strong>Step 4:</strong> Adding round key</h4><p>Each round has its own round key that is derived from the original 128-bit encryption key in the manner described in this section. The last step of each round (for both encryption and decryption) involves XORing of the round key with the state array. The 128-bit round key is derived from the original 128-bit encryption key using the <strong>AES Key Expansion algorithm</strong>.</p><h3>What makes AES secure?</h3><p>Unlike DES, in AES, the decryption algorithm differs substantially from the encryption algorithm. Although overall, very similar steps are used in encryption and decryption, their implementations are not identical and the order in which the steps are invoked is different.</p><p>As discussed, DES was based on the Feistel network. On the other hand, what AES uses is a <strong>substitution-permutation network</strong> in a more general sense. Each round of processing in AES involves byte-level substitutions followed by word-level permutations. Speaking generally, DES also involves substitutions and permutations, except that the permutations are based on the Feistel notion of dividing the input block into two halves, processing each half separately, and then swapping the two halves.</p><p>Moreover, AES is an example of a <strong>key-alternating block cipher</strong>. In such ciphers, each round first applies a diffusion-achieving transformation operation (which may be a combination of linear and nonlinear steps) to the entire incoming block, which is then followed by the application of the round key to the entire block. Comparing that to DES which is based on the Feistel structure where, for each round, one-half of the block passes through unchanged and the other half goes through a transformation that depends on the S-boxes and the round key.</p><p>Another noteworthy point is that DES is a bit-oriented cipher (The substitution step in DES requires bit-level access to the block coming into a round) whereas AES is a byte-oriented cipher, which makes for <strong>convenient and fast software implementation</strong> of AES.</p><p>Key alternating ciphers lend themselves well to the <strong>theoretical analysis of the security of the ciphers</strong>.</p><p>A similarity that can be noted is that like DES, AES is an iterated block cipher in which plaintext is subject to multiple rounds of processing, with each round applying the same overall transformation function to the incoming block.</p><p>Considering the number of years that have passed since the cipher was introduced in 2001, all of the threats against the cipher remain theoretical — meaning that its <strong>time complexity</strong> is way beyond what any computer system will be able to handle for a long time to come.</p><p>To visualize it, consider the <strong>example</strong> to evaluate the time required to recover 56-bit DES and 128-bit AES key :</p><p>Assuming that the single evaluation of a block cipher takes 10 operations, and 10¹⁴ ≈ 2⁴⁶ operations can be performed per second in the least, then our hypothetical machine would take ≈ 362 seconds to find a 56-bit DES key, and ≈ 36 quadrillion years to find a 128-bit AES key.</p><h4>Why should we learn DES cipher?</h4><p>Despite DES losing the giant position of being the go-to data encryption standard algorithm, it’s still worth learning. There will always be room for the DES algorithm in cryptography because it was the <strong>foundation</strong> for subsequent encryption algorithms, and can be used to understand the current encryption methods better.</p><p>To learn more about how to implement AES using python, the following tutorial shares examples using module Crypto.cipher — <a href="https://pythonprogramming.net/encryption-and-decryption-in-python-code-example-with-explanation/"><strong><em>click here</em></strong></a><strong><em>.</em></strong></p><h3>References</h3><ul><li>The AES standard is described in this official document, <a href="http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf"><strong><em>here</em></strong></a>.</li><li>For further details on the cryptanalysis of AES ciphers and the various attacks on block ciphers, ‘<em>Lecture Notes on Computer and Network Security by Avi Kak</em>’ can be referred to.</li></ul><p><em>This article is published as a part of the ‘</em><strong><em>Hacker Series’</em></strong><em> under </em><a href="https://medium.com/spidernitt"><em>Spider Research and Development Club, NIT Trichy</em></a><em> on a Web Wednesday!</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=d9431235b3dc" width="1" height="1" alt=""><hr><p><a href="https://medium.com/spidernitt/encryption-algorithms-decrypted-d9431235b3dc">Encryption Algorithms — Decrypted!</a> was originally published in <a href="https://medium.com/spidernitt">Spider R&amp;D</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
    </channel>
</rss>