*sigh*
Yes, they're constitutional. There are only two possible legal challenges to the constitutionality of SS. One is the reserve clause which was struck down because the constitution allows the federal govt. to tax in the interest of the general public good. The other is that a payroll tax for social spending isn't actually mentioned in the Constitution. This was rejected because the definition of taxes used by the opponents of social security would be so narrow that if the court found in favor of it that it would rule out the ability of the federal government to tax "providing for the general welfare", which is a right given the feds specifically in the constitution.
So the OP is right in that if you want to do away with entitlement programs you need a new constitution.
http://www.socialsecurity.gov/history/court.html