We present Carry-based Differential Power Analysis (CDPA) — a new side-channel attack targeting algorithms that use arithmetic addition. Applied to HMAC-SHA-2, CDPA enables full key recovery from power traces, both in simulation and on FPGA hardware. With as few as 30K traces, secret keys can be recovered in some cases, allowing for forging the HMAC-SHA-2 signature of any message, and with 275K traces, the success rate reaches 100%. This demonstrates that even pure hardware implementations of HMAC-SHA-2 are vulnerable unless properly protected. To our knowledge, this is the first successful non-profiling attack on hardware HMAC-SHA-2.