Students who have been in the U.S. less than five years (and are therefore non-residents for tax purposes) and who are on practical training off-campus are not subject to any FICA (Social Security) and Medicare withholdings. The mechanism for the exemptions are found under Internal Revenue Code 3121(b)(19) and is available to persons on F-1, J-1, M-1 and Q immigration status. It is a blanket exemption with the only qualification being that the person be a nonresident for tax purposes and that the work is authorized (CPT, OPT). IRS Publication 519 is a good resource.

Though F-1 students working off campus are exempt from FICA, they are subject to higher federal (and state) withholding for nonresident aliens.